[백준] 3085 사탕 게임 Java
상반기 공채가 얼마 남지 않은 시점이기에, 하반기 정말 가고 싶어하던 기업 최탈 이후 쉬고 있던 알고리즘을 다시 시작해보려 한다. 사실 2월부터 다시 한 번 새로운 부트캠프에 합류하게 되었는데, 학습량이 많은만큼 기술 블로그에 꾸준하게 기록하고 정리하는 작업이 필요하다고 생각해 기존 알고리즘 풀이 용도로 사용하던 velog 대신 tistory 블로그를 새로 만들었다. 곧 프로젝트를 시작하기 때문에 언제가 될 지 모르겠지만 시간이 되는대로 천천히 마이그레이션 할 예정이다.
서론이 길었는데, 오늘 푼 문제는 백준 3085번 사탕 게임 문제이다. 문제는 다음과 같다.
https://www.acmicpc.net/problem/3085
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입력
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ예제 출력
4
난이도는 백준 티어 기준 실버 2로, 기업 코딩테스트 1번 문제 혹은 그보다 쉬운 수준이라고 생각한다.
우선 이 문제의 포인트는 보드의 크기가 3 ≤ N ≤ 50 으로 제공된다는 것이다. 이 말은 O(N^2) 시간 복잡도로 배열 완전 탐색을 하면 최악의 경우 2500번 연산을 수행한다는 뜻이다. Java 언어 기준 보통 1초 == 1억 번의 연산으로 계산하면 되므로, 시간이 매우 넉넉하게 주어진 것을 볼 수 있다. 4중 for문을 돌더라도 시간 초과가 나지 않을 것이라고 예측할 수 있다.
그렇다면 브루트포스를 적용한 코드를 작성하는 것이 가능해진다. 내가 작성한 main 메서드 코드는 다음과 같다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
char[][] arr = new char[N][N];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine().toCharArray();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j < N - 1) swapAndFindMax(arr, i, j, i, j + 1);
if (i < N - 1) swapAndFindMax(arr, i, j, i + 1, j);
}
}
System.out.println(res);
}
배열 전체를 탐색하며 각 위치의 배열 값과 해당 위치의 오른쪽, 아래 방향에 해당하는 배열 값을 스왑하고 바뀐 배열에서 각 행, 열에 대해 가장 긴 연속 부분을 찾아주면 된다. 나는 이 연산을 swapAndFindMax 메서드로 작성했다.
private static void swapAndFindMax(char[][] arr, int x1, int y1, int x2, int y2) {
char temp = arr[x1][y1];
arr[x1][y1] = arr[x2][y2];
arr[x2][y2] = temp;
countMaxCandies(arr);
temp = arr[x1][y1];
arr[x1][y1] = arr[x2][y2];
arr[x2][y2] = temp;
}
가장 긴 연속 부분을 찾고 난 후에는 다음 연산을 위해 원래 배열 상태로 돌려주어야 한다. 그래서 다시 한번 스왑 연산을 진행하도록 했다. 이 과정에서 고민했던 것은 swap 연산과 관련한 시간 비용인데, 사실 스왑 자체는 O(1) 상수 시간이 소요되기 때문에 크게 걱정할 것은 아니기도 하고 swap 연산을 대체하려면 메모리 비용을 들이는 방법도 있지만 (실제 구현이 빡센 문제들에서는 이런 방법을 사용해서 시간 초과를 막기도 한다), 이 문제에서는 적합하지 않은 방식이라고 판단했다.
쓰면서 보니 swap 연산 작업과 관련한 것들은 메서드로 분리하는 편이 깔끔할 것 같지만, 우선은 리팩토링이 중요한 건 아니니 넘어가도록 한다.
private static void countMaxCandies(char[][] arr) {
for (int i = 0; i < N; i++) {
int maxR = 1;
int maxC = 1;
for (int j = 1; j < N; j++) {
if (arr[i][j - 1] == arr[i][j]) { // i행
maxR++;
} else {
res = Integer.max(res, maxR);
maxR = 1;
}
if (arr[j][i] == arr[j - 1][i]) { // i열
maxC++;
} else {
res = Integer.max(res, maxC);
maxC = 1;
}
}
res = Integer.max(res, maxR);
res = Integer.max(res, maxC);
}
}
실제 정답을 구하는데 가장 중요한 로직인 countMaxCandies를 살펴보면 꽤나 효율적인 탐색을 진행한다. i 라는 값을 기준으로 행과 열을 진행하며 진행 방향의 이전 값과 현재 값을 비교하면서, 같으면 count 값을 올려주고 다르면 정답 값인 res 값을 갱신한 후, 진행하는 방식이다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N, res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
char[][] arr = new char[N][N];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine().toCharArray();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j < N - 1) swapAndFindMax(arr, i, j, i, j + 1);
if (i < N - 1) swapAndFindMax(arr, i, j, i + 1, j);
}
}
System.out.println(res);
}
private static void swapAndFindMax(char[][] arr, int x1, int y1, int x2, int y2) {
char temp = arr[x1][y1];
arr[x1][y1] = arr[x2][y2];
arr[x2][y2] = temp;
countMaxCandies(arr);
temp = arr[x1][y1];
arr[x1][y1] = arr[x2][y2];
arr[x2][y2] = temp;
}
private static void countMaxCandies(char[][] arr) {
for (int i = 0; i < N; i++) {
int maxR = 1;
int maxC = 1;
for (int j = 1; j < N; j++) {
if (arr[i][j - 1] == arr[i][j]) { // i행
maxR++;
} else {
res = Integer.max(res, maxR);
maxR = 1;
}
if (arr[j][i] == arr[j - 1][i]) { // i열
maxC++;
} else {
res = Integer.max(res, maxC);
maxC = 1;
}
}
res = Integer.max(res, maxR);
res = Integer.max(res, maxC);
}
}
}
프로그래머스에서 코테 보고 뭐하고,, 하다가 오랜만에 백준 플랫폼에서 알고리즘 문제를 풀었는데 이렇게 기록까지 하니까 나름 재밌는 것 같다 (?) 1일 1알고리즘 굉장히 힘든 것이지만, 이번 기회를 통해 더 가파르게 성장할 수 있을 것이라고 생각한다.