[백준] 30023번 '전구 상태 바꾸기' - Java

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

---

문제

---

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	final static int MAX = 900_000;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		char[] lights = br.readLine().toCharArray();
		
		int firstLight = lightsOn(n, lights);
		change(lights, 1);
		int secondLight = lightsOn(n, lights) + 1;
		change(lights, 1);
		int thirdLigth = lightsOn(n, lights) + 2;
		int minLights = Math.min(firstLight, Math.min(secondLight, thirdLigth));
		int ans = (minLights == MAX) ? -1:minLights;
		
		System.out.println(ans);
	}
    
    public static int lightsOn(int n, char[] lights) {
    	char[] lightsCopy = Arrays.copyOf(lights, n);
    	int cnt = 0;
    	
    	for(int i=2; i<n-1; i++) {
    		while(lightsCopy[0] != lightsCopy[i-1]) {
    			change(lightsCopy, i);
    			cnt++;
    		}
    	}
    	
    	for(int i=1; i<n; i++) {
    		if(lightsCopy[0] != lightsCopy[i]) {
    			cnt = MAX;
    			break;
    		}
    	}
    	
    	return cnt;
    }
    
    public static void change(char[] lightsCopy, int idx) {
    	for(int i=idx-1; i<=idx+1; i++) {
    		switch(lightsCopy[i]) {
    		case 'R':
    			lightsCopy[i] = 'G';
    			break;
    		case 'G':
    			lightsCopy[i] = 'B';
    			break;
    		case 'B':
    			lightsCopy[i] = 'R';
    			break;
    		}
    	}
    }
}

 

기존 내가 생각했던 풀이

위와 같은 형식으로 BFS를 구현하려고 했지만 결과는 메모리초과 였습니다..

=import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		n = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(br.readLine(), "");
		String light = st.nextToken();
		origin = light;
		
		BFS(light, 0);
		
		System.out.println(ans);
	}
	
	static String origin;
	
	static int ans = 0;
	static int n;
	
	public static void BFS(String pre, int cnt) {
		Queue<String> q = new LinkedList<>();
		q.add(pre);
		
		while(!q.isEmpty()) {
			String light = q.poll();
			cnt += 1;
			
			for(int i=0; i<light.length()-1; i++) {
				
				if(light.charAt(i) != light.charAt(i+1)) {
					break;
				}
				if(i == light.length()-2) {
					ans = cnt;
					return;
				}
			}
			
			for(int i=0; i<=light.length()-3; i++) {
				String next = change(light, i);
				System.out.println(i);
				System.out.println("cur: " + light);
				System.out.println("next: "+ next);
				if(!next.equals(origin)) {
					q.add(next);
				}
			}
		}
		
	}
	
	public static String change(String light, int idx) {
		
		for(int i=idx; i<idx+3; i++) {
			switch (light.charAt(i)) {
			case 'R':
				light = light.substring(0, i) + 'G' + light.substring(i+1);
				break;
			case 'G':
				light = light.substring(0, i) + 'B' + light.substring(i+1);
				break;
			case 'B':
				light = light.substring(0, i) + 'R' + light.substring(i+1);
				break;
			}
		}
		
		return light;
	}
}

---

회고

코드를 제출하니 메모리 초과가 나는 걸 보고.. 처음에는 이건 대체 얼마나 최적화 해서 풀어야 하는거지? 라는 생각과 내가 문제를 제대로 이해하고 있는게 맞나 싶어서 계속해서 문제를 봤지만 답이 안 나왔고.. 다른 분들의 풀이를 보면서도 문제 이해력이 딸리는 것인가 진지하게 생각하고 있었습니다.

그런데 코드를 보니까 굉장히 브루트포스의 느낌이 스멀스멀 오더라고요

그리디에 속아 브루트포스를 본 느낌..

코테 문제라는 것은 하나의 카테고리로 정의할 수 없다는 것을 느꼈습니다.

 

그렇지만 그리디로도 풀 수 있을 것 같은데 메모리로 너무 제약을 둔 게 아닌가 라는 생각이 들게 했던 억울한(?) 문제네요