문제 풀이

1차 실행 오류

50.0/100

실패 및 런타임 에러

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        int cur = 1;
        int answer = 0;
        Deque<Integer> sub = new ArrayDeque<>();

        int idx = 0;
        while(true) {
            if (idx >= orders.length || cur > orders[idx] && sub.peek() > orders[idx]) {
                break;
            }
            if (cur == orders[idx]) { // 현재 꺼낸 상자가 이번 순서인 경우
                answer++;
                idx++;
            }
            else if (!sub.isEmpty() && sub.peek() == orders[idx]) { 
                // 보조 컨테이너 벨트의 상자가 이번 순서인 경우
                answer++;
                idx++;
                sub.pop();
            }
            else { // 현재 꺼낸 상자가 이번 순서가 아닌 경우
                sub.push(cur); // 보조 컨테이너 벨트에 삽입
            }
            cur++;
        }

        return answer;
    }
}

나의 코드

소요 시간: 38분 시간 복잡도: $O(n)$

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        int cur = 1;
        int answer = 0;
        Deque<Integer> sub = new ArrayDeque<>();

        int idx = 0;
        while(true) {
            if (!sub.isEmpty() && sub.peek() == orders[idx]) {
                sub.pop();
                answer++;
                idx++;
            }
            else sub.push(cur++);
            if (idx >= orders.length || !sub.isEmpty() && sub.peek() > orders[idx]) break;
        }

        return answer;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

전체적인 구조는 동일하다.

바깥쪽 for문을 이용해서 orders의 길이만큼 반복하고 안쪽의 while문을 이용해서 서브 컨테이너 벨트에서 택배 상자를 빼는 작업을 분할해서 진행한 코드이다.

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int[] orders) {
        int n = orders.length;
        Deque<Integer> sub = new ArrayDeque<>(); // 보조 컨테이너
        int idx = 0;                             // 다음에 실어야 할 주문 위치

        for (int box = 1; box <= n; box++) {
            sub.push(box);                       // 컨테이너 벨트에서 상자 하나 올림
            // 꼭대기가 원하는 상자인 동안 계속 트럭에 실음
            while (idx < n && !sub.isEmpty() && sub.peek().intValue() == orders[idx]) {
                sub.pop();
                idx++;
            }
        }
        return idx; // 실은 상자 개수 = 처리한 주문 개수
    }
}

문제 풀이 후기

나의 코드에서 answer와 idx가 가리키는 값이 항상 일치하기 때문에 둘 중 하나만 사용하면 된다.

1차에서 실패한 코드를 보고 로직이 너무 꼬여 있다는 생각이 들었다. 좀 더 단순화해서 풀 수 있는 방법이 없을까? 고민하다가 서브 컨테이너 벨트에 계속 다 넣고, 들어가 있는 상자가 현재 실어야 하는 순서의 상자이면 빼는 방식으로 코드를 작성하였다.

문제 풀이

나의 코드

소요 시간: 2시간 16분 시간 복잡도: $O(n)$

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        int order = 1;
        Map <String, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        for (char c = 'A'; c <= 'Z'; c++) { // 해시맵에 알파벳 저장
            map.put(Character.toString(c), order++);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            sb.append(c);
            if (map.get(sb.toString()) == null) { // 해시맵에 해당 단어가 존재하지 않을 때
                map.put(sb.toString(), order++);
                list.add(map.get(sb.substring(0, sb.length() - 1)));
                sb.setLength(0);
                sb.append(c);
            }
        }
        if (sb.length() > 0) {
            list.add(map.get(sb.toString()));
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

substring 대신에 prev, cur 변수를 이용하여 반복당 문자열 객체 1개 생성을 감소하였다.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        Map<String, Integer> dict = new HashMap<>();
        int index = 1;
        for (char c = 'A'; c <= 'Z'; c++) { // 사전 초기화
            dict.put(String.valueOf(c), index++);
        }

        List<Integer> answer = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int prev = 0; // 직전까지 매칭된 문자열의 색인

        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            sb.append(c);
            Integer cur = dict.get(sb.toString());

            if (cur == null) {          // 사전에 없음 → 등록하고 직전 색인 출력
                dict.put(sb.toString(), index++);
                answer.add(prev);
                sb.setLength(0);
                sb.append(c);           // 마지막 글자부터 다시 시작
                prev = dict.get(sb.toString());
            } else {                    // 사전에 있음 → 색인만 갱신하고 계속 확장
                prev = cur;
            }
        }
        answer.add(prev);               // 남은 문자열 처리

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

문제 풀이 후기

이전에는 풀었던 문제임에도 불구하고 이번에는 해결하지 못하였다.

프로젝트의 막바지라 약 2주동안 코딩 테스트를 쉬었던 상태에서 시작해서 감을 잃었나 싶다. 역시 뭐든 꾸준히 하는 것이 가장 중요하다고 생각된다.

문제 풀이

1차 실행 오류

0.0/100

시간 초과 오류

시간 초과 원인 분석

행의 개수가 100,000개 이하인 배열에 DFS를 사용한 것이 원인

class Solution {
    private int answer = 0;
    int solution(int[][] land) {
        dfs(land, 0, 0, 0);

        return answer;
    }
    private void dfs(int land[][], int row, int col, int sum) {
        answer = Math.max(answer, sum);
        if (row >= land.length) {
            return;
        }

        for (int i = 0; i < land[row].length; i++) {
            if (i == col) {
                continue;
            }
            dfs(land, row + 1, col, sum + land[row][i]);    
        }
    }
}

나의 코드

소요 시간: 45분 시간 복잡도: $O(n)$

코드 분석

이전 행과 현재 행 사이에서 가장 큰 값을 찾아 저장하여 가장 큰 값을 찾아냄

class Solution {
    int solution(int[][] land) {
        int row = land.length;
        int col = land[0].length;

        int[][] dp = new int[row][col];

        for (int i = 0; i < col; i++) {
            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < col; k++) {
                    if (j == k) continue;
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + land[i][j]);
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < col; i++) {
            answer = Math.max(answer, dp[row - 1][i]);
        }

