이번 문제는 백준의 골드 5 문제 사다리타기 문제이다.
문제를 차근차근 한 번 읽어보도록 하자.
A부터 순서대로 사람 수대로 알파벳이 배정된다고 한다.
이후 사다리타기를 통해 모든 사람이 내려갔을 때 결과가 주어진다.
또한 사다리 중간의 한 줄이 반드시 비워진 채로 주어지게 되는데,
이 때 주어진 결과를 만들 수 있는 사다리를 판단해서 출력한다.
어떤 경우에도 만들 수 없다면, XXXXXX...를 K-1개 출력한다.
문제를 어떻게 풀어야 할까?
완전 탐색
처음엔 모든 경우의 수를 조합으로 만들어 볼까 했다.
하지만 당연하게도 시간초과가 발생했다.
최대 26개의 알파벳이 주어질 수 있으므로,
모든 경우의 수는 최악의 경우 2^26개나 된다.
거기다 가능한 경우의 수인지 시뮬레이션까지 해야한다.
이는 시간초과가 발생할 수 밖에 없는 경우의 수라고 생각한다.
이 방식은 폐지하도록 하자.
아이디어 구현
계속 생각을 해보다, 이 문제는 결국 구현 문제임을 깨달았다.
그 말인 즉슨, 해당 문제를 풀 수 있는 아이디어가 필요하다는 말이다.
결국 우리가 구해야 하는 것은 ????로 가득찬 부분이다.
그럼 어차피 해당 열 앞뒤로는 문자열이 정해져 있을 것이다.
사다리를 통해서 미리 해당 열 직전, 직후까지 문자열들을 보내보자!
아래와 같이 함수를 구현했다.
원래 순서를 사다리 아래로 내려보내고, 결과를 위로 올려보낸다.
void send_down_origin() {
for (int i = 0; i < target_row; i++) {
for (int j = 0; j < col - 1; j++) {
if (ladders[i][j] == '-')
swap(origin[j], origin[j + 1]);
}
}
}
void send_up_target() {
for (int i = row - 1; i > target_row; i--) {
for (int j = 0; j < col - 1; j++) {
if (ladders[i][j] == '-')
swap(target[j], target[j + 1]);
}
}
}이제 대상 사다리에 따라 내려보낸 문자열을 만들 수 있는지가 관건이다.
어떤 식으로 비교를 해주어야 할까?
예시로 CADBEGFHIJ CABDGEFHJI 두 문자열이 위아래로 있다고 생각해보자.
CA와 같이 그대로 문자열이 내려가는 경우엔, *을 넣어도 된다.
즉, 그냥 내려보내도 된다는 말이다.
그럼 DB BD와 같이 교차하는 경우에는 어떨까?
이럴 땐 -을 통해서 둘을 교차시켜주면 만들 수 있는 문자열이 된다.
DC BD와 같이 이상하게 꼬여있는 경우에는 어떨까?
이 경우에는 위의 두 경우에 해당하지 않아, 만들 수 없는 문자열이다.
즉, 즉시 XXXX..를 반환하면 된다.
위의 논리를 코드로 구현하면 아래와 같다.
string compare_between() {
string answer = "";
for (int i = 0; i < col - 1; i++) {
if (origin[i] == target[i])
answer += '*';
// origin과 target이 동일하다면 그냥 내려보내도 됨
else if (origin[i] == target[i + 1] && origin[i + 1] == target[i]) {
swap(origin[i], origin[i + 1]);
answer += '-';
// origin과 target이 서로 교차된 알파벳이라면
// 둘의 자리를 바꾸면 만들 수 있는 문자열이다.
}
else {
answer = "";
for (int j = 0; j < col - 1; j++)
answer += 'x';
return answer;
// 두 경우에 모두 걸리지 않으면 만들 수 없는 문자열.
// 바로 결과를 반환해도 된다.
}
}
return answer;
}아직 구현 아이디어를 떠올리는 힘이 부족한 것 같다.
조금 더 구현 문제를 풀어 생각하는 힘을 길러보자.