백준 3085번 사탕 게임 자바 Java (☆공부 286, 287일차)

3085 사탕 게임

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

3085번: 사탕 게임

 

 

---

백준 3085번 문제 사탕 게임

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	38080	12950	8859	32.898%

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

제한

 

예제 입력 1

3
CCP
CCP
PPC

예제 출력 1

3

예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

4

예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

4

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/282

공부 147일차: 백준 3085번 사탕 게임 자바 java

4달 전에 푼 문제

 

 

풀이는 두 가지

 

 

1) 2) 가로, 세로가 다를 때 바꾼 후 매번 모든 행, 렬을 확인3) 모든 행, 렬을 바꿔본 후 바뀐 자리를 기준으로 위 아래 확인 (★코드 효율적. 맨 아래에서 성능 비교 가능)

 

 

 

---

정답 인정 코드

---

 

1)

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    
    static int n;
    static char[][] candies;
    static int max;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = read();
        candies = new char[n][n];
        max = 0;
 
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < n; j++) {
                candies[i][j] = str.charAt(j);
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n-1; j++) {
                // 가로가 다르다
                if(candies[i][j] != candies[i][j+1]) {
                    // 바꾸기
                    char temp = candies[i][j];
                    candies[i][j] = candies[i][j+1];
                    candies[i][j+1] = temp;
                    check();
                    // 돌려놓기
                    temp = candies[i][j];
                    candies[i][j] = candies[i][j+1];
                    candies[i][j+1] = temp;
                }
            }
        }
        
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n; j++) {
                // 세로가 다르다
                if(candies[i][j] != candies[i+1][j]) {
                    char temp = candies[i][j];
                    candies[i][j] = candies[i+1][j];
                    candies[i+1][j] = temp;
                    check();
                    temp = candies[i][j];
                    candies[i][j] = candies[i+1][j];
                    candies[i+1][j] = temp;
                }
            }
        }
        System.out.println(max);
    }
 
    static int check() {
        for(int i = 0; i < n; i++) {
            int count = 1;
            for(int j = 0; j < n-1; j++) {
                if(candies[i][j] == candies[i][j+1]) {
                    count++;
                }else {
                    count = 1;    // 다르면 1부터 다시 시작
                }
                max = Math.max(count, max);
            }
        }
        
        for(int i = 0; i < n; i++) {
            int count = 1;
            for(int j = 0; j < n-1; j++) {
                if(candies[j][i] == candies[j+1][i]) {
                    count++;
                }else {
                    count = 1;
                }
                max = Math.max(count, max);
            }
        }
        return max;
    }
 
    static int read() throws Exception{
        int c, n = System.in.read() & 15;
        while((c = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (c & 15);
        }
        if(c == 13) {
            System.in.read();
        }
        return n;
    }
}
 

 

2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    
    static int n;
    static char[][] candies;
    static int max;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = read();
        candies = new char[n][n];
        max = 0;
 
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < n; j++) {
                candies[i][j] = str.charAt(j);
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n-1; j++) {
                // 가로가 다르다
                if(candies[i][j] != candies[i][j+1]) {
                    // 바꾸기
                    change(i, j, i, j+1);
                    check();
                    // 돌려놓기
                    change(i, j, i, j+1);
                }
            }
        }
        
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n; j++) {
                // 세로가 다르다
                if(candies[i][j] != candies[i+1][j]) {
                    change(i, j, i+1, j);
                    check();
                    change(i, j, i+1, j);
                }
            }
        }
        System.out.println(max);
    }
    
    static void change(int x1, int y1, int x2, int y2) {
        char temp = candies[x1][y1];
        candies[x1][y1] = candies[x2][y2];
        candies[x2][y2] = temp;
    }
 
    static int check() {
        for(int i = 0; i < n; i++) {
            int count = 1;
            for(int j = 0; j < n-1; j++) {
                if(candies[i][j] == candies[i][j+1]) {
                    count++;
                }else {
                    count = 1;    // 다르면 1부터 다시 시작
                }
                max = Math.max(count, max);
            }
        }
        
        for(int i = 0; i < n; i++) {
            int count = 1;
            for(int j = 0; j < n-1; j++) {
                if(candies[j][i] == candies[j+1][i]) {
                    count++;
                }else {
                    count = 1;
                }
                max = Math.max(count, max);
            }
        }
        return max;
    }
 
    static int read() throws Exception{
        int c, n = System.in.read() & 15;
        while((c = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (c & 15);
        }
        if(c == 13) {
            System.in.read();
        }
        return n;
    }
}
Colored by Color Scripter

 

3) 백준 맞힌 사람 1번째 코드 응용

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    
    static int n;
    static char[][] candies;
    static int max;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = read();
        candies = new char[n][n];
        max = 0;
 
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < n; j++) {
                candies[i][j] = str.charAt(j);
            }
        } 
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 가로 세로 다를 떄만 바꾸지 말고 모두 바꿔봄 -> 모든 행, 열 확인 가능
                if(j < n-1) { 
                    change(i, j, i, j+1);    // 자리 바꾸기
                    max = Math.max(check(i, j), max);    // 바뀐 대상 기준 세기
                    max = Math.max(check(i, j+1), max);    // 바뀐 대상 기준 세기
                    change(i, j, i, j+1);    // 원상복구
                }
 
                if(i < n-1) {
                    change(i, j, i+1, j);
                    max = Math.max(check(i, j), max);
                    max = Math.max(check(i+1, j), max);
                    change(i, j, i+1, j);
                    
                }
            }
        }
 
        System.out.println(max);
    }
    
    static void change(int x1, int y1, int x2, int y2) {
        char temp = candies[x1][y1];
        candies[x1][y1] = candies[x2][y2];
        candies[x2][y2] = temp;
    }
 
    static int check(int x, int y) {
        int cnt1 = 1;    // candies[x][y] 포함해서 1부터 세기
        for (int i = x-1; i >= 0; i--) {
            if (candies[i][y] == candies[x][y]) {                
                cnt1++;
            } else {                
                break;
            } 
        }
        for (int i = x+1; i < n; i++) {
            if (candies[i][y] == candies[x][y]){                
                cnt1++;
            } else {                
                break;
            } 
        }
 
        int cnt2 = 1;    // candies[x][y] 포함해서 1부터 세기
        for (int i = y-1 ; i >= 0; i--) {
            if (candies[x][i] == candies[x][y]){                
                cnt2++;
            } else {                
                break;
            } 
        }
        for (int i = y+1; i < n; i++) {
            if (candies[x][i] == candies[x][y]){                
                cnt2++;
            } else {                
                break;
            } 
        }
        return Math.max(cnt1, cnt2);
    }
 
    static int read() throws Exception{
        int c, n = System.in.read() & 15;
        while((c = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (c & 15);
        }
        if(c == 13) {
            System.in.read();
        }
        return n;
    }
}
 

 

 

 

---

 

마지막 214ms로 나온 코드가 3번 코드다

맞힌 사람 코드로 배우는 재미가 쏠쏠.. 복습 안 하면 몰랐을 일