        return answer;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

기존 나의 코드에서 3중 for문을 사용하던 방식에서 이전 행의 첫 번째로 큰 값과 두 번째로 큰 값을 미리 구해서 이번 행의 가장 큰 값과 더하는 방식을 사용하여 개선함

class Solution {
    int solution(int[][] land) {
        int n = land.length, c = land[0].length;
        int[] prev = land[0].clone();

        for (int i = 1; i < n; i++) {
            // 직전 행의 1등 값/인덱스와 2등 값
            int best = Integer.MIN_VALUE, second = Integer.MIN_VALUE, bestIdx = -1;
            for (int j = 0; j < c; j++) {
                if (prev[j] > best) { second = best; best = prev[j]; bestIdx = j; }
                else if (prev[j] > second) { second = prev[j]; }
            }

            int[] cur = new int[c];
            for (int j = 0; j < c; j++) {
                cur[j] = land[i][j] + (j == bestIdx ? second : best);  // 같은 열이면 2등을 사용
            }
            prev = cur;   // 행 하나만 굴린다 → 공간 O(1)
        }

        int answer = Integer.MIN_VALUE;
        for (int v : prev) answer = Math.max(answer, v);
        return answer;
    }
}

문제 풀이 후기

DP 문제가 너무 어렵다고 느껴진다. AI 분석을 해 본 결과 다른 자료구조 문제에 비해 풀어 보았던 문항 수가 현저히 적어서 손에 익지 않았다는 것이 그 원인이다.

나의 학습법을 보면 많은 경험을 토대로 익숙해지는 것이 가장 수월하게 배울 수 있는 길이라고 생각한다.

문제 풀이

나의 코드

소요 시간: 16분 시간 복잡도: $O(t·m)$

class Solution {
    public String solution(int n, int t, int m, int p) {
        StringBuilder sb = new StringBuilder();

        int idx = 0;
        int order = 1;
        while(sb.length() < t) {
            String number = Integer.toString(idx, n);
            number = number.toUpperCase();
            for (int i = 0; i < number.length(); i++) {
                if (order == p) {
                    sb.append(number.charAt(i));
                    if (sb.length() == t) {
                        break;
                    }
                }
                order = order % m + 1;
            }
            idx++;
        }

        return sb.toString();
    }
}

AI 코드

시간 복잡도: $O(t·m)$

코드 분석

필요한 n진수 전부를 미리 tube에 저장해두고, 튜브의 순서에 필요한 수만 따로 빼서 저장

class Solution {
    public String solution(int n, int t, int m, int p) {
        // 1) 필요한 만큼만 튜브 생성: 마지막으로 읽을 위치는 (t-1)*m + p ≤ t*m
        StringBuilder tube = new StringBuilder();
        for (int i = 0; tube.length() < t * m; i++) {
            tube.append(Integer.toString(i, n).toUpperCase());
        }

        // 2) p번째(1-based)부터 m칸씩 t개 뽑기
        StringBuilder answer = new StringBuilder();
        for (int i = p - 1; answer.length() < t; i += m) {
            answer.append(tube.charAt(i));
        }
        return answer.toString();
    }
}

문제 풀이 후기

수학적인 계산이 코드 길이에 얼마나 큰 영향을 주는지 알 수 있었다. 필요한 n진수를 미리 계산하는 과정을 통해서, 각 숫자마다 String을 2개씩 할당하는 과정을 없앴다.

문제 풀이

나의 코드

소요 시간: 37분 시간 복잡도: $O(n)$

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<int[]> stack = new ArrayDeque<>();

        int cnt = -1;
        for (int i = 0; i < prices.length; i++) {
            cnt++;
            while(!stack.isEmpty() && stack.peek()[1] > prices[i]) {
                int[] s = stack.pop();
                answer[s[0]] = cnt - s[0];
            }
            stack.push(new int[]{i, prices[i]});      
        }
        while(!stack.isEmpty()) {
            int[] s = stack.pop();
            answer[s[0]] = cnt - s[0];
        }

        return answer;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

전체적인 알고리즘은 동일하나, cnt를 사용하지 않고 i로 대체, 값을 저장하지 않고, 인덱스만 저장하여 prices[stack.peek()]로 대체하여 코드의 불필요한 변수 사용을 줄였다.

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        int[] stack = new int[n];   // 아직 가격이 떨어지지 않은 시점들의 인덱스
        int top = -1;

        for (int i = 0; i < n; i++) {
            // i초에 가격이 떨어졌다면, 그보다 비쌌던 시점들은 여기서 기간 확정
            while (top >= 0 && prices[stack[top]] > prices[i]) {
                int j = stack[top--];
                answer[j] = i - j;
            }
            stack[++top] = i;
        }
        // 끝까지 떨어지지 않은 시점들
        while (top >= 0) {
            int j = stack[top--];
            answer[j] = n - 1 - j;
        }
        return answer;
    }
}

문제 풀이 후기

대체 가능한 필요없는 변수를 정리해서 해당 작업을 거친 AI 코드는 훨씬 길이가 짧고 가독성이 좋다. 코드 작성 후에 깔끔하게 마무리 하는 습관을 들여야 할 것 같다.

문제 풀이

1차 실행 오류

86.9/100

런타임 에러

런타임 에러 원인 분석

n = 797161, k = 3 (n을 k진수로 변환하면 1111111111111에 해당함) int로 전부 담을 수 없음

class Solution {
    public int solution(int n, int k) {
        int cnt = 0;
        String baseK = Integer.toString(n, k);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < baseK.length(); i++) {
            char c = baseK.charAt(i);
            if (c == '0') {
                if (!sb.isEmpty() && isPrime(Integer.parseInt(sb.toString()))) {
                    cnt++;
                }
                sb.setLength(0);
            }
            else {
                sb.append(c);
            }
        }
        if (!sb.isEmpty() && isPrime(Integer.parseInt(sb.toString()))) {
            cnt++;
        }
        return cnt;
    }
    private boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int limit = (int)Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

나의 코드

소요 시간: 42분 시간 복잡도: $O(√(10^{log_k n}))$

