프로그래머스LV2_12

기능개발

접근 과정

1. 각 기능에 필요 일수를 계산하여 큐에 추가하여 2-3을 큐가 빌 때까지 반복
2. 큐의 앞에 필요 기능 일 수보다 작거나 같을 때까지 큐의 앞을 제거하고 개수를 늘림
3. 정답 리스트에 해당 개수를 추가
4. 리스트를 배열로 변환하여 반환하면 해결

시행착오

• 큐를 안쓰고 반복문으로 풀려다가 인덱스가 초과하는 에러가 터지는 것을 생각했는데 잘 안되어 큐를 사용하여 해결

해결 코드

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

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < speeds.length; i++){
            int left = 100 - progresses[i];
            q.add(((left) % speeds[i] == 0)? (left / speeds[i]) : (left / speeds[i] + 1));
        }
        List<Integer> li = new ArrayList<>();
        while(!q.isEmpty()){
            int cnt = 1;
            int day = q.poll();
            while(!q.isEmpty() && q.peek() <= day){
                q.poll();
                cnt++;
            }
            li.add(cnt);
        }
        return li.stream().mapToInt(i -> i).toArray();
    }
}

시간 및 공간 복잡도

• 시간 복잡도(작업의 개수를 N)

• 공간 복잡도(큐와 리스트에 N개의 데이터가 들어갈 수 있음)

개선

• 중간에 삼항 연산자 대신에 Math.ceil 을 활용하여 올림 계산을 하면 좀 더 코드가 간결해짐

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < speeds.length; i++){
            double left = 100.0 - progresses[i];
            q.add((int)Math.ceil(left / speeds[i]));
        }
        List<Integer> li = new ArrayList<>();
        while(!q.isEmpty()){
            int cnt = 1;
            int day = q.poll();
            while(!q.isEmpty() && q.peek() <= day){
                q.poll();
                cnt++;
            }
            li.add(cnt);
        }
        return li.stream().mapToInt(i -> i).toArray();
    }
}

캐시

접근 과정

1. 캐시를 LinkedList로 선언하여 최근에 사용된 것을 앞으로 배치
2. 캐시 사이즈가 최대치이면 캐시의 마지막 요소를 제거하고 해당 요소를 맨 앞에 추가하고 answer를 5늘림
3. 이미 캐시에 있다면 그 요소를 제거하고 맨 앞에 추가하고 answer를 1늘림

시행착오

• LRU를 어떤 자료구조로 구현하면 되는지 구글링 하여 찾았다.

해결 코드

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

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        if (cacheSize == 0) return cities.length * 5;
        LinkedList<String> cache = new LinkedList<>();
        for(String city : cities){
            if(cache.contains(city)){
                cache.remove(city);
                cache.addFirst(city);
                answer += 1;
            }
            else {
                if (cache.size() == cacheSize) {
                    cache.removeLast();
                }
                cache.addFirst(city);
                answer += 5;
            }
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(도시 배열의 길이를 N, 캐시 크기를 C라고 할 때)

• 공간 복잡도(캐시 크기만큼 저장해야 하므로)