da9dac

문제

접근 방식

스택을 활용해서 풀 수 있는 문제다.

주어진 입력을 순회하면서 크게 두 가지 경우로 나누어 처리해 주면 되는데

바로 현재 입력값이 now와 같은지 다른지이다.

now는 1부터 시작하는 변수를 선언하여 해당 순서가

간식을 받을 때마다 1씩 증가시켜 주면서

다음 순서를 확인할 수 있게 해주는 변수다.

만약 현재 사람이 간식을 받을 순서가 맞다면 스택에 넣지 않고

그대로 now를 1 증가시켜 준 뒤에 남아있는 스택을 확인하면서

now와 일치하는 값이 있다면 뽑아주고 그렇지 않다면 넘어간다.

반대로 현재 사람이 받을 순서가 아니라면 스택에 넣어주기만 하면 된다.

예를 들어 3 2 1 순서로 줄을 서 있다면 3과 2는 스택에 들어가고

1이 간식을 받은 후에 2와 3의 순서대로 꺼내면 정렬된 순서를 만들 수 있다.

풀이

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Stack<Integer> s = new Stack<>();
        
        int now = 1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] == now) {
                now++;
                while (!s.isEmpty()) {
                    if (s.peek() == now) {
                        s.pop();
                        now++;
                    } else {
                        break;
                    }
                }
            } else {
                s.push(arr[i]);
            }
        }
        
        System.out.println(s.isEmpty() ? "Nice" : "Sad");
    }
}

문제

접근 방식

HashSet을 사용해서 처음 키워드를 저장한 후에

글을 작성할 때마다 삭제해 주고 사이즈를 출력해주기만 하면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		Set<String> set = new HashSet<>();

		while (n-- > 0) {
			set.add(br.readLine());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine(), ",");

			while(st.hasMoreTokens()) {
				set.remove(st.nextToken());
			}
			
			sb.append(set.size()).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

각 확장자인 파일의 개수를 Map을 이용하여 카운팅하여

확장자명의 사전 순으로 개수와 같이 출력해주면 된다.

키를 기준으로 정렬된 상태를 유지하면 되기 때문에

TreeMap을 사용하면 효율적으로 풀 수 있다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		String[] name;

		TreeMap<String, Integer> map = new TreeMap<>();

		while (n-- > 0) {
			name = br.readLine().split("\\.");
			map.put(name[1], map.getOrDefault(name[1], 0) + 1);
		}

		for (String key : map.keySet()) {
			sb.append(key).append(" ").append(map.get(key)).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

사전순으로 출력하기 위해 키값을 기준으로 정렬할 수 있는 TreeMap을 사용하여

각 나무가 입력으로 들어올 때마다 해당 키의 값을 1씩 증가시켜 주면 된다.

이때 입력을 한 줄씩 받을 때마다 카운트를 하여 총 입력수를 기록해 두고

이를 나중에 출력 시에 사용해 확률을 계산해 주면 된다.

정확히 소수점 넷째 자리까지만 출력해야 하고 적거나 많으면 틀리기 때문에

자바는 String.format을 이용해 자릿수를 맞춰서 출력해 주면 된다.

풀이

class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int total = 0;
		TreeMap<String, Integer> trees = new TreeMap<>();

		String tree;

		for (int i = 0; i < 29; i++) {
			tree = br.readLine();
			trees.put(tree, trees.getOrDefault(tree, 0) + 1);
			total++;
		}

		for (String key : trees.keySet()) {
			int cnt = trees.get(key);

			double per = ((double) cnt / total) * 100;

			sb.append(key).append(" ").append(String.format("%.4f", per)).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

구현해야 할 기능은 크게 세 가지로

첫 번째는 같은 뿌요가 4개 이상 이어진 지 확인하고 터트리는 것이고,

두 번째는 남은 뿌요들을 빈 공간으로 내려주는 기능이고,

마지막은 4개 이상이 이어져 터진 경우 위 과정을 재귀호출을 통해 반복하는 것이다.

우선 첫 번째 기능은 필드를 순회하며

뿌요를 발견할시 BFS로 같은 뿌요인 경우만 탐색을 하며

기록해 두었다 4개 이상인 경우에는

기록해 둔 좌표의 뿌요들을 빈 공간으로 바꿔준다.

다음으로 두 번째 기능은 필드를 열을 기준으로 행을 거꾸로 순회하며

뿌요 발견 시 가장 밑 인덱스부터 채워주면 된다.

마지막 기능은 첫 번째 기능에서 터진 경우 폭발 여부를 기록해 두었다가

폭발을 했다면 재귀호출을 진행하고 그렇지 않다면 넘어가면 된다.

풀이

class Main {
    
	static int max = 0;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] fields = new char[12][6];
	static boolean[][] isVisited = new boolean[12][6];
	static Queue<Pair> q = new ArrayDeque<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int i = 0; i < 12; i++) {
			fields[i] = br.readLine().toCharArray();
		}

		solve();

		System.out.println(max);
	}

	static void solve() {
		boolean boom = false;

		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (isVisited[i][j]) continue;
				if (fields[i][j] != '.') {
					boolean b = bfs(i, j, fields[i][j]);
					if (b) boom = true;
				}
			}
		}

		if (boom) {
			max++;
			down();
			solve();
		}
	}

	static void down() {
		for (int start = 0; start < 6; start++) {
			int idx = 11;

			for (int i = 11; i >= 0; i--) {
				isVisited[i][start] = false;
				if (fields[i][start] != '.') {
					char tmp = fields[i][start];
					fields[i][start] = '.';
					fields[idx--][start] = tmp;
				}
			}
		}
	}

	static boolean bfs(int x, int y, char c) {
		Pair curP = new Pair(x, y);
		q.offer(curP);
		isVisited[x][y] = true;

		ArrayList<Pair> list = new ArrayList<>();
		list.add(curP);

		while (!q.isEmpty()) {
			Pair cur = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;
				if (fields[nx][ny] != c || isVisited[nx][ny]) continue;

				isVisited[nx][ny] = true;
				Pair next = new Pair(nx, ny);
				list.add(next);
				q.offer(next);
			}
		}

		if(list.size() > 3) {
			for (Pair p : list) fields[p.x][p.y] = '.';
			return true;
		}

		return false;
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