class Solution {
    private boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        int limit = (int)Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int solution(int n, int k) {        
        int cnt = 0;
        String baseK = Integer.toString(n, k);           
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < baseK.length(); i++) {
            char c = baseK.charAt(i);
            if (c == '0') {
                if (!sb.isEmpty() && isPrime(Long.parseLong(sb.toString()))) {
                    cnt++;
                }
                sb.setLength(0);
            }
            else {
                sb.append(c);
            }
        }
        if (!sb.isEmpty() && isPrime(Long.parseLong(sb.toString()))) {
            cnt++;
        }
        return cnt;
    }
}

AI 코드

시간 복잡도: $O(√(10^{log_k n}))$

코드 분석

전체적인 구조는 동일하나 split("0")을 사용해서 길었던 if/else문을 단번에 정리했음

sb.isEmpty()는 Java 15에서 추가된 메서드이기 때문에 이전 버전에서는 오류가 발생할 수 있음.

class Solution {
    public int solution(int n, int k) {
        int cnt = 0;
        for (String s : Integer.toString(n, k).split("0")) {
            if (!s.isEmpty() && isPrime(Long.parseLong(s))) cnt++;
        }
        return cnt;
    }

    private boolean isPrime(long num) {
        if (num <= 1) return false;
        if (num <= 3) return true;          // 2, 3
        if (num % 2 == 0) return false;     // 짝수 선제거

        for (long i = 3; i * i <= num; i += 2) {   // 홀수만 검사
            if (num % i == 0) return false;
        }
        return true;
    }
}

문제 풀이 후기

split()과 같은 문자열 메서드를 활용할 생각을 하지 못해봤다. 내가 이미 알고 있는 지식들만 하더라도 다방면으로 응용이 가능하며, 엄청난 활용이 가능하다는 것을 깨달을 수 있었다.

문제 풀이

나의 코드

소요 시간: 49분 시간 복잡도: $O(nlogn)$

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int k : scoville) {
            pq.add(k);
        }

        while(pq.peek() < K) {
            if (pq.size() < 2) {
                return -1;
            }
            int key1 = pq.poll();
            int key2 = pq.poll();
            pq.add(key1 + key2 * 2);
            cnt++;
        }

        return cnt;
    }
}

AI 코드

시간 복잡도: $O(nlogn)$

코드 분석

List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toList());

1. .stream()을 이용해 scoville[] 원소가 하나씩 흘러가는 통로를 만듦
2. boxed()를 이용해 IntStream을 Integer 객체로 포장함
3. .collect를 이용해 흘러가는 원소들을 실제 컬렉션에 모아 담음

PriorityQueue<Integer> pq = new PriorityQueue<>(list);   // O(n) heapify

add를 n번 호출 시, 힙 생성 비용은 O(n log n)이지만, 컬렉션을 한번에 받아 O(n)으로 생성이 가능함.

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] scoville, int K) {
        List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toList());
        PriorityQueue<Integer> pq = new PriorityQueue<>(list);   // O(n) heapify

        int cnt = 0;
        while (pq.peek() < K) {
            if (pq.size() < 2) return -1;

            int first = pq.poll();
            int second = pq.poll();
            long mixed = (long) first + (long) second * 2;       // 오버플로 차단
            pq.add((int) Math.min(mixed, Integer.MAX_VALUE));    // K 이상이면 값 자체는 무의미
            cnt++;
        }
        return cnt;
    }
}

문제 풀이 후기

자동 정렬을 해주는 TreeMap으로 해결해보려 했으나 값의 삽입 및 삭제가 용이하지 않아 부적합하다고 판단했음.

문제 풀이

나의 코드

소요 시간: 14분 시간 복잡도: $O(n)$

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] numbers) {
        int len = numbers.length;
        int[] result = new int[len];

        Deque<int[]> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            while(!stack.isEmpty() && numbers[i] > stack.peek()[1]) {
                int[] arr = stack.pop();
                result[arr[0]] = numbers[i];
            }
            stack.push(new int[]{ i, numbers[i] });
        }
        while(!stack.isEmpty()) {
            int[] arr = stack.pop();
            result[arr[0]] = -1;
        }

        return result;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

단조 감소 스택(monotonic stack)을 사용한 동일한 알고리즘이지만, 하나의 배열과 top 변수를 사용하여, 원소마다 배열 객체를 생성하는 나의 코드의 단점을 개선하였다.

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];
        int[] stack = new int[n];   // 인덱스만 저장하는 배열 스택
        int top = 0;                // 스택 크기

        for (int i = 0; i < n; i++) {
            while (top > 0 && numbers[stack[top - 1]] < numbers[i]) {
                answer[stack[--top]] = numbers[i];
            }
            stack[top++] = i;
        }
        while (top > 0) {
            answer[stack[--top]] = -1;
        }

        return answer;
    }
}

문제 풀이 후기

가장 값이 적게 나가는 배열 활용을 1차로 생각해보고, 불가능하다고 생각되면 그 때 라이브러리를 활용해야겠다.

문제 풀이

나의 코드

소요 시간: 1시간 시간 복잡도: $O(1)$

class Solution {
    private String[] alphabet = { "A", "E", "I", "O", "U" };
    private int ans = 0;
    private int cnt = 0;
    public int solution(String word) {
        dfs("", word);

        return ans;
    }
    private void dfs(String s, String word) {
        if (s.length() == 5) {
            return;
        }
        for (int i = 0; i < alphabet.length; i++) {
            cnt++;
            if ((s + alphabet[i]).equals(word)) {
                ans = cnt;
                return;
            }
            dfs(s + alphabet[i], word);
        }
    }
}

AI 코드

시간 복잡도: $O(1)$

코드 분석

수학적인 규칙을 사용하여 각 자릿수마다 가중치를 두고, 한번의 순회로 끝냄

class Solution {
    public int solution(String word) {
        int[] weight = { 781, 156, 31, 6, 1 };
        String alphabet = "AEIOU";
        int answer = 0;

        for (int i = 0; i < word.length(); i++) {
            answer += alphabet.indexOf(word.charAt(i)) * weight[i] + 1;
        }

        return answer;
    }
}

문제 풀이 후기

기본적인 DFS 문제였는데 너무 어렵게 생각해서 이전에 풀었던 코드를 참고해서 해결했다.

수학적인 규칙을 찾으려 했으나, 찾지 못해서 DFS로 해결했다.

문제 풀이

1차 실행 오류

10/100

실패

실패 원인 분석

