[백준] S4 3085 사탕 게임 (java)

www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

풀이

 

1) 이차원 배열을 탐색하면서 오른쪽으로 한번, 아래쪽으로 한번 바꿈

2) 최대길이를 갱신한다.

3) 바꾼거 제자리로 원위치

 

주의사항

 

1) 배열의 오른쪽, 아래 가장자리 때문에 isIn()으로 체크해줘야함

 

package com.baekJoon;

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

public class BJ_S4_3085_사탕게임 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, max=1;
	static char map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		map = new char[N][N];
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<N; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		
		solve();
		System.out.println(max);
	}

	private static void solve() {
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				int nr = r+1;
				int nc = c+1;
				
				if(isIn(r, nc)) {
					char temp = map[r][c];
					map[r][c] = map[r][nc];
					map[r][nc] = temp;
					getMaxCandy();
					temp = map[r][nc];
					map[r][nc] = map[r][c];
					map[r][c] = temp;
				}
				
				if(isIn(nr, c)) {
					char temp = map[r][c];
					map[r][c] = map[nr][c];
					map[nr][c] = temp;
					getMaxCandy();
					temp = map[nr][c];
					map[nr][c] = map[r][c];
					map[r][c] = temp;
				}
			}	
		}
	}

	private static void getMaxCandy() {
		char peek = '0';
		for(int r=0; r<N; r++) {
			int cnt = 0;
			for(int c=0; c<N; c++) {
				if(peek == '0') {
					peek = map[r][c];
					cnt = 1;
				}else {
					if(peek == map[r][c]) {
						cnt++;
						if(max < cnt) {
							max = cnt;
						}
					}else {
						cnt = 1;
						peek = map[r][c];
					}
				}
			}
		}
		peek = '0';
		for(int c=0; c<N; c++) {
			int cnt = 0;
			for(int r=0; r<N; r++) {
				if(peek == '0') {
					peek = map[r][c];
					cnt = 1;
				}else {
					if(peek == map[r][c]) {
						cnt++;
						if(max < cnt) {
							max = cnt;
						}
					}else {
						cnt = 1;
						peek = map[r][c];
					}
				}
			}
		}
	}

	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<N);
	}
	
	static String src =
			"4\r\n" + 
			"CCCC\r\n" + 
			"YDYD\r\n" + 
			"DYDY\r\n" + 
			"YDYD";
}

 

 

후기

 

처음엔 있어보일려고 스택을 썼는데 메모리가 213080KB, 시간이 900ms가 나와서 스택부분을 없앴더니 시간과 메모리가 단축되었다. 쉽게생각하는것이 좋다는것을 깨달았다.