내일은 알고리즘

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 

시뮬레이션의 정수를 담은 문제입니다.

주어진 문제의 조건과 순서를 따라 잘 구현하면 되지만 잘 구현하는것이 어렵습니다.

코드의 가독성을 높이기 위해 여러 단계를 나누어 함수로 구현하고

실행 시간을 줄이기 위해 재귀함수를 이용해서 이전 상태를 기억해 거기서부터 다시 탐색합니다.

상태를 기억할때는 Map이 2차원 배열임을 감안해 깊은 복사를 위해 copy() 함수를 따로 만들었습니다.

Java언어에서 N차원 배열로 모든 배열을 순회하며 복사해도 되지만 clone() 메소드가 Array에 존재해 활용했습니다.

모든 경우를 탐색해야하기 때문에 효율적인 코드를 짜는게 중요할 것 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q5656_SWEA_벽돌깨기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int answer, N, W, H;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;

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

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			map = new int[H][W];
			for (int h = 0; h < H; h++) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; w++) {
					map[h][w] = Integer.parseInt(st.nextToken());
				}
			}

			dfs(0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int count) {
		if (count == N) {
			answer = Math.min(answer, countBlock(map));
			return;
		}
		int[][] save = new int[H][W];
		for (int w = 0; w < W; w++) {		
			copy(map, save);				
			shoot(w);
			dfs(count + 1);
			copy(save, map);

		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < H && 0 <= y && y < W) {
			return true;
		}

		return false;
	}

	static void copy(int[][] from, int[][] to) {
		for (int h = 0; h < H; h++) {
			to[h] = from[h].clone(); 
		}
	}

	static int countBlock(int[][] result) {
		int count = 0;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				if (result[h][w] != 0) {
					count++;
				}
			}
		}
		return count;
	}

	static void shoot(int w) {			
		for (int h = 0; h < H; h++) {	
			if (map[h][w] != 0) {		
				boom(h, w);
				return;
			}
		}
		return;
	}

	static void boom(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y, map[x][y]-1 });
		map[x][y] = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int range = now[2];

			for (int i = 0; i < 4; i++) {
				int nX = now[0];
				int nY = now[1];
				for (int r = 0; r < range; r++) {
					nX += delta[i][0];
					nY += delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != 0) {
						queue.offer(new int[] { nX, nY, map[nX][nY]-1 });
						map[nX][nY] = 0;
					}
				}
			}
		}

		gravity();
	}

	static void gravity() {
		Queue<Integer> queue;

		for (int w = 0; w < W; ++w) {   
			queue = new LinkedList<>();	

			for (int h = H - 1; h >= 0; --h) {
				if (map[h][w] > 0) {
					queue.offer(map[h][w]);
				}
			}

			for (int h = H - 1; h >= 0; --h) {
				if (!queue.isEmpty()) {
					map[h][w] = queue.poll();
				} else {
					map[h][w] = 0;
				}
			}
		}

	}
}

https://programmers.co.kr/learn/courses/30/lessons/1831

원래는 이분탐색의 Lv.4 문제를 풀려고 했는데, 저도 구현하다가 애매한 부분이 있어 확인해보니 문제에 오류가 있다는 얘기가 많아서 다른 Lv.4 문제를 가져왔습니다.

연산후의 값이 주어지고 그 값이 연산을 통해 만들 수 있는가를 검증하거나 가능한 경우의 수를 찾는 문제는 주어진 값부터 연산을 거꾸로 짚어가며 풀이하면 쉽고 빠르게 풀리는 경우가 많습니다. 이번 문제도 그런 유형이었는데요.

처음엔 3단고음이라는 연산이 중첩되어 계산되는 것을 stack처럼 중첩의 갯수를 카운팅해서 풀이하려고 했는데 구현 난이도가 어마어마 했을 뿐만 아니라 통과도 실패했습니다.

QnA의 도움을 얻어, 이 3단고음이라는 연산은 뒤에서부터 읽어들어갈때, +의 갯수가 2개보다 큰 경우 *하나와 묶어서 사라질 수 있다는걸 알았습니다. 즉, 거꾸로 3단고음 연산이 동작할때 1을 뺄때 +의 갯수를 늘려주고 (+를 역산), +의 갯수가 두개이상이면 3으로 나눠지면서 두개와 소멸하고, 초기값인 1에 도달했을때 +와 *가 모두 상쇄되었으면 카운트를 1 늘려주었습니다.

재귀호출 중간에 ++의 갯수만큼 *의 역산이 이루어져야 하는데 불가능한 경우 가지치기 했습니다.

해당 아이디어를 바탕으로 dfs를 응용한 재귀문을 작성해 테스트케이스를 통과했습니다.