for (int j = 0; j < reversedArr.length; j++) {
    reversedArr[j] = arr[arr.length - j - 1];
}

에서 잘못된 인덱스 값을 넣고 있던 것이 원인

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

class Solution {
    public int solution(String dirs) {
        int x = 0;
        int y = 0;
        int[] before = new int[2];
        int[] after = new int[2];
        int[] arr = new int[4];
        int[] reversedArr = new int[4];
        Set<String> set = new HashSet<>();

        for (int i = 0; i < dirs.length(); i++) {
            before[0] = x;
            before[1] = y;
            char dir = dirs.charAt(i);

            switch(dir) {
                case 'L': {
                    x = (x > -5 ? x - 1 : -5);
                    break;
                }
                case 'R': {
                    x = (x < 5 ? x + 1 : 5);
                    break;
                }
                case 'U': {
                    y = (y < 5 ? y + 1 : 5);
                    break;
                }
                case 'D': {
                    y = (y > -5 ? y - 1 : -5);
                    break;
                }
            }
            after[0] = x;
            after[1] = y;
            arr[0] = before[0];
            arr[1] = before[1];
            arr[2] = after[0];
            arr[3] = after[1];

            for (int j = 0; j < reversedArr.length; j++) {
                reversedArr[j] = arr[arr.length - j - 1];
            }

            if (arr[0] == arr[2] && arr[1] == arr[3]) {
                continue;
            }
            set.add(Arrays.toString(arr));
            set.add(Arrays.toString(reversedArr));
        }
        return set.size() / 2;
    }
}

나의 코드

소요 시간: 59분 시간 복잡도: $O(N)$

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

class Solution {
    public int solution(String dirs) {
        int x = 0;
        int y = 0;
        int[] before = new int[2];
        int[] after = new int[2];
        int[] arr = new int[4];
        int[] reversedArr = new int[4];
        Set<String> set = new HashSet<>();

        for (int i = 0; i < dirs.length(); i++) {
            before[0] = x;
            before[1] = y;
            char dir = dirs.charAt(i);

            switch(dir) {
                case 'L': {
                    x = (x > -5 ? x - 1 : -5);
                    break;
                }
                case 'R': {
                    x = (x < 5 ? x + 1 : 5);
                    break;
                }
                case 'U': {
                    y = (y < 5 ? y + 1 : 5);
                    break;
                }
                case 'D': {
                    y = (y > -5 ? y - 1 : -5);
                    break;
                }
            }
            after[0] = x;
            after[1] = y;
            arr[0] = before[0];
            arr[1] = before[1];
            arr[2] = after[0];
            arr[3] = after[1];

            reversedArr[0] = arr[2];
            reversedArr[1] = arr[3];
            reversedArr[2] = arr[0];
            reversedArr[3] = arr[1];

            if (arr[0] == arr[2] && arr[1] == arr[3]) { // 이동하지 않았을 때
                continue;
            }
            set.add(Arrays.toString(arr));
            set.add(Arrays.toString(reversedArr));
        }
        return set.size() / 2;
    }
}

AI 코드

시간 복잡도: $O(N)$

코드 분석

로직 자체는 나의 코드와 유사하다.

그러나 Set에 저장할 때에는 바로 문자열 형태로 만들어서 저장하기 때문에 arr[], reversedArr[]를 사용할 필요가 없다.

before[], after[] 또한 배열이 아닌 변수를 그대로 사용하고, 값의 비교 없이 해당 값이 이탈했는지 하지 않았는지만을 판별한다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(String dirs) {
        Set<String> visited = new HashSet<>();
        int x = 0;
        int y = 0;

        for (char c : dirs.toCharArray()) {
            int nx = x;
            int ny = y;

            switch (c) {
                case 'U' -> ny++;
                case 'D' -> ny--;
                case 'L' -> nx--;
                case 'R' -> nx++;
            }

            if (nx < -5 || nx > 5 || ny < -5 || ny > 5) continue; // 좌표 평면 이탈

            // 같은 길을 양방향으로 저장 → 왕복해도 1개로 취급
            visited.add(x + "," + y + "," + nx + "," + ny);
            visited.add(nx + "," + ny + "," + x + "," + y);

            x = nx;
            y = ny;
        }

        return visited.size() / 2;
    }
}

문제 풀이 후기

이미 풀어봐서 익숙한 문제라 그런지 모르겠지만, 전체적인 코드 구조에 대한 알고리즘을 짜는 데에는 큰 어려움이 없다.

그러나 코드가 너무 난잡하다는 문제가 있다. AI 코드처럼 개선의 여지가 분명함에도 문제점을 인식하지 못하고 있다.

잘 짜여진 코드들을 보면서 나의 코드가 어느 부분이 개선 여지가 있는지 판단할 수 있는 눈을 길러야 한다.

문제 풀이

나의 코드

소요 시간: 1시간 42분 시간 복잡도: $O(n)$

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(String str1, String str2) {
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        Map<String, Integer> unionMap = new HashMap<>();

        float union = 0;
        float intersection = 0;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str1.length() - 1; i++) {
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i + 1);
            if (Character.isLetter(c1) && Character.isLetter(c2)) { // 문자일 때
                sb.append(c1);
                sb.append(c2);
                String s = sb.toString().toUpperCase();
                map1.put(s, map1.getOrDefault(s, 0) + 1);
                unionMap.put(s, unionMap.getOrDefault(s, 0) + 1);
                sb.setLength(0);
            }
        }
        for (int i = 0; i < str2.length() - 1; i++) {
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i + 1);
            if (Character.isLetter(c1) && Character.isLetter(c2)) { // 문자일 때
                sb.append(c1);
                sb.append(c2);
                String s = sb.toString().toUpperCase();
                map2.put(s, map2.getOrDefault(s, 0) + 1);
                sb.setLength(0);
            }
            else {
                sb.setLength(0);
            }
        }

        for (String key : map2.keySet()) {
            if (unionMap.get(key) != null) { // 해당 값이 이미 존재할 때
                int n = Math.max(unionMap.get(key), map2.get(key));
                unionMap.put(key, n);
            }
            else {
                unionMap.put(key, map2.get(key));
            }
        }

        for (String key : unionMap.keySet()) {
            union += unionMap.get(key);
        }

        for (String key : map1.keySet()) {
            if (map2.containsKey(key)) {
                intersection = intersection + Math.min(map1.get(key), map2.get(key));
            }
        }

        if (union == 0) {
            return 65536;
        }
        return (int)(intersection / union * 65536);
    }
}

