프로그래머스(카카오 프렌즈 컬러링북, N으로 표현) - Java

[카카오 프렌즈 컬러링북]

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

* 조건

1. 2차원 배열을 위한 m, n이 주어진다. (1<=m, n <= 100)
2. 배열에 넣을 수 있는 값의 타입은 int형으로 가능하다
3. 0보다 큰 값들은 각각의 색이 있다고 생각
4. 배열의 값이 같은 수 -> 같은 색
5. 상하좌우로 탐색했을 때 같은 색의 영역 개수를 구하고, 가장 큰 영역을 지닌 칸의 개수와 몇개의 영역이 존재하는지 출력한다

* 알고리즘

- 상하좌우로 인접한 곳을 탐색: BFS

 

* 로직(Logic)

- for문으로 (0,0)부터 색이 존재하면서 영역 탐색이 이루어지지 않은 부분을 BFS로 탐색한다

- 다른 수가 나오면 영역의 탐색이 끝

- 해당 영역의 개수를 리턴하고, 최대 영역의 수를 계속해서 덮어준다

 

 

import java.util.LinkedList;
import java.util.Queue;

class Position_kakaoColorBook {
    public int y,x;

    public Position_kakaoColorBook(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Problem_kakaoColorBook {

    static int row, col;
    static boolean[][] checked;

    static int[] dy = {-1, 0 ,1, 0};
    static int[] dx = {0, 1 ,0, -1};

    public static void main(String[] args) {
        int m = 6;
        int n = 4;
        int[][] picture = {
                {1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}
        };

        int[] answer = solution(m, n, picture);
        for(int ans : answer)
            System.out.print(ans + " ");
        System.out.println();
    }

    public static int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        row = m;
        col = n;
        checked = new boolean[row][col];

        for(int i=0; i<row; ++i){
            for(int j=0; j<col; ++j){
                if(picture[i][j] != 0 && !checked[i][j]){
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, doBfs(picture, i, j));
                    numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    private static int doBfs(int[][] picture, int y, int x) {
        Queue<Position_kakaoColorBook> queue = new LinkedList<>();
        queue.offer(new Position_kakaoColorBook(y, x));
        checked[y][x] = true;

        int area = 1;
        while (!queue.isEmpty()){
            Position_kakaoColorBook q = queue.poll();
            for(int i=0; i<4; ++i){
                int moveY = q.y + dy[i];
                int moveX = q.x + dx[i];

                if(isRanged(moveY, moveX) && !checked[moveY][moveX] && picture[q.y][q.x] == picture[moveY][moveX]){
                    queue.offer(new Position_kakaoColorBook(moveY, moveX));
                    checked[moveY][moveX] = true;

                    area++;
                }
            }
        }
        return area;
    }

    private static boolean isRanged(int y, int x) {
        if(y >=0 && y<row && x>=0 && x<col) return true;
        return false;
    }
}

 

---

[N으로 표현]

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

* 조건

1. N: 사용할 수 있는 숫자, number: N을 가지고 만들고자하는 숫자 값
2. 사칙연산을 사용한다
3. N을 사용할 수 있는 횟수는 최대 8번까지이다
4. 최대 횟수 내에서 N을 이어붙일 수 있다 (ex. 2, 22, 222, 2222 ...)
5. 1 <= number <= 32000
6. N을 사용한 최소 횟수를 출력한다 (8번을 넘어가게 되면 -1을 리턴)

* 알고리즘

- 모든 경우의 수를 탐색: 브루트포스

 

* 로직

- 재귀 함수 내에서 N을 가지고 만들 수 있는 자릿 수(최대 8번) 탐색이 가능하도록 for문을 설정한다

- 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈)에 대한 재귀를 각각 만들어준다

- (조건-4)를 고려하여 N = N*10 + N을 통해 이어붙이는 카드의 범위를 넓혀준다

- 재귀를 돌면서 원하는 결과값과 같아지면 최소 카드 개수를 넣어준다

- 원하는 값을 얻지 못했다면 -1을 리턴한다

 

 

public class Problem_representN {
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int N = 1;
        int number = 23;
        int ans = solution(N, number);
        System.out.println(ans);
    }

    public static int solution(int N, int number) {
        int count = 0;
        doCalculate(0, number, count, N);

        if(answer != Integer.MAX_VALUE) return answer;
        else return -1;
    }

    private static void doCalculate(int num, int number, int count, int N) {
        int increaseN = N;

        if(num == number){
            answer = Math.min(answer, count);
            return;
        }

        for(int i=0; i<8-count; ++i){
            //사칙연산
            doCalculate(num + increaseN, number, count+i+1, N);
            doCalculate(num - increaseN, number, count+i+1, N);
            doCalculate(num * increaseN, number, count+i+1, N);
            doCalculate(num / increaseN, number, count+i+1, N);

            increaseN = increaseN * 10 + N;
        }
    }
}

 

 

[N으로 표현]의 경우, 테스트케이스가 부족한건지는 모르겠는데 약간의 오류가 있는거 같다는 생각을 했다. 예를 들어, N=5이고 number=23이라면 (5*5) - (5+5)/5 -> 5개면 완성이되지만 위 코드에서는 6개로 완성이 된다. 아마 괄호에 대한 고려가 부족했기때문 아닐까..

 

근데 답이 맞았다고 하는걸 보면 식의 중간부분에는 괄호가 적용이 안됐기 때문에 그냥 순서대로 완전탐색을 통해 계산을 해도 무방했던거 같다.

 

이 문제를 풀 때, 이어붙이는게 한번씩 밖에 안된다는 생각에 갇혀 해맸다.(조건을 덜 따진거겠지..)
ex. N=1이고 number = 23일 때 -> 11 + 11 + 1 (5개)가 가능한데, 나는 처음에 11묶는게 한번밖에 못하는 줄 알았다.. 케이스를 넓게 생각하려고 계속해서 되뇌어야겠다.