카카오 모의 테스트 문제(Java)

카카오 모의 테스트 문제(Java)

문제 풀어본거 코드 올려봅니다. 궁금하신 점이나 코드에서 고쳐야할 부분이 있다면 댓글 달아주세요.

* 문제 1, 2, 3 : 쉬움

* 문제 4, 5, 6, 7 : dp 문제

* 문제 5

- 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패, 바텀업 방식으로 풀이 시 효율성 테스트 성공. 두 경우 걸리는 시간은 비슷함.

(두가지 방식의 코드 모두 올려놨습니다)

- 제가 올린 바텀업 코드에서 메모리를 더 많이 절약할 수 있습니다. dp배열을 [100001][4]로 선언하지 않아도 됩니다.

* 문제 7

- 문제 7번의 경우에도 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패.

---

문제 #1

/**
 * 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.
 * 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.
 */

public class Solution {

    public int solution(int n) {

        return getAnswer(n);
    }

    public int getAnswer(int n) {

        int answer = 0;

        while (n > 0) {

            answer += (n % 10);
            n /= 10;
        }

        return answer;
    }
}

문제 #2

/**
 * 길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
 * 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.
 */
class Solution {

    public boolean solution(int[] arr) {

        boolean answer = true;

        boolean[] check = new boolean[arr.length + 1];

        for (int i = 0; i < arr.length; i++) {

            if (arr[i] <= arr.length && !check[arr[i]]) {

                check[arr[i]] = true;

            } else {

                answer = false;
                break;
            }
        }

        return answer;
    }
}

문제 #3

/**
 * 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다.
 * 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요.
 * 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다.
 */
class Solution {

    public int[] solution(int[][] v) {

        int[] answer = new int[2];

        answer[0] = 0;
        answer[1] = 0;

        for (int i = 0; i < 3; i++) {

            answer[0] ^= v[i][0];
            answer[1] ^= v[i][1];
        }

        return answer;
    }
}

문제 #4

/**
 * 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.
 * 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.
 * (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
 */
class Solution {

    public int solution(int[][] board) {

        int answer = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {

                if (board[i][j] == 0) continue;

                if ((i - 1 >= 0 && board[i - 1][j] > 0)
                        && (j - 1 >= 0 && board[i][j - 1] > 0)
                        && (i - 1 >= 0 && j - 1 >= 0 && board[i - 1][j - 1] > 0)) {

                    board[i][j] = Math.min(Math.min(board[i - 1][j], board[i][j - 1]), board[i - 1][j - 1]) + 1;
                }

                answer = answer < board[i][j] ? board[i][j] : answer;
            }
        }
        return answer * answer;
    }
}

문제 #5

/**
 * 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다.
 * 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다.
 * 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
 */
class Solution {

    static int[][] dp = new int[100001][4];

    static int solution(int[][] land) {

        int answer = 0;
        //Solve Recursive
        /*
        for (int col = 0; col < 4; col++) {

            answer = Math.max(answer, solveRecursive(land, 0, col));
        }
        */

        // Solve

        for (int i = 0; i < 4; i++) {

            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < land.length; i++) {

            for (int j = 0; j < 4; j++) {

                int maxValue = 0;
                for (int k = 0; k < 4; k++) {

                    if (j == k) continue;
                    maxValue = Math.max(maxValue, dp[i - 1][k] + land[i][j]);
                }

                dp[i][j] = maxValue;
            }
        }

        for (int i = 0; i < 4; i++) {

            answer = Math.max(answer, dp[land.length - 1][i]);
        }

        return answer;
    }

    static int solveRecursive(int[][] land, int rowIdx, int prevColIdx) {

        // 기저 조건
        if (rowIdx >= land.length) return 0;

        // Memoization
        if (dp[rowIdx][prevColIdx] != 0) return dp[rowIdx][prevColIdx];

        // 탐색
        int maxSum = 0;

        for (int col = 0; col < 4; col++) {

            if (col == prevColIdx) continue;

            maxSum = Math.max(solveRecursive(land, rowIdx + 1, col) + land[rowIdx][col], maxSum);
        }

        return dp[rowIdx][prevColIdx] = maxSum;
    }
}

문제 #6

/**
 * N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.
 * 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다.
 * 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.
 */
class Solution {

    static int[][] dp = new int[100001][2];

    public static int solution(int sticker[]) {

        int N = sticker.length;

        // N <= 2 인 경우
        if (N == 1) return sticker[0];
        if (N == 2) return Math.max(sticker[0], sticker[1]);

        // N > 2 인 경우

        // 해설 : 0번 스티커를 기준으로 했을 때, 모든 경우의 수는 0번 스티커를 뜯는/뜯지 않는 경우, 이 2가지 경우로 나눌 수 있다
        
        // dp 정의 : dp[N] -> N번째 스티커까지 진행했을 때 얻을 수 있는 최대 값
        // dp[N][0] -> N번째 스티커까지 진행했을 때 얻을 수 있는 최대 값(0번째 스티커를 뜯는 경우)
        // dp[N][1] -> N번째 스티커까지 진행했을 때 얻을 수 있는 최대 값(0번째 스티커를 뜯지 않는 경우)
        
        // 1. 0번 스티커를 뜯는 경우
        dp[0][0] = sticker[0];
        dp[1][0] = dp[0][0];

        for (int i = 2; i < N - 1; i++) {

            // i 번째에서 얻을 수 있는 최대값은 2가지 중 max값이다
            // 1) i-2번째에서 얻을 수 있는 최대값 + 현재 스티커 값
            // 2) i-1번째에서 얻을 수 있는 최대값
            dp[i][0] = Math.max(dp[i - 2][0] + sticker[i], dp[i - 1][0]);
        }
        dp[N - 1][0] = dp[N - 2][0];

        // 2. 0번 스티커를 뜯지 않는 경우
        dp[0][1] = 0;
        dp[1][1] = sticker[1];

        for (int i = 2; i < N; i++) {

            dp[i][1] = Math.max(dp[i - 2][1] + sticker[i], dp[i - 1][1]);
        }
        
        
        // Result
        return Math.max(dp[N - 1][0], dp[N - 1][1]);
    }
}

문제 #7

import java.util.Arrays;
import java.util.HashSet;

public class Solution {

    static HashSet<String> set = new HashSet<>();
    static int[] dp = new int[20001];

    static final int INF = 1000000000;

    static {

        Arrays.fill(dp, -1);
    }

    public static int solution(String[] strs, String t) {

        for (String s : strs) {

            set.add(s);
        }

        solveRecursive(t, 0);

        return dp[0] == INF ? -1 : dp[0];
    }

    public static int solveRecursive(String t, int idx) {

        // 기저 조건
        if (idx == t.length()) return 0;

        // memoization
        if (dp[idx] != -1) return dp[idx];

        dp[idx] = INF;

        // 탐색
        for (int i = idx; i < Math.min(idx + 5, t.length()); i++) {

            String s = t.substring(idx, i + 1);

            if (set.contains(s)) {

                dp[idx] = Math.min(dp[idx], solveRecursive(t, idx + s.length()) + 1);
            }
        }

        return dp[idx];
    }
}