AI 코드

시간 복잡도: $O(n)$ 코드 분석

2개의 알파벳 조합으로 가질 수 있는 경우의 수 26*26크기의 배열을 만들어서 해당하는 인덱스 값을 증감시켰음 해당 배열을 통해 intersection과 union값을 얻어 계산

class Solution {
    private static final int SIZE = 26 * 26;

    public int solution(String str1, String str2) {
        int[] cnt1 = countPairs(str1);
        int[] cnt2 = countPairs(str2);

        int intersection = 0;
        int union = 0;
        for (int i = 0; i < SIZE; i++) {
            intersection += Math.min(cnt1[i], cnt2[i]);
            union        += Math.max(cnt1[i], cnt2[i]);
        }

        if (union == 0) {                 // 두 집합 모두 공집합 → J = 1
            return 65536;
        }
        return intersection * 65536 / union;   // 정수 나눗셈 = 절삭, 오차 없음
    }

    private int[] countPairs(String s) {
        int[] cnt = new int[SIZE];
        for (int i = 0; i < s.length() - 1; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            if (isAlpha(a) && isAlpha(b)) {
                int idx = (toUpper(a) - 'A') * 26 + (toUpper(b) - 'A');
                cnt[idx]++;
            }
        }
        return cnt;
    }

    private boolean isAlpha(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }

    private char toUpper(char c) {
        return (c >= 'a' && c <= 'z') ? (char) (c - 32) : c;
    }
}

문제 풀이 후기

이전부터 느끼는 점이지만 AI는 배열의 활용을 정말 잘 하는 것 같다. 26 * 26 크기의 배열만 하더라도 생각지도 못한 방향이었다.

나의 코드에서 개선점이 꽤나 많이 보여졌다.

첫번째, float의 사용 대신 intersection에 65536을 먼저 곱한 후 union으로 나누어 리턴했으면 더 안전하게 연산이 가능하다.

둘째, else sb.setLength(0) 구문이 필요가 없다. sb.append()는 if문 안에서만 하고 있기 때문이다.

셋째, unionMap이 필요하지 않다. sets1.size() + sets2.size() - intersection으로 union을 바로 얻을 수 있다. 수학이 중요한 이유

넷째, isLetter()는 é나 한글의 경우에도 true를 리턴하기 때문에 알파벳 범위를 벗어나게 된다. 따라서 'a'~'z', 'A'~'Z' 범위 검사가 더 적합하다.

다섯째, unionMap.get(key) != null보다는 위에서 사용한 코드인 containsKey()를 사용하는 것이 더 적합하다.

코드를 작성하면서 값이 제대로 나오지 않아, 리턴값을 intersection, union 만도 사용해보면서 오류 후보를 좁혀나갔다.

해당 방식으로 하나하나 어떤 부분에 오류가 있는지 천천히 탐색하면 오늘처럼 AI를 사용하지 않고 스스로 문제를 해결할 수 있을 것이다.

문제 풀이

나의 코드

소요 시간: 1시간 8분 시간 복잡도: $O(n^2)$

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int[] solution(String s) {
        Map<Integer, Integer>map = new HashMap<>();

        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(2));

        for (int i = 3; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '{' && c != '}' && c != ',') { // 숫자일 때,
                sb.append(c);
            }
            if (sb.length() > 0 && (c == '}' || c == ',')) {
                Integer n = Integer.parseInt(sb.toString());
                map.put(n, map.getOrDefault(n, 0) + 1);
                sb.delete(0, sb.length());
            }
        }
        int[] result = new int[map.size()];
        int idx = 0;
        while(!map.isEmpty()) {
            int maxKey = 0;
            int maxValue = 0;

            for (Integer key : map.keySet()) {
                if (map.get(key) > maxValue) {
                    maxKey = key;
                    maxValue = map.get(key);
                }
            }
            map.remove(maxKey);
            result[idx++] = maxKey;
        }
        return result;
    }
}

AI 코드

시간 복잡도: $O(n^2)$

코드 분석

num * 10 + (c - '0')을 이용하여 int만을 이용해 숫자 누적

merge(num, 1, Integer::sum)은 put(n, getOrDefault(n, 0) + 1)과 동일

reading이라는 boolean 변수를 두어 숫자가 저장되어 있는지 판별

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(String s) {
        Map<Integer, Integer> freq = new HashMap<>();

        int num = 0;
        boolean reading = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');   // 자릿수 누적
                reading = true;
            } else if (reading) {             // 숫자가 끝나는 지점
                freq.merge(num, 1, Integer::sum);
                num = 0;
                reading = false;
            }
        }

        return freq.entrySet().stream()
                   .sorted((a, b) -> b.getValue() - a.getValue())  // 등장 횟수 내림차순
                   .mapToInt(Map.Entry::getKey)
                   .toArray();
    }
}

문제 풀이 후기

간단한 변수 추가로 코드를 훨씬 더 간단하게 만드는 방법을 사용하니 코드가 훨씬 더 깔끔하게 보이고 가독성이 좋아졌다.

마지막에 정렬 하는 부분은 strea()을 이용하여 정렬했는데, 해당 부분이 이해가 잘 안돼서 반복적으로 의식하고 해당 코드를 사용할 수 있을 때 앞으로 사용해야겠다는 생각이 들었다.

문제 풀이

1차 실행 오류

실패 원인 분석 sum + numbers[i]의 과정에서 visited[i] = true후, sum - numbers[i]의 과정에서 visited[i] == true 이기 때문에 값을 빼는 경우의 dfs가 동작하지 않음

또한 타겟 넘버는 모든 숫자를 다 더하거나 뺐을 경우에만 카운트해야 하는데, 해당 코드의 경우 중간 부분합의 경우도 더함

