[백준] 3085 : 사탕게임

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

3085번: 사탕 게임

N의 최대가 굉장히 작아서 4중포문까지도 괜찮았기 때문에 편하게 코드를 짰다.

근데 코드가 너무 반복되는 것도 많고 복잡하고 길어지는 느낌이라 결국 찾아봄.

반복되는 부분이 많으면 따로 메소드를 짜서 사용하는 것이 편하다고 한다.

메소드 짜는 것도 피하지 말고 많이 해봐야 할 것 같음.

 

바꿀 수 있는 부분을 하나씩 바꾼 후에 요소가 바뀐 행과 열을 탐색 해주고 최댓값을 구한다.

변경은 한 번만 되니 바꿨던 부분은 다시 돌려줌.

가로로 변경되면 요소가 바뀐 열이 2개, 요소가 바뀐 행이 1개

세로로 변경되면 요소가 바뀐 행이 2개, 요소가 바뀐 열이 1개

이렇게 계속 3개의 행과 열을 탐색해준다.

 

내 코드

메모리 : 14172 KB

시간 : 140 ms

코드길이 : 2315 B

 

[내 코드]

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

public class Main {
	static int N;
	static char[][] candy;
	static int max = 1;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		candy = new char[N][N];
		for(int r = 0; r < N; r++) {
			String str = br.readLine();
			for(int c = 0; c < N; c++) {
				candy[r][c] = str.charAt(c);
			}
		}
		
		//바꾸지 않고 행의 최댓값
		for(int i = 0; i < N; i++) {
			searchRow(i);
		}
		//바꾸지 않고 열의 최댓값
		for(int i = 0; i < N; i++) {
			searchColumn(i);
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				//가로로 바꿔가며 최댓값
				if(j + 1 < N) {
					if(candy[i][j] != candy[i][j + 1]) {
						changeRightLeft(i, j);
						searchRow(i);
						searchColumn(j);
						searchColumn(j + 1);
						changeRightLeft(i, j); // 다시 바꿔주야 함
					}
				}
				
				//위아래 바꿔가며 최댓값
				if(i + 1 < N) {
					if(candy[i][j] != candy[i + 1][j]) {
						changeUpDown(i, j);
						searchRow(i);
						searchRow(i + 1);
						searchColumn(j);
						changeUpDown(i, j);
					}
				}
			}
		}
		sb.append(max);
		System.out.print(sb);
	}
	
	//row번째 행 탐색
	public static void searchRow(int row) {
		int tmp = 1; //해당 행의 최대길이
		for(int i = 0; i < N - 1; i++) {
			if(candy[row][i] == candy[row][i + 1])
					tmp++;
			else
				tmp = 1;
			max = Math.max(max, tmp);
		}
	}
	
	//열 탐색
	public static void searchColumn(int column){
		int tmp = 1; // 해당 열의 최대길이
		for(int i = 0; i < N - 1; i++) {
			if(candy[i][column] == candy[i + 1][column])
				tmp++;
			else
				tmp = 1;
			max = Math.max(max, tmp);
		}
	}
	
	//가로로 교환
	public static void changeRightLeft(int row, int column) {
		char tmp = candy[row][column];
		candy[row][column] = candy[row][column + 1];
		candy[row][column + 1] = tmp;
	}
	
	//세로로 교환
	public static void changeUpDown(int row, int column) {
		char tmp = candy[row][column];
		candy[row][column] = candy[row + 1][column];
		candy[row + 1][column] = tmp;
	}
	


}

1등 코드

메모리 : 11836 KB

시간 : 76 ms

코드길이 : 3688 B

 

[1등 코드]

/* 
    사탕 게임
*/

import java.io.*;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        init();

        change();

        System.out.println(answer);

    }

    static int N, answer;
    static char[][] board;

    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        board = new char[N][N];
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
        }
    }

    static void change() {

        answer = 0;

        for (int i = 0; i < N; i++) {
            int c = 1;
            for (int j = 1; j < N; j++) {
                if (board[i][j] == board[i][j - 1]) {
                    c++;
                    if (c > answer) {
                        answer = c;
                    }
                } else {
                    c = 1;
                }
            }
        }
        for (int j = 0; j < N; j++) {
            int c = 1;
            for (int i = 1; i < N; i++) {
                if (board[i][j] == board[i-1][j]) {
                    c++;
                    if (c > answer) {
                        answer = c;
                    }
                } else {
                    c = 1;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                if (j < N - 1 && (board[i][j] != board[i][j + 1])) {
                    countCandy(i, j, i, j + 1);
                }

                if (i < N - 1 && (board[i][j] != board[i + 1][j])) {
                    countCandy(i, j, i + 1, j);

                }
            }
        }
    }

    static void countCandy(int x1, int y1, int x2, int y2) {

        int count = 1;
        int nx = x1;
        int ny = y1;
        while (--nx >= 0) {
            if (board[nx][ny] != board[x2][y2] || (nx == x2) && (ny == y2)) {
                break;
            }
            count++;
        }
        nx = x1;
        while (++nx < N) {
            if (board[nx][ny] != board[x2][y2] || (nx == x2) && (ny == y2)) {
                break;
            }
            count++;
        }
        answer = Math.max(answer, count);

        count = 1;
        nx = x1;
        while (--ny >= 0) {
            if (board[nx][ny] != board[x2][y2] || (nx == x2) && (ny == y2)) {
                break;
            }
            count++;
        }
        ny = y1;
        while (++ny < N) {
            if (board[nx][ny] != board[x2][y2] || (nx == x2) && (ny == y2)) {
                break;
            }
            count++;
        }
        answer = Math.max(answer, count);

        count = 1;
        nx = x2;
        ny = y2;
        while (--nx >= 0) {
            if (board[nx][ny] != board[x1][y1] || (nx == x1) && (ny == y1)) {
                break;
            }
            count++;
        }
        nx = x2;
        while (++nx < N) {
            if (board[nx][ny] != board[x1][y1] || (nx == x1) && (ny == y1)) {
                break;
            }
            count++;
        }
        answer = Math.max(answer, count);

        count = 1;
        nx = x2;
        while (--ny >= 0) {
            if (board[nx][ny] != board[x1][y1] || (nx == x1) && (ny == y1)) {
                break;
            }
            count++;
        }
        ny = y2;
        while (++ny < N) {
            if (board[nx][ny] != board[x1][y1] || (nx == x1) && (ny == y1)) {
                break;
            }
            count++;
        }
        answer = Math.max(answer, count);

    }

}