테스트케이스가 하나뿐이라 예외에 걸릴지는 잘 모르겠네요.

public class q1831_Programmers_4단고음 {
	static int answer;

	public static void main(String[] args) {

//		int[] input = { 15, 24, 41 };
		int[] input = { 15, 24, 41, 2147483647 };

		for (int i = 0; i < input.length; i++) {
			System.out.println(solution(input[i]));
		}
	}

	private static int solution(int n) {
		answer = 0;

		dfs(n, 0);

		return answer;
	}

	private static void dfs(int now, int depth) {
		//System.out.println("now:" + now + "   depth:" + depth);
		
		if (now == 1 && depth == 0) {
			answer++;
			return;
		}
		
		if (now < Math.pow(3, (depth / 2))) {
			return;
		}

		dfs(now - 1, depth + 1);
		
		if (depth >= 2 && now >= 3 && now % 3 == 0) {
			dfs(now / 3, depth - 2);
		}

	}

}

https://programmers.co.kr/learn/courses/30/lessons/64064

Lv.3치고 간단한 조합 응용문제입니다.

전체 사용자 리스트 Y개에서 불량 사용자 리스트에 대하여 대입이 가능한 X개를 뽑아 만들면 됩니다. (yCx)

조합과 다른 점은 아이디를 넣을 수 있는 경우가 제한되어 있어 사용자 Y가 아닌 불량 사용자 X에 대해 찾는다는 점입니다. 

모든 경우(Y x X)에 대하여 가능 여부를 미리 계산한 뒤, 재귀를 통해 불량 사용자 리스트마다 사용자를 대입하고 X개를 뽑았을 때 저장했습니다.

입력 데이터의 최대 사이즈가 8개이기 때문에 중복체크는 bitmask를 이용해 간단히 구현했습니다. 

가능한 리스트 최대 길이가 64이기 때문에 HashMap을 이용해도 구현이 가능할 것 같습니다. 

package programmers;

public class q64064_Programmers_불량사용자 {

	public static void main(String[] args) {
		String[] user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
		String[] banned_id = { "fr*d*", "*rodo", "******", "******" };
		System.out.println(solution(user_id, banned_id));
	}

	private static int solution(String[] user_id, String[] banned_id) {
		int answer = 0;
		boolean[] bitmask = new boolean[1 << user_id.length];

		boolean[][] possible = new boolean[user_id.length][banned_id.length];

		for (int u = 0; u < user_id.length; u++) {
			for (int b = 0; b < banned_id.length; b++) {
				boolean flag = true;

				if (user_id[u].length() != banned_id[b].length()) {
					flag = false;
				} else {
					for (int i = 0; i < user_id[u].length(); i++) {
						if (banned_id[b].charAt(i) == '*')
							continue;
						else if (user_id[u].charAt(i) != banned_id[b].charAt(i)) {
							flag = false;
							break;
						}
					}
				}

				possible[u][b] = flag;
			}
		}

		recur(possible, bitmask, 0, 0);

		for (int i = 0; i < bitmask.length; i++) {
			if (bitmask[i])
				answer++;
		}
		return answer;
	}

	private static void recur(boolean[][] possible, boolean[] bitmask, int mask, int idx) {
		if (idx == possible[0].length) {
			bitmask[mask] = true;
			return;
		}

		for (int u = 0; u < possible.length; u++) {
			if (possible[u][idx] && (mask & (1 << u)) == 0) {
				recur(possible, bitmask, mask | (1 << u), idx + 1);
			}
		}
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

https://nodingco.tistory.com/30 의 시리즈 문제입니다.

1. 이해 (5분) - 1분

A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다. 

하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다. 

앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.

대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.

2. 계획 (5분) - 3분

재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.

대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.

(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)

그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.

3. 검증 (5분) - 1분

검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.

4. 풀이 (30분) - 17분

재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.

5. 채점, 디버깅 

다행히 이번에도 한 번에 통과했습니다. 감사합니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	static char[] S;

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

		S = br.readLine().toCharArray();
		char[] T = br.readLine().toCharArray();

		N = S.length;

		makeS(T, T.length);

		if (N == 100) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	static void makeS(char[] T, int l) {
		if (l < N) {
			return;
		}
		if (l == N) {
			N = (checkS(T)) ? 100 : N;
			return;
		}

		if (T[l - 1] == 'A') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[i];
			}
			makeS(newT, l - 1);
		}

		if (T[0] == 'B') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[l - 1 - i];
			}
			makeS(newT, l - 1);
		}
	}

	static boolean checkS(char[] T) {
		for (int n = 0; n < N; n++) {
			if (T[n] != S[n]) {
				return false;
			}
		}
		return true;
	}
}