class Solution {
    private boolean[] visited;
    private int result = 0;
    public void dfs(int[] numbers, int sum, int target) {
        if (sum == target) {
            result++;
        }
        for (int i = 0; i < numbers.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            dfs(numbers, sum + numbers[i], target);
            dfs(numbers, sum - numbers[i], target);
        }
    }
    public int solution(int[] numbers, int target) {
        int len = numbers.length;
        visited = new boolean[len];
        dfs(numbers, 0, target);

        return result;
    }
}

AI 코드

class Solution {
    private int answer = 0;

    private void dfs(int[] numbers, int idx, int sum, int target) {
        if (idx == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        dfs(numbers, idx + 1, sum + numbers[idx], target);
        dfs(numbers, idx + 1, sum - numbers[idx], target);
    }

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, 0, target);
        return answer;
    }
}

문제 풀이 후기

이번 문제는 해결하지 못했다.

처음 공부할 때에도 재귀함수에 대해 큰 어려움이 있었고, 여전히 재귀함수에 대한 어려움이 있다.

나의 코드를 다시 한번 분석해보면, 근본적으로 코드에서 사용한 visited[] 를 사용할 필요가 없었다는 것이다. 위의 실패 원인에서 서술한 것 처럼 처음 visited[i] == true를 한 후, +연산과 -연산을 진행하게 되는데, 재귀적으로 진행하며 - 연산을 진행하지 않는 데에 있다.

문제 풀이

나의 코드

소요 시간: 51분 시간 복잡도: O(N x M)

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    private int row;
    private int col;
    private boolean[][] visited;

    public int bfs(int[][] maps) {
        Deque<int[]> queue = new ArrayDeque<>();

        queue.offer(new int[] {0, 0, 1}); // 행, 열, 이동거리

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();

            if (cur[0] == (row - 1) && cur[1] == (col - 1)) {
                return cur[2];
            }
            int[][] move = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

            for (int[] m : move) {
                int r = cur[0] + m[0];
                int c = cur[1] + m[1];
                if (r >= row || c >= col || r < 0 || c < 0) {
                    continue;
                }
                else {
                    if (maps[r][c] == 0 || visited[r][c]) {
                        continue;
                    }
                    else {
                        queue.offer(new int[] {r, c, cur[2] + 1});
                        visited[r][c] = true;
                    }
                }
            }
        }
        return -1;
    }

    public int solution(int[][] maps) {
        row = maps.length;
        col = maps[0].length;
        visited = new boolean[row][col];
        int answer = bfs(maps);

        return answer; 
    }     
}

AI 코드

시간 복잡도: O(N x M)

코드 분석

전체적인 구조는 동일

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

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

        boolean[][] visited = new boolean[n][m];
        Deque<int[]> queue = new ArrayDeque<>();

        queue.offer(new int[] {0, 0, 1});   // 행, 열, 이동 거리
        visited[0][0] = true;               // 시작점 방문 처리

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], dist = cur[2];

            if (r == n - 1 && c == m - 1) {
                return dist;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d];
                int nc = c + DC[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (maps[nr][nc] == 0 || visited[nr][nc]) continue;

                visited[nr][nc] = true;     // 큐에 넣는 시점에 방문 처리 (중복 삽입 방지)
                queue.offer(new int[] {nr, nc, dist + 1});
            }
        }
        return -1;
    }
}

문제 풀이 후기

나의 코드에 존재하는 3가지 문제 및 개선점이 존재함

• 기존 나의 코드에서 시작 위치인 visited[0][0] = true를 하지 않아 (0, 0)이 거리 3으로 다시 큐에 들어가는 오류가 발생

  시작 지점의 미방문 처리는 BFS에서 가장 흔한 감점/오답 포인트임

• move 배열을 while 루프 안에서 매번 재생성 하고 있음

• else 중첩 + continue가 섞여 있어 depth가 깊음

BFS는 DFS에 비해 상대적으로 문제 유형이 자주 출제되지 않았기에 해당 자료구조에 대해 사용했던 적이 적었다.

이 문제는 이전에 DFS로 해결을 시도했다가 실패했던 문제인데 이번에는 BFS로 한 번에 해결하고 익숙하지 않았던 BFS에 대해 다시 한번 복습할 수 있어서 좋았다.

문제 풀이

나의 코드

소요 시간: 19분 시간 복잡도: $O(n)$

개선점

Integer t = topping[i];

의 과정에서 오토 언박싱이 지속적으로 발생함 int로 선언 후, put 시점에만 박싱되게 하는 것이 나음

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] topping) {
        int result = 0;
        Map<Integer, Integer> right = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>();

        for (int i = 0; i < topping.length; i++) {
            Integer t = topping[i];
            right.put(t, right.getOrDefault(t, 0) + 1);
        }
        for (int i = 0; i < topping.length; i++) {
            Integer t = topping[i];
            left.put(t, left.getOrDefault(t, 0) + 1);
            right.put(t, right.get(t) - 1);
            if (right.get(t) <= 0) {
                right.remove(t);
            }
            if (left.size() == right.size()) {
                result++;
            }
        }
        return result;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

right는 개수가 계속 빠지므로 rightCnt를 사용하고,

left는 개수가 빠지지 않으므로, leftHas를 이용하여 이미 가지고 있던 토핑인지 구분한다.

class Solution {
    public int solution(int[] topping) {
        int[] rightCnt = new int[10001];
        boolean[] leftHas = new boolean[10001];
        int leftKind = 0, rightKind = 0, answer = 0;

        for (int t : topping) {
            if (rightCnt[t]++ == 0) rightKind++;
        }

        // i번째까지 철수, 나머지 동생 → 마지막 인덱스는 자를 수 없으므로 제외
        for (int i = 0; i < topping.length - 1; i++) {
            int t = topping[i];
            if (--rightCnt[t] == 0) rightKind--;
            if (!leftHas[t]) {
                leftHas[t] = true;
                leftKind++;
            }
            if (leftKind == rightKind) answer++;
        }
        return answer;
    }
}

문제 풀이 후기

배열의 길이가 1,000,000 이하인 조건을 보고, 2중 반복문을 사용하면 안된다는 것을 이전의 문제를 풀면서 알아냈다.

이전에는 고려하지 않고 일단 코드 작성 뒤 시간 초과 오류가 났을 부분이지만, 이전과는 달리 한 번에 통과하여 발전하고 있는 자신이 보기 좋다.

문제 풀이

나의 코드

소요 시간: 37분 시간 복잡도: $O(n^3)$

import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        int maxIdx = 0;
        int len = priorities.length;
        for (int i = 1; i < len; i++) {
            if (priorities[maxIdx] < priorities[i]) {
                maxIdx = i;
            }
        }
        int order = 1;
        int idx = maxIdx;
        while(true) {
            while(true) {
                int p = priorities[idx];
                boolean isExist = Arrays.stream(priorities).anyMatch(a -> a > p);
                if (!isExist) {
                    priorities[idx] = -1;
                    break;
                }
                idx = (idx + 1) % len;
            }
            if (idx == location) {
                break;
            }
            idx = (idx + 1) % len;
            order++;
        }
        return order;
    }
}

