프로그래머스LV2_16

k진수에서 소수 구하기

접근 과정

1. 문제의 조건을 곰곰히 생각해보면 진수 변환 후 0으로 분리하면 되는 것이라고 판단
2. n을 k진수 문자열로 바꾸어 0으로 분리하여 배열로 만듦
3. 분리된 수가 소수인지 판별하여 answer을 늘리면 해결

시행착오

• 런타임 에러가 나서 곰곰히 생각해보니 진수 변환을 했을 때 너무 길어지면 Integer로 받을 수 없었다.

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String number = Integer.toString(n, k);
        String[] numbers = number.split("0");
        for(String num : numbers){
            if(num.length() == 0) continue;
            if(isPrime(Integer.parseInt(num))) answer++;
        }
        return answer;
    }
    
    private boolean isPrime(int num){
        if(num == 1 || num == 0) return false;
        if(num == 2 || num == 3) return true;
        for(int i = 2; i <= (int)Math.sqrt(num); i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}

해결 코드

• 긴 문자열을 숫자로 변환하기 위해 Long형으로 변환하여 해결
• 자료형을 잘 생각하자!

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String number = Integer.toString(n, k);
        String[] numbers = number.split("0");
        for(String num : numbers){
            if(num.length() == 0) continue;
            if(isPrime(Long.parseLong(num))) answer++;
        }
        return answer;
    }
    
    private boolean isPrime(long num){
        if(num == 1 || num == 0) return false;
        if(num == 2 || num == 3) return true;
        for(long i = 2; i <= (long)Math.sqrt(num); i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(진법 변환 문자열 길이를 L, 변환된 개별 숫자를 N)

• 공간 복잡도

주식 가격

접근 과정

1. 해당 시작 지점에서 가격이 떨어질 때까지 시간을 측정
2. 다음에 바로 떨어져도 1초이므로 먼저 시간을 늘리고 멈춤

시행착오

• 시행착오 없이 해결

해결 코드

• 접근 과정대로 구현하여 해결

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length - 1; i++){
            for(int j = i + 1; j < prices.length; j++){
                answer[i]++;
                if(prices[j] < prices[i]){
                    break;
                }
            }
        }
        answer[answer.length - 1] = 0;
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(주식 가격 배열의 길이를 N)

• 공간 복잡도

개선

• O(N^2) 풀이라 제한 사항이 더 커지면 시간 초과가 날 것이라고 판단하여 이전에 C++로 풀었던 풀이를 보고 스택으로 개선해보았다.
• 시간 복잡도 : O(N)

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!dq.isEmpty() && prices[dq.peek()] > prices[i]){
                int prev = dq.pop();
                answer[prev] = i - prev;
            }
            dq.push(i);
        }
        while (!dq.isEmpty()) {
            int prev = dq.pop();
            answer[prev] = n - 1 - prev;
        }
        return answer;
    }
}

땅따먹기

접근 과정

1. 열은 4개로 고정이라 행의 개수만 시간 복잡도에 고려하면 된다.
2. dp를 활용하여 현재 선택된 열에서 해당 열이 아닌 이전 행의 값을 더한 최댓값으로 갱신
3. 마지막 행 중 최댓값을 반환하여 해결

시행착오

• dfs로 풀었는데 시간 복잡도가 지수 승이 되어서 시간 초과가 났다.

class Solution {
    int answer = 0;
    
    int solution(int[][] land) {
        dfs(land, 0, 0, 0);
        return answer;
    }
    
    void dfs(int[][] land, int prev, int cur, int sum){
        if(cur == land.length){
            answer = Math.max(answer, sum);
            return;
        }
        for(int i = 0; i < land[cur].length; i++){
            if(i != prev){
                dfs(land, i, cur + 1, sum + land[cur][i]);
            }
        }
    }
}

해결 코드

