프로그래머스LV2_15

방문 길이

접근 과정

1. 방문한 길의 방향은 중요하지 않으므로 지나간 길을 체크하기 위해 Set 자료구조를 생각
2. UDRL에 따라 좌표를 옮기고 이미 방문한 루트인지 체크하여 answer를 늘리면 해결
3. 이미 좌표 끝이면 이동하지 않고 비교도 하지 않는 것을 고려

시행착오

• 처음에 클래스를 만들어서 시작 지점과 도착 지점을 받아서 Set에 넣으려고 했는데 생각해보니 그러면 서로 비교가 안되므로 String으로 만들어 해결했다.

해결 코드

• 접근 과정대로 Set과 문자열로 저장하여 해결

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        int x = 0, y = 0;
        Set<String> s = new HashSet<>();
        for(char c : dirs.toCharArray()){
            switch(c) {
                case 'U' -> {
                    if(y >= 5) continue;
                    int ny = y + 1;
                    if(move(s, x, y, x, ny)) answer++;
                    y = ny;
                }
                case 'D' -> {
                    if(y <= -5) continue;
                    int ny = y - 1;
                    if(move(s, x, y, x, ny)) answer++;
                    y = ny;
                }
                case 'R' -> {
                    if(x >= 5) continue;
                    int nx = x + 1;
                    if(move(s, x, y, nx, y)) answer++;
                    x = nx;
                }
                case 'L' -> {
                    if(x <= -5) continue;
                    int nx = x - 1;
                    if(move(s, x, y, nx, y)) answer++;
                    x = nx;
                }
            }
        }
        return answer;
    }
    
    boolean move(Set<String> s, int x, int y, int nx, int ny){
        String dir1 = x + "," + y + "," + nx + "," + ny;
        String dir2 = nx + "," + ny + "," + x + "," + y;
        if(s.contains(dir1) || s.contains(dir2)) return false;
        s.add(dir1);
        s.add(dir2);
        return true;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(문자열 dirs의 길이를 N)

• 공간 복잡도(문자열 dirs의 길이를 N)

개선

• 자료구조를 사용하지 않고 해결할 수 있어 개선해보았다.
• boolean 4차원 배열을 활용하고 시작 지점을 5, 5로 만들면 -5가 되어도 0이므로 괜찮다.
• 매번 문자열을 생성하지 않고 비교하므로 속도가 더 빠르다.

import java.util.*;

class Solution {
    public int solution(String dirs) {
        boolean[][][][] visited = new boolean[11][11][11][11];
        int x = 5, y = 5;
        int answer = 0;
        for (char c : dirs.toCharArray()) {
            int nx = x, ny = y;
            if (c == 'U') ny++;
            else if (c == 'D') ny--;
            else if (c == 'R') nx++;
            else if (c == 'L') nx--;
            if (nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;
            if (!visited[x][y][nx][ny] && !visited[nx][ny][x][y]) {
                visited[x][y][nx][ny] = true;
                visited[nx][ny][x][y] = true;
                answer++;
            }
            x = nx; y = ny;
        }
        return answer;
    }
}

뒤에 있는 큰 수 찾기

접근 과정

1. 앞의 수에서 뒤에 수를 탐색하면서 비교하면 시간 초과가 나므로 반대로 뒤에서 앞으로 오면서 더 큰 수가 있는지 체크
2. 스택을 활용하여 더 큰 수만 유지하는 방식으로 해결
3. 해당 인덱스의 수를 보고 스택의 위가 더 큰지 비교하여 더 크면 그 수로 넣음
4. 아니라면 스택에서 제거를 스택이 빌 때까지 반복
5. 스택이 비어 있다면 -1로 넣음
6. 해당 인덱스의 수를 스택에 추가

시행착오

• 1차로 단순 2중 for문으로 해결했는데 역시 시간 초과가 났다. 제한 사항이 100만이라 n^2이면 시간 초과가 난다.

import java.util.*;

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

해결 코드

• 시행착오를 겪으며 스택을 활용하여 뒤에서 앞으로 오는 방식으로 해결하였다.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> st = new Stack<>();
        for(int i = numbers.length - 1; i >= 0; i--){
            int num = numbers[i];
            while(!st.isEmpty()){
                if(num < st.peek()){
                    answer[i] = st.peek();
                    break;
                }
                else{
                    st.pop();
                }
            }
            if(st.isEmpty()) answer[i] = -1;
            st.push(num);
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(입력 배열의 길이를 N)

• 공간 복잡도

더 맵게

접근 과정

1. 가장 작은 스코빌이 K보다 작으면 스코빌이 작은 음식 2개를 꺼내 문제의 공식으로 섞어야 하므로 최소 힙을 사용
2. 우선순위 큐에 음식의 스코빌을 모두 넣음
3. 맨 앞이 K보다 작으면 음식 2개를 문제의 공식으로 계산하여 큐에 넣음
4. 3번을 맨 앞이 K보다 크거나 같아질 때까지 반복
5. 반복하다가 큐의 크기가 2보다 작으면 더이상 공식이 적용안되기에 -1 반환

시행착오

• 시행착오 없이 해결

해결 코드

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

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int s : scoville) pq.add(s);
        while(pq.peek() < K){
            if(pq.size() < 2) return -1;
            int food1 = pq.poll();
            int food2 = pq.poll();
            pq.add(food1 + food2 * 2);
            answer++;
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(음식의 개수를 N)

• 공간 복잡도