AI 코드

시간 복잡도: $O(n^2)$

코드 분석

인덱스와 우선순위의 분리 인덱스는 queue, 우선순위는 sorted[]로 각각 분리하여 관리

우선순위의 경우 .sort()를 이용해 오름차순으로 정렬 후, top값을 이용한 가장 후방의 인덱스부터 시작하여 내림차순처럼 사용함

인덱스의 경우 계속해서 순환하는 흐름을 만들어냄 0부터 시작하여 해당 인덱스에 해당하는 값이 soted[top]의 값과 동일한 경우, 현재 가장 높은 우선순위를 갖는 값이 된다.

두 값이 일치되면 top--를 하여 location과 일치할 때 까지 반복해서 진행한다.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int solution(int[] priorities, int location) {
        int n = priorities.length;

        // 오름차순 정렬 후 뒤에서부터 꺼내면 = 남은 문서 중 최대 우선순위
        int[] sorted = priorities.clone();
        Arrays.sort(sorted);
        int top = n - 1;

        // 원래 인덱스를 큐에 담아 대기열 순서 유지
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i);
        }

        int order = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (priorities[cur] == sorted[top]) {   // 최우선순위 → 인쇄
                top--;
                order++;
                if (cur == location) {
                    return order;
                }
            } else {                                // 뒤로 밀기
                queue.offer(cur);
            }
        }
        return order;
    }
}

문제 풀이 후기

나의 코드에서 anyMatch()를 사용하여 해당 값보다 더 큰 값이 있는지 탐색을 했기 때문에 maxIdx를 탐색하여 사용할 필요가 없었다.

이와 같이 코드의 개선점이 뚜렷하게 보였다.

두 번째로 AI 코드를 보며 든 생각이 있다. 예전부터 수학 시험을 보면, 기본 문제나 문제집에서 이미 풀어봤던 문제는 잘 풀었지만, 응용 문제의 경우에는 처음부터 막혀서 항상 풀지 못했다.

코딩도 마찬가지로 기본적인 사용은 쉽게 가능하지만, 위의 AI 코드와 같이 응용을 해서 사용한다는 발상 자체가 떠오르지 않는다.

문제집에서 풀어 봤던 문제는 잘 푸는 것 처럼 이와 같은 응용된 코드를 많이 보면서 부족한 코드의 응용을 하는 방법에 익숙해지는 수 밖에 없다.

문제 풀이

1차 실행 오류

79.2/100

실패 및 시간 초과

실패 원인 분석

123, 12 순서의 배열에서 12는 123으로 시작하지 않지만, 123은 12로 시작하는 경우를 고려하지 않음

class Solution {
    public boolean solution(String[] phone_book) {
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = i + 1; j < phone_book.length; j++) {
                if (phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

2차 실행 오류

91.7/100

시간 초과

시간 초과 원인 분석

1 <= phone_book <= 1,000,000 이므로 2중 for문을 사용하면 안됨

class Solution {
    public boolean solution(String[] phone_book) {
        if (phone_book.length <= 1) {
            return true;
        }

        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book.length; j++) {
                if (i == j) {
                    continue;
                }
                if (phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

나의 코드

소요 시간: 31분 시간 복잡도: $O(n log n)$

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        if (phone_book.length <= 1) {
            return true;
        }

        for (int i = 1; i < phone_book.length; i++) {
            if (phone_book[i].startsWith(phone_book[i - 1]) || 
                phone_book[i - 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

HashSet의 .contains()의 조회 속도가 $O(1)$이라는 점을 이용하여 해결

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();
        for (String number : phone_book) {
            set.add(number);
        }

        for (String number : phone_book) {
            for (int i = 1; i < number.length(); i++) {
                if (set.contains(number.substring(0, i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

문제 풀이 후기

substring()과 contains()의 혼합 사용은 생각하지 못했다. Hash의 활용 방법은 무궁무진 하다는 생각이 들었다.

이전에 해결하지 못했던 시간 초과 오류를 AI를 활용하지 않고 스스로 원인 분석 및 해결했다는 점에서 높은 점수를 주고 싶다.

문제 풀이

1차 실행 오류

90/100

실패

실패 원인 분석

cacheSize == 0일 때, 캐시에 하나의 데이터가 저장이 되는 경우의 수를 고려하지 않음

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int runTime = 0;
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < cities.length; i++) {
            for (String key : map.keySet()) { // 캐시 갱신
                map.put(key, map.get(key) + 1);
            }

            String city = cities[i].toUpperCase();
            if (map.get(city) == null) { // cache miss 일 때
                runTime += 5;
                if (map.size() >= cacheSize) { // cache가 다 찼을 때
                    String removeCity = "s";
                    int min = 0;
                    for (String key : map.keySet()) {
                        if (map.get(key) > min) {
                            removeCity = key;
                            min = map.get(key);
                        }
                    }
                    map.remove(removeCity); // 가장 오래 전에 사용한 캐시 삭제
                }
                map.put(city, 0); // 새로운 캐시 삽입
            }
            else {
                runTime++;
                map.put(city, 0); // 사용한 캐시 초기화
            }
        }
        return runTime;
    }
}

나의 코드

소요 시간: 23분 시간 복잡도: $O(n)$

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return 5 * cities.length;
        }
        int runTime = 0;
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < cities.length; i++) {
            for (String key : map.keySet()) { // 캐시 갱신
                map.put(key, map.get(key) + 1);
            }

            String city = cities[i].toUpperCase();
            if (map.get(city) == null) { // cache miss 일 때
                runTime += 5;
                if (map.size() >= cacheSize) { // cache가 다 찼을 때
                    String removeCity = "s";
                    int min = 0;
                    for (String key : map.keySet()) {
                        if (map.get(key) > min) {
                            removeCity = key;
                            min = map.get(key);
                        }
                    }
                    map.remove(removeCity); // 가장 오래 전에 사용한 캐시 삭제
                }
                map.put(city, 0); // 새로운 캐시 삽입
            }
            else {
                runTime++;
                map.put(city, 0); // 사용한 캐시 초기화
            }
        }
        return runTime;
    }
}

AI 코드

시간 복잡도: $O(n)$

코드 분석

LinkedList를 사용하여 순서를 유지한 채 해시를 유지 캐시가 사용되면 기존 캐시를 뺀 후 재삽입

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return 5 * cities.length;

        int runTime = 0;
        LinkedList<String> cache = new LinkedList<>();

        for (String city : cities) {
            String upper = city.toUpperCase();
            if (cache.remove(upper)) {   // hit: 기존 원소 제거 후 뒤에 재삽입
                runTime += 1;
            } else {                     // miss
                runTime += 5;
                if (cache.size() >= cacheSize) {
                    cache.pollFirst();   // 가장 오래된 것 제거 (LRU)
                }
            }
            cache.addLast(upper);        // 최근 사용으로 갱신
        }
        return runTime;
    }
}

문제 해결 후기

익숙하지 않았던 해시 사용을 점점 능숙하게 사용하고 있다는 생각이 든다. 동시에 LinkedList와 같은 다양한 해시들도 고루고루 활용해가며 적재적소에 활용하는 능력을 키워야겠다고 생각했다.

문제 풀이

나의 코드

소요 시간: 20분 시간 복잡도: $O(n!) (n = 던전 개수)$

class Solution {
    boolean[] visited;
    int result = 0;
    public void dfs(int k, int[][] dungeons, int cnt) {
        result = Math.max(result, cnt);
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] || dungeons[i][0] > k) {
                continue;
            }
            visited[i] = true;
            dfs(k - dungeons[i][1], dungeons, cnt + 1);
            visited[i] = false;
        }
    }

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(k, dungeons, result);

        return result;
    }
}

AI 코드

시간 복잡도: $O(n!) (n = 던전 개수)$

코드 분석

전체적인 코드 구조는 거의 동일하고 가독성 측면에서 일부 변경되었음.

class Solution {
    static int answer = 0;
    static boolean[] visited;

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(k, 0, dungeons);
        return answer;
    }