M개 이상 13개 이하의 치킨집이 있을 때, M개의 치킨집을 골라

가장 적은 치킨 거리를 구해야 한다.

입력만 보면 그래프 문제처럼 보이기도 하지만 그래프를 쓸 일은 없다.

리스트 두 개를 만들어 입력을 받으면서 집과 치킨집의 좌표를 담아준 후에

두 리스트를 반복문을 돌면서 각 집과 치킨집들의 거리를 모두 구해준다.

그 후 백트래킹으로 M개의 치킨집을 고른 후에

선택된 치킨집들과 집들의 치킨 거리를 구한 후

최소 치킨 거리를 비교해 주며 갱신하면 된다.

순서가 다른 중복된 조합까지 반복적으로 계산하면

시간초과가 발생하는 문제이기 때문에

중복된 조합을 피해서 백트래킹을 해줘야 한다.

풀이

class Main {
    
    static int n, m, h, c, answer = Integer.MAX_VALUE;
	static ArrayList<Pair> home = new ArrayList<>();
	static ArrayList<Pair> chicken = new ArrayList<>();
	static int[] selects;
	static int[][] distance;
	static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());

				if (x == 1) home.add(new Pair(i, j));
				if (x == 2) chicken.add(new Pair(i, j));
			}
		}

		c = chicken.size();
		h = home.size();
		isUsed = new boolean[c];
		selects = new int[m];

		calculateDistance();
		solve(0, 0);

		System.out.println(answer);
	}

	static void calculateDistance() {
		distance = new int[h][c];

		for (int i = 0; i < h; i++) {
			Pair cur = home.get(i);
			for (int j = 0; j < c; j++) {
				Pair tar = chicken.get(j);
				distance[i][j] = Math.abs(cur.x - tar.x) + Math.abs(cur.y - tar.y);
			}
		}
	}

	static void solve(int start, int size) {
		if (size == m) {
			calculateSum();
			return;
		}

		for (int i = start; i < c; i++) {
			if (isUsed[i]) continue;
			isUsed[i] = true;
			selects[size] = i;
			solve(i + 1, size + 1);
			isUsed[i] = false;
		}
	}

	static void calculateSum() {
		int sum = 0;

		for (int i = 0; i < h; i++) {
			int min = Integer.MAX_VALUE;

			for (int j = 0; j < m; j++) {
				min = Math.min(min, distance[i][selects[j]]);
			}

			sum += min;
		}

		answer = Math.min(answer, sum);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

이런 BFS 문제는 물의 입장에서 먼저 BFS를 진행하며

시간을 기록해둔 후에 고슴도치의 입장에서 BFS를 진행해

물보다 먼저 도착할 수 있는 곳으로만 탐색을 진행해주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");

		int r = Integer.parseInt(input[0]);
		int c = Integer.parseInt(input[1]);

		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		char[][] map = new char[r][c];

		Queue<Pair> wq = new ArrayDeque<>();
		Queue<Pair> hq = new ArrayDeque<>();

		int[][] water = new int[r][c];
		int[][] hog = new int[r][c];

		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				water[i][j] = -1;
				hog[i][j] = -1;

				map[i][j] = s.charAt(j);

				if (map[i][j] == '*') {
					wq.offer(new Pair(i, j, 0));
					water[i][j] = 0;
				}

				if (map[i][j] == 'S') {
					hq.offer(new Pair(i, j, 0));
					hog[i][j] = 0;
				}
			}
		}

		while (!wq.isEmpty()) {
			Pair cur = wq.poll();

			for (int dir = 0; dir < 4; dir++) {
				int x = cur.x + dx[dir];
				int y = cur.y + dy[dir];

				if (x < 0 || x >= r || y < 0 || y >= c) continue;
				if (map[x][y] == 'X' || map[x][y] == 'D' || water[x][y] != -1) continue;

				water[x][y] = cur.move + 1;
				wq.offer(new Pair(x, y, cur.move + 1));
			}
		}

		while (!hq.isEmpty()) {
			Pair cur = hq.poll();
			int next = cur.move + 1;

			for (int dir = 0; dir < 4; dir++) {
				int x = cur.x + dx[dir];
				int y = cur.y + dy[dir];

				if (x < 0 || x >= r || y < 0 || y >= c) continue;
				if (map[x][y] == 'X' || map[x][y] == '*' || hog[x][y] != -1) continue;
				if (map[x][y] == 'D') {
					System.out.println(next);
					return;
				}
				if (water[x][y] != -1 && water[x][y] <= next) continue;

				hog[x][y] = next;
				hq.offer(new Pair(x, y, next));
			}
		}

		System.out.println("KAKTUS");
	}

	static class Pair {
		int x, y, move;

		public Pair(int x, int y, int move) {
			this.x = x;
			this.y = y;
			this.move = move;
		}
	}
}