• dfs 풀이에서 시간 복잡도를 줄이기 위해 dp를 활용하여 해결

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int r = land.length, c = land[0].length;
        int[][] dp = new int[r][c];
        for(int i = 0; i < c; i++){
            dp[0][i] = land[0][i];
        }
        for(int i = 1; i < r; i++){
            for(int j = 0; j < c; j++){
                for(int k = 0; k < c; k++){
                    if(k != j){
                        dp[i][j] = Math.max(dp[i][j] , dp[i - 1][k] + land[i][j]);
                    }
                }
            }
        }
        for(int i = 0; i < c; i++){
            answer = Math.max(dp[r - 1][i], answer);
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도

• 공간 복잡도

개선

• 생각해보면 열이 4개로 고정이라 굳이 3중 for문을 할 필요가 없다!
• 단순 3개 비교로 개선

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        for(int i = 1; i < land.length; i++){
            land[i][0] += Math.max(land[i -1][1], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][1] += Math.max(land[i -1][0], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][2] += Math.max(land[i -1][0], Math.max(land[i - 1][1], land[i - 1][3]));
            land[i][3] += Math.max(land[i -1][0], Math.max(land[i - 1][1], land[i - 1][2]));
        }
        for(int i = 0; i < 4; i++){
            answer = Math.max(answer, land[land.length - 1][i]);
        }
        return answer;
    }
}

n진수 게임

접근 과정

1. 숫자 0부터 t개를 말할 수 있는 충분한 길이의 n진수 문자열을 만든다.
2. 시작 순서부터 해당 인원만큼 점프하면서 해당 인덱스의 값을 붙여 반환하면 해결

시행착오

• 문제를 잘못 이해하여 t개의 숫자에서 말하는 수를 반환하는 것으로 착각했다.
• 문제 접근을 위해 AI를 활용하였다.

해결 코드

• t개를 말할 수 있도록 충분한 길이를 수를 만들고 거기서 맞는 인덱스의 값을 붙이면 된다.

class Solution {
    public String solution(int n, int t, int m, int p) {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        while(sb.length() < t * m){
            sb.append(Integer.toString(num++, n).toUpperCase());
        }
        StringBuilder answer = new StringBuilder();
        for(int i = p - 1; i < sb.length(); i += m){
            answer.append(sb.charAt(i));
            if(answer.length() == t){
                break;
            }
        }
        return answer.toString();
    }
}

시간 및 공간 복잡도

• 시간 복잡도(미리 구해야 하는 숫자의 개수 t, 인원수 m)

• 공간 복잡도

압축

접근 과정

1. 사전에 A-Z를 맵에 저장
2. msg를 크기를 늘리면서 잘라 맵에 포함 여부에 따라 3-4를 수행
3. 맵에 있으면 찾은 단어와 마지막 인덱스를 갱신
4. 맵에 없다면 맵에 자른 단어를 추가
5. answer에 찾은 단어의 값을 맵에서 찾아 추가
6. 바깥 for문의 인덱스를 마지막 인덱스로 갱신

시행착오

• 인덱스를 무조건 1씩 늘어난다고 잘못 생각
• 인덱스는 맵에 없는 마지막 인덱스의 위치로 갱신해야 함

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Integer> m = new HashMap<>();
        char word = 'A';
        for(int i = 0; i < 26; i++){
            m.put(Character.toString(word++), i + 1);
        }
        int idx = 27;
        for(int i = 0; i < msg.length(); i++){
            String w = "";
            int lastIdx = 0;
            for (int j = i; j < msg.length(); j++) {
                String next = msg.substring(i, j + 1);
                if(m.containsKey(next)){
                    w = next;
                    lastIdx = j;
                }
                else{
                    m.put(next, idx++);
                    break;
                }
            }
            answer.add(m.get(w));
            i = lastIdx;
        }
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

시간 및 공간 복잡도

• 시간 복잡도(메시지 길이를 N, 사전의 최종 크기를 K)

• 공간 복잡도

택배 상자

접근 과정