    private void dfs(int k, int depth, int[][] dungeons) {
        answer = Math.max(answer, depth);
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;
                dfs(k - dungeons[i][1], depth + 1, dungeons);
                visited[i] = false;
            }
        }
    }
}

문제 풀이 후기

이 문제를 처음 풀었을 때에는 dfs에 대한 활용이 많이 부족했다.

복습을 하면서 아주 쉽게 문제를 해결했는데 이전보다 실력이 나아진 것은 분명하나, 문제 해결 방법을 외워서 푼 것 같아 다른 문제들도 계속 풀어보며 점점 고난이도의 문제들을 해결하는 것이 필요할 것 같다.

틀렸던 문제들에 대해 복습을 반복하며 내가 어떤 점이 부족했고 보완해야 하는가를 깨닫고, 정답률이 낮은 고난이도 문제들과 더불어 Level 3의 문제들을 도전해가는 방향으로 진행하면 실력 향상이 이루어질 것이다.

문제 풀이

1차 실행 오류

6.3/100

실패

실패 원인 분석

[7, 0, 3]의 배열이 입력으로 주어지는 경우,
정답이 2가 되어야 하지만, 1이 출력되는데, 그 이유는

for (int i = 0; i < citations.length; i++) {
    for (Integer key : map.keySet()) {
        if (key < citations[i]) {
            map.put(key, map.get(key) + 1);
        }
    }
map.put(citations[i], map.getOrDefault(citations[i], 0) + 1);
}

에서 큰 인용 횟수가 먼저 들어오면, 작은 횟수는 증가하지 않기 때문임

따라서 오름차순으로 정렬해서 해결할 수 있음

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] citations) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < citations.length; i++) {
            for (Integer key : map.keySet()) {
                if (key < citations[i]) {
                    map.put(key, map.get(key) + 1);
                }
            }
            map.put(citations[i], map.getOrDefault(citations[i], 0) + 1);
        }
        int h = 0;
        for (Integer key : map.keySet()) {
            int n = Math.min(key, map.get(key));
            h = (h <= n ? n : h);
        }

        return h;
    }
}

나의 코드

소요 시간: 30분 시간 복잡도: $O(n^2)$

import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < citations.length; i++) {
            for (Integer key : map.keySet()) {
                if (key < citations[i]) {
                    map.put(key, map.get(key) + 1);
                }
            }
            map.put(citations[i], map.getOrDefault(citations[i], 0) + 1);
        }
        int h = 0;
        for (Integer key : map.keySet()) {
            int n = Math.min(key, map.get(key));
            h = (h <= n ? n : h);
        }

        return h;
    }
}

AI 코드

시간 복잡도: $O(n log n)$

코드 해석

입력된 배열을 오름차순으로 정렬했기 때문에
cirtations[i]의 현재 인덱스로부터 총 길이까지는 차는
현재 상황에서 인용 가능한 최대 논문 수가 됨

따라서 현재 인용한 논문 횟수가 이보다 더 크다면 해당 값이 최댓값이 되는 구조

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        for (int i = 0; i < n; i++) {
            int h = n - i;               // i번째 이후 논문 수
            if (citations[i] >= h) return h;
        }
        return 0;
    }
}

문제 풀이 후기

이전 문제를 풀면서도 느꼈던 점이지만, 이번 AI 코드를 보며 더욱 더 수학적 사고방식이 정말 중요하다고 느낀다.

해당 사고방식이 있다면 같은 문제라도 코드가 훨씬 더 간결해진다. 결론적으로 문제를 많이 풀며 모범 답안을 많이 접하는 것 밖에는 정답이 없다.