코딩테스트 5주

바가지로 target 만들 수 있는지 판단

목표 : 2개의 바가지로 target을 만들 수 있는 지 여부 확인

해결방법 : gcd로 해결하였다.

target을 만들 때 아래 4가지 동작을 조합/반복해서 만들어야한다.

• 바가지에 물을 가득 채운다.
• 바가지의 물을 비운다.
• 한 바가지에서 다른 바가지가 가득 찰 때 까지 옮겨 담는다.
• 한 바가지가 빌 때 까지 다른 바가지에 옮겨 담는다.

그래서 두 개의 gcd를 구해서 gcd의 배수라면 target을 채울 수 있다고 생각했고 그렇게 문제를 푸니 해결이 되었다.

코드

class Solution {
    public boolean solution(int x, int y, int target) {
        if (target > Math.max(x, y)) return false;
        return target % gcd(x, y) == 0;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a%b);
    }
}

희소 행렬 곱 구하기

목표 : 희소 행렬 s와 t의 곱을 출력

해결방법 : s[i][k] * t[k][j]에서 s[i][k] == 0인 경우는 건너뛰어 연산을 줄인다.

O(m * n * l) 구조에서 불필요한 곱셈을 줄여 효율적으로 계산한다.

코드

class Solution {
    public int[][] solution(int[][] s, int[][] t) {
        int[][] answer = new int[s.length][t[0].length];

        for(int i=0; i<s.length; i++) {
            for(int k=0; k<s[0].length; k++) {
                if(s[i][k] == 0) continue;
                for(int j=0; j<t[0].length; j++) {
                    answer[i][j] += s[i][k] * t[k][j];
                }
            }
        }
        return answer;
    }
}

RLE(Running Length Encoding) 벡터 곱

목표 : 희소 벡터를 곱하고 결과를 RLE로 압축해서 출력한다.

해결방법 :

처음에는 s, t를 완전히 디코딩한 후 대응되는 위치끼리 곱한 뒤 결과 배열을 다시 RLE로 압축하는 방식으로 접근했다. 그러나 이 방식은 입력이 수십만 단위일 경우 디코딩 배열의 길이가 매우 길어지고 시간복잡도 및 메모리 측면에서 비효율적이라 시간 초과가 발생했다.

그래서 압축된 형태를 그대로 사용하여 곱셈과 RLE 압축을 동시에 처리하는 방식으로 변경했다. 두 벡터는 [값, 개수] 형식의 RLE로 표현되고 각 값을 순차적으로 읽어가면서 동일 인덱스끼리 곱하고 곱 결과가 연속되면 그룹핑하여 압축된 결과 배열을 생성했다.

핵심은 디코딩 없이 연산과 압축을 한 번에 수행한 것이다.

코드(90점)

import java.util.*;

class Solution {
    public int[][] solution(int[][] s, int[][] t) {
        int i = 0, j = 0;
        int sCnt = 0, tCnt = 0;

        List<int[]> list = new ArrayList<>();
        int prev = 0;
        int prevCnt = 0;
        boolean flag = true;

        while (i < s.length && j < t.length) {
            if (sCnt == 0) sCnt = s[i][1];
            if (tCnt == 0) tCnt = t[j][1];

            int cnt = Math.min(sCnt, tCnt);
            int mul = s[i][0] * t[j][0];

            if (flag) {
                prev = mul;
                prevCnt = cnt;
                flag = false;
            } else if (mul == prev) {
                prevCnt += cnt;
            } else {
                list.add(new int[]{prev, prevCnt});
                prev = mul;
                prevCnt = cnt;
            }
            
            sCnt -= cnt;
            tCnt -= cnt;

            if (sCnt == 0) i++;
            if (tCnt == 0) j++;
        }

         list.add(new int[]{prev, prevCnt});

        return list.toArray(new int[list.size()][]);
    }
}

가장 긴 증가하는 부분 수열

목표 : 가장 긴 증가하는 부분 수열(LIS) 길이 구하기

해결방법 : DP를 사용해 각 위치에서 끝나는 LIS의 길이를 저장하며 갱신한다.

nums[i] > nums[j]인 경우 dp[i] = max(dp[i], dp[j] + 1)로 점화식을 구성해서 문제를 해결했다.

코드

class Solution {
    public int solution(int[] nums) {
        int answer = 1;
        int[] dp = new int[nums.length];

        for(int i=0; i<nums.length; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}

블록 제거 반복 시뮬레이션

목표 : 동일한 숫자가 3개 이상 상하좌우로 붙어있을 경우 제거하고 제거된 공간을 위에서 채운 후 반복해서 최종 상태를 구한다.

해결방법 : BFS로 풀었다.

BFS를 사용해 상하좌우로 연결된 동일 숫자 블록을 탐색했고 3개 이상 연결된 경우만 제거 대상으로 판단했다. 제거된 블록들은 0으로 바꾸고, 각 열별로 위에서 아래로 숫자를 떨어뜨리는 중력 처리를 수행했다. 이 과정을 더 이상 제거할 수 있는 블록이 없을 때까지 반복적으로 수행하여 최종 보드 상태를 만들었다.

코드

import java.util.*;

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

    public int[][] solution(int[][] board) {
        int n = board.length;
        int m = board[0].length;

        while (true) {
            boolean[][] visited = new boolean[n][m];
            boolean removed = false;

            List<int[]> list = new ArrayList<>(); // 이번 턴에 제거할 블록 좌표들

			// 1. 전체 보드를 순회하며 같은 숫자가 3개 이상 연결된 그룹 찾기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j] && board[i][j] != 0) {
                        List<int[]> group = bfs(board, visited, i, j, n, m);
                        if (group.size() >= 3) {
                            removed = true; // 최소 한 개라도 제거되었는지 체크
                            list.addAll(group); // 제거 대상에 추가
                        }
                    }
                }
            }

			// 2. 제거할 블록이 없으면 종료
            if (!removed) break;

            // 3. 제거 대상 블록을 0으로 설정
            for (int[] pos : list) {
                board[pos[0]][pos[1]] = 0;
            }
            
            // 4. 중력 처리: 각 열(column) 별로 위에서 아래로 숫자 내리기
            for (int j = 0; j < m; j++) {
                int[] col = new int[n];
                int idx = n - 1;

                // 아래부터 위로 스캔하며 숫자만 아래부터 쌓기
                for (int i = n - 1; i >= 0; i--) {
                    if (board[i][j] != 0) {
                        col[idx--] = board[i][j];
                    }
                }

                // 다시 보드에 해당 열 갱신
                for (int i = 0; i < n; i++) {
                    board[i][j] = col[i];
                }
            }
        }

        return board;
    }

    // BFS로 연결된 동일 블록 탐색
    private List<int[]> bfs(int[][] board, boolean[][] visited, int y, int x, int n, int m) {
        List<int[]> group = new ArrayList<>();
        Queue<int[]> q = new LinkedList<>();

        visited[y][x] = true;
        q.add(new int[]{y, x});
        group.add(new int[]{y, x});
        int value = board[y][x];

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int ny = cur[0] + dy[d];
                int nx = cur[1] + dx[d];

                if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

                if (!visited[ny][nx] && board[ny][nx] == value) {
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                    group.add(new int[]{ny, nx});
                }
            }
        }

        return group;
    }
}