이번에 풀어본 문제는
백준 2469번 사다리 타기 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int K,N;
static char [][] map;
static int blankLine;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K = Integer.parseInt(br.readLine());
N = Integer.parseInt(br.readLine());
// 최초 순서
char [] origin = new char[K];
for (int i = 0; i < K; i++) {
origin[i] = (char)('A' + i);
}
// 결과 순서
char [] result = br.readLine().toCharArray();
map = new char[N][K - 1];
for (int i = 0; i < N; i++) {
String input = br.readLine();
//?로 채워진 blank 찾아두기
if (input.charAt(0) == '?') {
blankLine = i;
continue;
}
map[i] = input.toCharArray();
}
// 최초 알파벳 순서로 blankLine 까지 사다리 진행
for (int i = 0; i < blankLine; i++) {
for (int j = 0; j < K - 1; j++) {
// 가로 막대를 만났을 때 swap
if (map[i][j] == '-') {
char tmpChar = origin[j];
origin[j] = origin[j + 1];
origin[j + 1] = tmpChar;
}
}
}
//최종 결과도 반대로 blankLine 까지 사다리 진행
for (int i = N - 1; i > blankLine; i--) {
for (int j = 0; j < K - 1; j++) {
if (map[i][j] == '-') {
char tmpChar = result[j];
result[j] = result[j + 1];
result[j + 1] = tmpChar;
}
}
}
//최종 두 결과를 비교하여 결과 문자열 완성시킴
StringBuilder sb = new StringBuilder();
for (int i = 0; i < K - 1; i++) {
// 서로 같으면 그대로 내려가야 하므로 *
if (origin[i] == result[i]) {
sb.append("*");
}
// 인덱스 하나 차이라면 가로막대를 놔야하므로 -
else if (origin[i] == result[i + 1]) {
sb.append("-");
// 그대로 진행하면 다음 반복에서 또 가로막대를 놓기 때문에 swap
char tmpChar = origin[i];
origin[i] = origin[i + 1];
origin[i + 1] = tmpChar;
}
// 이외 경우는 2칸 이상 차이나므로 x로 채운 후 break
else {
sb = new StringBuilder();
sb.append("x".repeat(K - 1));
break;
}
}
System.out.print(sb);
}
}
우리가 흔히 아는 사다리 게임입니다.
이 문제에서는 사다리 게임의 결과를 미리 입력받습니다.
이후 ''은 세로 막대, '-'는 가로 막대를 의미하는 입력이 주어집니다.
하지만 그 중 한 줄은 '?'로 채워진 빈칸 입니다.
알파벳 순서로 게임을 시작하여, 입력으로 주어진 게임의 결괏값과 동일한 결과를 도출해 낼 수 있도록 '?'로 채워진 빈칸을 완성하여 출력해봅시다.
빈 칸을 목적지로 하여 위아래(위 = 시작순서, 아래 = 입력된 결괏값)에서 각자 사다리 게임을 시작한 후 두 값을 비교하면, 빈칸이 어떤 막대로 이루어져 있는지 알아낼 수 있습니다.
세로 막대는 그대로 내려가고, 가로 막대를 만났을때는 사실상 우측에 있는 알파벳과 자리를 변경하면 되기 때문에, 이 방법으로 사다리 게임을 진행한 후 결과 문자열을 비교해줍니다.
두 값이 같다면 , 다르다면 -로 결과 문자열을 채워 출력하면 해결할 수 있습니다.
나올 수 있는 모든 경우의 수를 조합하여 해결하려 했는데, 풀다보니 경우의 수가 너무 방대하고 뭔가 해답이 아닌 것 같아서 다른 풀이를 참고했습니다. 정말 머리가 좋은 풀이 인 것 같네요...