1. 마지막에 들어온 박스부터 뺄 수 있으므로 스택을 사용
2. 일단 들어온 박스에 스택에 넣음
3. 스택의 위가 order의 해당 인덱스의 박스이면 pop하고 인덱스를 늘림
4. 3번을 스택이 비거나 위가 해당 인덱스의 박스일 때까지 반복

시행착오

• 시행착오 없이 해결

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        int idx = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 1; i <= order.length; i++) {
            st.push(i);
            while (!st.isEmpty() && st.peek() == order[idx]) {
                st.pop();
                answer++;
                idx++;
            }
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(상자의 총 개수를 N)

• 공간 복잡도

숫자 변환하기

접근 과정

1. 모든 경우를 관리해야 하므로 BFS를 활용 생각
2. 큐를 선언하여 x를 시작점으로 넣고 방문 체크를 위한 배열을 선언하여 x를 방문 처리
3. 큐에서 꺼내 현재 지점이 y이면 현재 횟수를 반환
4. y가 아니라면 2배, 3배, n을 더한 것이 y보다 작은지 체크하여 큐에 추가하고 방문 처리
5. 큐가 빌 때까지 반환이 안됐으면 안되는 것으로 -1 반환

시행착오

• 처음에 방문 체크를 놓쳐서 시간 초과가 났다.

import java.util.*;

class Solution {
    class Cur {
        int cur;
        int cnt;
        Cur(int cur, int cnt){
            this.cur = cur;
            this.cnt = cnt;
        }
    }
    
    public int solution(int x, int y, int n) {
        int answer = 0;
        Queue<Cur> q = new LinkedList<>();
        q.add(new Cur(x, 0));
        while(!q.isEmpty()){
            Cur c = q.poll();
            if(c.cur == y){
                return c.cnt;
            }
            if(c.cur * 2  <= y){
                q.add(new Cur(c.cur * 2, c.cnt + 1));
            }
            if(c.cur * 3  <= y){
                q.add(new Cur(c.cur * 3, c.cnt + 1));
            }
            if(c.cur + n  <= y){
                q.add(new Cur(c.cur + n, c.cnt + 1));
            }
        }
        return -1;
    }
}

해결 코드

• 배열로 방문 체크하여 해결

import java.util.*;

class Solution {
    class Cur {
        int cur;
        int cnt;
        Cur(int cur, int cnt){
            this.cur = cur;
            this.cnt = cnt;
        }
    }
    
    public int solution(int x, int y, int n) {
        int answer = 0;
        Queue<Cur> q = new LinkedList<>();
        boolean[] visited = new boolean[y + 1];
        q.add(new Cur(x, 0));
        visited[x] = true;
        while(!q.isEmpty()){
            Cur c = q.poll();
            if(c.cur == y){
                return c.cnt;
            }
            if(c.cur * 2  <= y && !visited[c.cur * 2]){
                visited[c.cur * 2] = true;
                q.add(new Cur(c.cur * 2, c.cnt + 1));
            }
            if(c.cur * 3  <= y && !visited[c.cur * 3]){
                visited[c.cur * 3] = true;
                q.add(new Cur(c.cur * 3, c.cnt + 1));
            }
            if(c.cur + n  <= y && !visited[c.cur + n]){
                visited[c.cur + n] = true;
                q.add(new Cur(c.cur + n, c.cnt + 1));
            }
        }
        return -1;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(목표 숫자 y의 크기를 Y)

• 공간 복잡도

개선

• 큐에 매번 new를 하면 객체 생성 비용이 발생하므로 다른 방식으로 개선
• 횟수를 저장하는 DP 방식을 섞으면 매번 객체 생성이 없고 좀 더 가독성 있게 해결 가능

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        if (x == y) return 0;
        int[] dist = new int[y + 1];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(x);
        while (!q.isEmpty()) {
            int cur = q.poll();
            int[] nexts = {cur + n, cur * 2, cur * 3};
            for (int next : nexts) {
                if (next == y) return dist[cur] + 1;
                if (next < y && dist[next] == 0) {
                    dist[next] = dist[cur] + 1;
                    q.add(next);
                }
            }
        }
        return -1;
    }
}