문제

접근 방식

정말 있는 그대로 구현하기만 하면 되서 티어에 비해 쉬운 문제다.

많이들 실수하는 부분이 전역 변수 관리나 객체의 얕은 복사인데

이 부분만 조심하면 풀이에 어려움은 없다.

움직이고자 하는 방향의 끝 인덱스에서부터 거꾸로 탐색해주면서

수가 같다면 합쳐주면 되는데 0인 경우를 조심해야 한다.

현재 바라보고 있는 곳이 0이라면 어떤 값이든 들어올 수 있으니

처음 마주치는 값을 옮겨주고 그 후에 같은 값이 있는지 또 확인해준다.

반대로 현재 바라보고 있는 곳이 0이 아니라면 같은 숫자만

합칠 수 있으니 같은 값이 있는지 한 번만 확인해주면 된다.

만약 수가 같지 않다면 멈춘다.

풀이

public class Main {

	static int n, max = 0;
	static int[] move = new int[5];
	static int[][] board, newBoard;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		board = new int[n][n];
		newBoard = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				newBoard[i][j] = board[i][j];
			}
		}

		solve(0);

		System.out.println(max);
	}

	static void solve(int cnt) {
		if (cnt == 5) {
			for (int i = 0; i < 5; i++) {
				move(move[i]);
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					max = Math.max(max, board[i][j]);
				}
			}
			back();
			return;
		}

		for (int dir = 0; dir < 4; dir++) {
			move[cnt] = dir;
			solve(cnt + 1);
		}
	}

	static void move(int dir) {
		switch(dir) {
			case 0: {
				right();
				break;
			}
			case 1: {
				left();
				break;
			}
			case 2: {
				up();
				break;
			}
			default: {
				down();
				break;
			}
		}
	}

	static void right() {
		for (int i = 0; i < n; i++) { 
			for (int j = n - 1; j >= 0; j--) { 
				for (int k = j - 1; k >= 0; k--) { 
					if (board[i][k] != 0) {
						if (board[i][j] == 0) {
							board[i][j] = board[i][k];
							board[i][k] = 0;
							continue;
						}

						if (board[i][j] == board[i][k]) {
							board[i][j] *= 2;
							board[i][k] = 0;
						}

						break;
					}
				}
			}
		}
	}

	static void left() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if (board[i][k] != 0) {
						if (board[i][j] == 0) {
							board[i][j] = board[i][k];
							board[i][k] = 0;
							continue;
						}

						if (board[i][j] == board[i][k]) {
							board[i][j] *= 2;
							board[i][k] = 0;
						}
						break;
					}
				}
			}
		}
	}

	static void up() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if (board[k][i] != 0) {
						if (board[j][i] == 0) {
							board[j][i] = board[k][i];
							board[k][i] = 0;
							continue;
						}

						if (board[j][i] == board[k][i]) {
							board[j][i] *= 2;
							board[k][i] = 0;
						}
						break;
					}
				}
			}
		}
	}

	static void down() {
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 0; j--) {
				for (int k = j - 1; k >= 0; k--) {
					if (board[k][i] != 0) {
						if (board[j][i] == 0) {
							board[j][i] = board[k][i];
							board[k][i] = 0;
							continue;
						}

						if (board[j][i] == board[k][i]) {
							board[j][i] *= 2;
							board[k][i] = 0;
						}
						break;
					}
				}
			}
		}
	}

	static void back() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				board[i][j] = newBoard[i][j];
			}
		}
	}
}