BOJ - RBY팡! 5577번 (JAVA)

❓ 문제 - 백준 RBY팡! 5577번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/5577)

5577번: RBY팡!

 

 

 

📝 문제해결법

1. 문제 해석

• N개의 공이 있을 때 하나의 공 색을 다른 색으로 바꿀 수 있다.
• 공이 같은 색으로 연속으로 4개 이상 이어질 때 팡!하고 터지고, 그 후 4개 이상 또 연속으로 공이 있으면 계속해서 공이 터진다. 그러다가 마지막까지 터지지 않고 남은 공의 갯수가 있을 때 그 공의 최소 갯수를 구하여라.

 

2. 해결 방법

• 위에 있는 공부터 차례대로 공의 색깔을 다른 색으로 바꾼 후, play 함수로 연속해서 터질 게 있으면 터짐 처리하고 남은 공의 갯수를 구해 최솟값을 계속해서 갱신한다.
• play() 함수 내에서는 투포인터인 start와 end로 같은 색의 공이 연속적으로 4개 이상 있는지 체크하고, 만약 연속적으로 공이 4개 이상 있다면 visited 배열을 true로 변경시켜준다.
• start, end=start+1로 두고, 만약 start지점에 공이 터지지 않은 상태(false)일때 b[start]의 컬러와 b[end] 컬러가 같거나 visited가 true로 해당 지역은 터졌으므로 다음 인덱스를 살펴야하므로  end = end +1 지점으로 계속해서 탐색할 수 있도록 한다. 계속 탐색하다가 end가 b[start]의 color와 다른 지점이 있다면 break해서 빠져나오고 연속된 색의 수(cnt)가 4개 이상이라면 터짐처리 해주고, 다시 start=0인 지점부터 다시 공이 연속해서 터지는지 탐색을 시작한다.
• 만약 4개 이상 연속된 컬러가 아니라면, start는 start+1부터 다시 할 필요 없이 end지점부터 다시 공이 연속되는지를 확인해주면 된다.
• 만약 start가 0인 지점부터 끝까지 탐색했지만 투포인터를 활용해서 팡!하고 터진 곳이 없다면 탐색을 종료하고, visited 배열로 현재 존재하는 공(false)만의 갯수를 세고 최솟값 갱신처리를 한다.

 

3. 삽질 & 느낀점

• 처음에 메모리 초과가 나서 while문 부분을 잘못 해서 무한 루프문으로 빠져 메모리 초과가 나는지 확인하였다.
• 하지만 로직 곳곳에 출력값을 넣어 디버깅을 해보았지만.. 딱히 무한 루프문에 빠질 만한 곳을 찾지 못했다.
• 하지만 다시 코드를 처음부터 살펴보니, ball을 clone해서 b라는 배열에 공의 색을 바꿔주고, play 함수에서 공이 터짐처리를 0으로 바꿔줘서 최대 10000*2번 만큼 10000의 배열이 생성되었고 이는 메모리 초과를 당연히 유발할 것이다.
• 따라서 ball 배열은 처음에 색을 바꿔주고 play함수 호출 후에 다시 원래 색으로 복귀 처리했다. 그리고 play 함수 내에서는 공의 터짐 처리를 visited라는 boolean 배열을 통해 관리를 해주었더니 통과가 되었다..!
• 알고리즘을 풀 때 사실 시간초과만 고려했고 메모리 초과가 나면 무한 루프문이나 무한 재귀만 고려 했는데 이런 공간복잡도도 잘 고려해서 문제를 접근해야겠다고 느꼈다.

 

 

 

💻 소스코드 

// BOJ - RBY!팡(5577번)
// 구현 + 투포인터

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

public class Main_5577 {
    public static int n, min_value;
    public static int[] ball;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        ball = new int[n];
        for(int i=0;i<n;i++){
            ball[i] = Integer.parseInt(br.readLine());
        }
        min_value = n;

        for(int i=0;i<n;i++){
            for(int j=1;j<=3;j++){
                if(ball[i] == j) continue;
                int origin = ball[i];
                ball[i] = j;
                play(ball);
                ball[i] = origin;
            }
        }

        System.out.println(min_value);


    }

    public static void play(int[] b){
        boolean[] visited = new boolean[n];

       while (true){
            boolean pang = false;
            int start = 0;
            outer :while (start < n) {
                if (visited[start]) {
                    start++;
                    continue;
                }

                int end = start + 1;
                int cnt = 1;
                int color = b[start];
                while (end < n) {
                    if (visited[end]) {
                        end += 1;
                        continue;
                    }
                    if (b[end] == color) {
                        end += 1;
                        cnt++;
                    } else {
                        break;
                    }
                }

                if(cnt >= 4){
                    pang = true;
                    for(int i=start;i<end;i++){
                        visited[i] = true;
                    }
                    break outer;
                } else {
                    start = end;
                    continue;
                }
            }

            if(!pang) break;

        }

        int cnt = 0;
        for(int i=0;i<n;i++){
            if(!visited[i]) cnt++;
        }
        min_value = Math.min(min_value, cnt);
    }
}