99클럽 코테 스터디 14일차 TIL

비기너

문제

10845번: 큐

# 큐

https://www.acmicpc.net/problem/10845

풀이

자바에 구현된 큐를 사용하면 된다.

back의 경우는 구현된 메서드가 없으니 push 시 값을 저장했다가 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		Queue<Integer> q = new LinkedList<>();

		int x = 0;
		while (n-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String s = st.nextToken();

			switch (s) {
				case "push":
					x = Integer.parseInt(st.nextToken());
					q.add(x);
					break;
				case "pop":
					if (q.isEmpty())
						bw.write("-1\n");
					else
						bw.write(q.poll() + "\n");
					break;
				case "size":
					bw.write(q.size() + "\n");
					break;
				case "empty":
					if (q.isEmpty())
						bw.write("1\n");
					else
						bw.write("0\n");
					break;
				case "front":
					if (q.isEmpty())
						bw.write("-1\n");
					else
						bw.write(q.peek() + "\n");
					break;
				default:
					if (q.isEmpty())
						bw.write("-1\n");
					else
						bw.write(x + "\n");
			}
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

14916번: 거스름돈

# 그리디

https://www.acmicpc.net/problem/14916

풀이

2원과 5원짜리로 거스름돈을 줄 때 동전의 최소 개수를 구하는 문제이다.

거스름돈 액수가 5로 나누어 떨어질 때까지 2원으로 걸러주고 5로 나누어 떨어지면 모두 5원으로 거슬러 주면 된다.

계속 2원씩 거슬러 주었는데 1원이 남았다면 거슬러 줄 수 없는 액수이므로 -1을 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int ans = 0;
		while (n > 1) {
			if (n % 5 == 0) {
				ans += n / 5;
				break;
			}
			n -= 2;
			ans++;
		}

		if (n == 1)
			bw.write("-1");
		else
			bw.write(ans + "");

		bw.flush();
		bw.close();
	}
}

챌린저

문제

미로 탈출 명령어

# dfs # 백트래킹

https://school.programmers.co.kr/learn/courses/30/lessons/150365

풀이

미로에서 k 거리 만큼 이동하여 탈출 지점에 도착하는 경로를 구하는 문제이다.

dfs를 이용하면 거리가 k인 경로를 구할 수 있다.

경로는 사전 순으로 가장 앞서는 것이므로 방문 순서에 신경써야 한다.

처음에 단순한 dfs로 구현하였더니 시간초과가 발생했다.

백트래킹을 이용하여 dfs를 진행할 때 시작 지점과 탈출 지점과의 거리와 사용할 수 있는 거리 수를 비교하여 탈출할 수 없는 경로는 돌아온다.

코드

class Solution {
    String ans = "impossible";
    int[] dy = { 1, 0, 0, -1 };
    int[] dx = { 0, -1, 1, 0 };
    char[] d = { 'd', 'l', 'r', 'u' };
    boolean flag = false;
    
    void dfs(int y, int x, String s, int n, int m, int r, int c, int k) {
        if (!ans.equals("impossible"))
            return;
        
        int dis = Math.abs(r - y) + Math.abs(c - x);
        if (dis > k - s.length() || (k - s.length() - dis) % 2 == 1)
            return;
        
        if (s.length() == k) {
            if (r == y && c == x) {
            ans = s;
            flag = true;
            }
            return;
        }

        for (int i = 0; i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny <= 0 || nx <= 0 || ny > n || nx > m)
                continue;
            dfs(ny, nx, s + d[i], n, m, r, c, k);
        }
    }
    
    public String solution(int n, int m, int y, int x, int r, int c, int k) {
        dfs(y, x, "", n, m, r, c, k);
        
        return ans;
    }
}