백준 JAVA 3085 사탕 게임

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

3085번: 사탕 게임

 

2주? 전에 한번 봤는데 다시 풀어보려고 했는데 실패했다.

문제는 이해가 되는데 구현이 안되니 답답하다.

2~3일 뒤에 다시한번 풀 예정.

 

// 가로 , 세로 비교하면서 먹을 수 있는 사탕의 최대 개수 찾기
static void check() {
    // 가로체크
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = 0; j < n-1; j++) {
            if ( arr[i][j] == arr[i][j+1]) {
                count++;
            } else {
                count = 1;
            }
            max = Math.max(max,count);
        }
    }

    // 세로체크
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = 0; j < n-1; j++) {
            if ( arr[j][i] == arr[j+1][i]) {
                count++;
            } else {
                count = 1;
            }
            max = Math.max(max,count);
        }
    }
}

먼저, 가로방향, 세로방향을 체크하는 메소드를 따로 정의한다.

가로 체크는 쉽게 이해가 갔는데, 세로체크에서 i 와 j 의 순서를 바꿔서 비교해야 하는것에서 조금 시간이 걸렸다.

전부다 노트에 써가면서 구현해보았더니 이해가 갔다.

비교할때마다 max 값과 count 값을 비교하면서 max 값을 최신화 시켜준다.

만약 비교하다가 다른 캔디가 나오면 count를 다시 세어야 하기 때문에 1로 초기화한다.

 

// 가로로 인접한 두사람 교환 및 최대 사탕개수 찾기
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {

        char tmp = arr[i][j];
        arr[i][j] = arr[i][j + 1];
        arr[i][j + 1] = tmp;
        check();
        tmp = arr[i][j];
        arr[i][j] = arr[i][j + 1];
        arr[i][j + 1] = tmp;
    }
}

// 세로로 인접한 두사람 교환 및 최대 사탕개수 찾기
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {

        char tmp = arr[j][i];
        arr[j][i] = arr[j + 1][i];
        arr[j + 1][i] = tmp;
        check();
        tmp = arr[j][i];
        arr[j][i] = arr[j + 1][i];
        arr[j + 1][i] = tmp;
    }
}

가로와 세로를 교환하는 과정도 따로 구현해주어야 했다.

교환했으면 비교메소드를 이용해 비교하고, 다시 되돌려(교환)해야 원상복구가 된다.

 

 

package BAEKJOON.Silver.Ⅲ;

/**
 * 시간 제한   메모리 제한 제출 정답 맞힌 사람  정답 비율
 * 1 초 128 MB 30734  10260  7061   32.405%
 */

import java.util.Scanner;

public class NO3085_re {

    static Character[][] arr;
    static int n;
    static int max = 0;

    // 가로 , 세로 비교하면서 먹을 수 있는 사탕의 최대 개수 찾기
    static void check() {
        // 가로체크
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n-1; j++) {
                if ( arr[i][j] == arr[i][j+1]) {
                    count++;
                } else {
                    count = 1;
                }
                max = Math.max(max,count);
            }
        }

        // 세로체크
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n-1; j++) {
                if ( arr[j][i] == arr[j+1][i]) {
                    count++;
                } else {
                    count = 1;
                }
                max = Math.max(max,count);
            }
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new Character[n][n];

        //입력받기
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < n; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        // 가로로 인접한 두사람 교환 및 최대 사탕개수 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {

                char tmp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = tmp;
                check();
                tmp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = tmp;
            }
        }

        // 세로로 인접한 두사람 교환 및 최대 사탕개수 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {

                char tmp = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = tmp;
                check();
                tmp = arr[j][i];
                arr[j][i] = arr[j + 1][i];
                arr[j + 1][i] = tmp;
            }
        }
        System.out.println(max);

    }
}

 

 

아래 블로그를 참고했다.

https://zzang9ha.tistory.com/203

[백준] 3085번: 사탕 게임(완전 탐색)