더 이상 물러설 곳이 없다

programmers.co.kr/learn/courses/30/lessons/42627

각 작업의 [작업 요청 시간, 수행 시간]이 담긴 int[][] jobs가 주어진다.

SJF(Shortest Job First) 알고리즘으로 작업들을 수행하였을 때 작업들의 평균 대기시간을 반환해야한다.

(대기시간 = 작업 완료 시간 - 작업 요청 시간)

풀이 .

import java.util.*;

class Work {
    int arrive;
    int require;
    public Work(int arrive, int require) {
        this.arrive = arrive;
        this.require = require;
    }
}

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;

        // 시간의 흐름을 하나 두자
        // 현재 시간에서 도착한 놈들끼리 SJF를 수행하면 된다.
        // 1. pqArrive에 다 떄려넣는다.
        // 2. 그 중에서 arrive가 time을 넘긴 것만(이미 도착한 것만) pqRequire로 넘긴다.
        // 3. pqRequire 가지고 SJF 수행.
        PriorityQueue<Work> pqArrive = new PriorityQueue<>(new Comparator<Work>() {
            @Override
            public int compare(Work o1, Work o2) {
                return o1.arrive < o2.arrive ? -1 : 1;
            }
        });
        PriorityQueue<Work> pqRequire = new PriorityQueue<>(new Comparator<Work>() {
            @Override
            public int compare(Work o1, Work o2) {
                return o1.require < o2.require ? -1 : 1;
            }
        });

        for(int[] job : jobs) {
            pqArrive.add(new Work(job[0], job[1]));
        }

        int time = 0;
        int wait = 0;
        while(!(pqArrive.isEmpty() && pqRequire.isEmpty())) {
            // 도착한 작업 이동
            // !pqArrive.isEmpty() 없으면 에러. 남아있는 작업이 있어야 넘길 수도 있음
            while(!pqArrive.isEmpty() && pqArrive.peek().arrive <= time) {
                pqRequire.add(pqArrive.poll());
            }

            // SJF
            if(pqRequire.isEmpty()) {  // 도착한 작업 없으면 다음 작업 도착할 시간으로 이동
                time = pqArrive.peek().arrive;
            } else {
                int arrive = pqRequire.peek().arrive;
                int require = pqRequire.poll().require;
                time += require;
                wait += time - arrive;
            }
        }

        answer = wait / jobs.length;
        return answer;
    }
}

작업 요청시간과(arrive) 수행시간을(require) 한 번에 관리하기 위해 class Work을 만들었다.

정렬 기준이 다른 두개의 PriorityQueue를 사용한다. 하나는 요청시간, 하나는 수행시간을 기준으로 한다.

1. 도착하기 전 Work들은 모두 pqArrive에 담긴다.

2. 요청된 작업들은 pqRequire로 넘어간다.

3. SJF 수행

4. 요청한 작업이 아무것도 없을 경우를 고려해야한다. 아무것도 도착하지 않았다면 바로 다음 작업이 요청되는 시간으로 이동한다.

programmers.co.kr/learn/courses/30/lessons/42626

각 음식의 스코빌 지수를 담은 int[] scoville과 최소 스코빌 지수 int K가 주어진다.

scoville의 모든 수가 K 이상이 되도록 각 스코빌 지수들을 조합하여 새로운 스코빌 지수를 만들어 넣는다.

이 과정을 몇 번 수행해야 모든 스코빌 지수가 K 이상이 되는지를 반환해야한다.

풀이 .

import java.util.*;

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

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

        while(minHeap.peek() < K) {
            int temp = minHeap.poll() + minHeap.poll() * 2;
            minHeap.add(temp);
            answer++;

            // 예외처리. 아무리 반복해도 K 이상이 될 수 없다면 return -1
            if(minHeap.size() == 1 && minHeap.peek() < K) {
                answer = -1;
                break;
            }
        }
        return answer;
    }
}

PriorityQueue를 사용해 minHeap을 만들었다.

pq의 디폴트는 민힙이고 new PriorityQueue<>(Collections.reverseOrder()을 통해 맥스힙도 만들 수 있다.

programmers.co.kr/learn/courses/30/lessons/42587

출력할 인쇄물의 우선순위를 담은 배열 int[] priorities, 타겟 인쇄물의 인덱스를 담은 int location 이 주어진다.

각 인쇄물의 우선순위를 반영하여 차례대로 출력할 때 타겟 인쇄물이 몇번째로 인쇄되는지를 반환해야한다.

1. 최초 대기열 순서는 priorities의 순서와 같다.

2. 맨 앞의 인쇄물을 꺼내서 뒤의 인쇄물들과 우선순위를 비교한다. 

3. 뒤의 인쇄물들 중 나보다 우선순위가 높은 것이 하나라도 있다면 맨 앞의 인쇄물을 맨 뒤로 보낸다.

4. 모든 인쇄물이 나보다 우선순위가 낮다면 그것을 출력한다.

풀이 .

import java.util.*;

class Work {
    int loc;  // 최초 대기열의 index
    int priority;  // 우선순위
    int done;  // 작업 완료되는 순서
    public Work(int loc, int priority) {
        this.loc = loc;
        this.priority = priority;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        List<Work> list = new LinkedList<Work>();

        Work target = null;
        for(int i = 0; i < priorities.length; i++) {
            list.add(new Work(i, priorities[i]));
            if(i == location) {  // 마지막에 정답 추출하기 위한 타겟 객체 참조
                target = list.get(i);
            }
        }

        int cnt = 1;
        while(!list.isEmpty()) {
            int p = list.get(0).priority;
            for(int i = 0; i < list.size(); i++) {
                if(p < list.get(i).priority) {  // 나보다 우선인 놈 있으면 맨 뒤로 넘긴다
                    list.add(list.remove(0));
                    break;
                }
                if(i == list.size() - 1) {  // 마지막 원소까지 검사 완료했으면
                    list.get(0).done = cnt++;  // 완료 순서 저장하고
                    list.remove(0);  // 대기열에서 제거
                }
            }
        }
        answer = target.done;
        return answer;
    }
}

인쇄물들을 관리하기 위해 Work 클래스를 만들었다.

작업이 완료된 객체들은 따로 저장하지 않고 바로 제거해버리기 때문에 Work target을 사용해 타겟 객체를 따로 참조했다.

나머지는 문제의 조건을 그대로 따라했다.

시간복잡도가 조금 걸리는데.. 

일단 priorities의 길이의 상한은 100

1개의 원소를 제거 가능한지 불가능한지 확인하는 데 n만큼이 걸린다.

우선순위가 가장 높은 원소가 맨 뒤에 있다고 가정하면 1개의 원소를 제거하는 데 n^2이 걸린다.

이런식으로 n개의 원소를 제거하려면 결국 O(n^3)이 걸린다.

100^3 = 1,000,000 이라 시간초과가 나진 않았지만 굉장히 비효율적...

programmers.co.kr/learn/courses/30/lessons/42583

다리의 길이, 다리가 견딜 수 있는 무게, 트럭들의 무게가 주어질 때 모든 트럭이 다리를 건너려면 몇 초가 걸리는지 반환해야한다.

1. 트럭은 int[] truck_weights의 순서대로 움직인다.

2. 트럭은 1초에 1만큼 이동한다.

3. 다리에 올라간 트럭의 무게의 합은 다리가 견딜 수 있는 무게 이하여야한다.

풀이 .

import java.util.LinkedList;
import java.util.Queue;

class Truck {
    int location;
    int weight;
    Truck(int location, int weight) {
        this.location = location;
        this.weight = weight;
    }
}

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;

        Queue<Truck> tQue = new LinkedList<Truck>();
        Queue<Truck> bQue = new LinkedList<Truck>();
        for(int w : truck_weights) {
            tQue.add(new Truck(0, w));
        }

        int cnt = 0;  // 다리를 통과한 트럭 개수
        int time = 0;
        int currentWeight = 0;
        while(cnt < truck_weights.length) {
            time++;  // 반복 한 번 당 1초

            // 다리 위 트럭 한 칸 씩 이동
            for(Truck t : bQue) {
                t.location++;
            }

            // 다 건넌 트럭 제거
            if(!bQue.isEmpty() && bQue.peek().location > bridge_length) {
                currentWeight -= bQue.poll().weight;
                cnt++;
            }

            if(!tQue.isEmpty() &&  // 더 들어갈 트럭이 있는가?
                    bQue.size() < bridge_length &&  // 다리에 들어갈 자리가 있는가?
                    currentWeight + tQue.peek().weight <= weight) {  // 다리가 무게를 감당할 수 있는가?
                tQue.peek().location++;
                currentWeight += tQue.peek().weight;
                bQue.add(tQue.poll());
            }
        }
        answer = time;
        return answer;
    }
}

트럭의 위치를 표시하기 위해 class Truck을 만들었다.

다리에 올라가기 전 모든 트럭의 location은 0이다.

1. 다리 위 모든 트럭들의 한 칸 전진

2. 다리를 건넌 트럭이 있다면 제거

3. 트럭이 새로 들어올 수 있다면 추가

nullpointerexception이 여러 번 떠서 찾느라 애를 먹었다.

처음 코딩할 때부터 nullpointer를 감안해서 짤 수 있었으면 좋겠는데 잘 안 된다.

programmers.co.kr/learn/courses/30/lessons/42586

각 작업의 진행상태와 작업속도를 담은 배열 int[] progresses, int[] speeds가 주어진다.

작업이 완료되어 배포될 때마다 몇 개의 작업이 배포되는지를 담은 배열을 반환해야한다.

1. 작업의 진도가 100까지 도달해야 새로운 기능을 배포할 수 있다.

2. 앞의 작업이 배포되기 전에 뒤의 작업이 배포될 수 없다. 뒤의 작업이 먼저 완료되더라도 앞이 끝날 때까지 기다렸다가 앞의 작업이 완료되면 함께 배포된다.

풀이 .

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> answer = new ArrayList<Integer>();

        ArrayList<Integer> pList = new ArrayList<Integer>();
        ArrayList<Integer> sList = new ArrayList<Integer>();
        for(int i = 0; i < progresses.length; i++) {
            pList.add(progresses[i]);
            sList.add(speeds[i]);
        }

        while(!pList.isEmpty()) {
            while(pList.get(0) < 100) {
                for(int i = 0; i < pList.size(); i++) {
                    pList.set(i, pList.get(i) + sList.get(i));
                }
            }
            int cnt = 0;
            while(!pList.isEmpty() && pList.get(0) >= 100) {  // 완료되지 않은 작업 있으면 바로 중지
                pList.remove(0);
                sList.remove(0);
                cnt++;
            }
            answer.add(cnt);
        }
        return answer;
    }
}

progress와 speed를 ArrayList로 옮겨 완료된 작업을 하나씩 삭제하며 진행했다.

맨 앞의 작업의 진도가 100이 될 때까지 모든 작업이 각자 자신의 속도대로 진도를 나간다.

맨 앞이 100이 됐다면 100 미만의 작업이 나올 때까지 앞에서부터 모두 제거하며 개수를 센다.

추가

java.util.ConcurrentModificationException
처음에 짠 코드에서 위 에러가 발생했다. 

원인은, 다음과 같다.

    for(int progress : pList) {
        if(progress >= 100) {
            pList.remove(0);
            sList.remove(0);
            cnt++;
        }else {
            break;
        }
    }

pList에 대한 반복을 돌리면서 pList.remove()를 실행했기 때문이다.

다음과 같이 코드를 수정했고 java.lang.nullpointerexception이 발생했다.

while(pList.get(0) >= 100) {
	pList.remove(0);
	sList.remove(0);
	cnt++;
}

반복 초반에는 상관이 없지만 마지막까지 가서 모든 원소가 지워지게 되면 pList는 비어있기 때문에 널포인트 예외가 발생한다.

!pList.isEmpty()를 추가하여 정답 코드를 완성하였다. 

programmers.co.kr/learn/courses/30/lessons/42584

초단위로 주식의 가격을 담은 int[] prices가 주어진다. (인덱스 한 칸 당 1초)

각 초를 시점으로 하여 주식 가격이 몇 초 동안 떨어지지 않는지 기록한 배열을 반환해야한다.

주의할 점은 1초 뒤에(바로 다음 인덱스에서) 가격이 떨어지는 경우는 1초 동안 떨어지지 않은 것으로 본다.

마지막 인덱스는 그 뒤의 가격이 존재하지 않기 때문에 0초로 한다.

풀이 .

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length; i++) {
            int time = 0;
            for(int j = i + 1; j < prices.length; j++) {
                // 다음 초에 가격이 떨어지더라도 그 초까지는 카운트를 해야한다
                time++;
                // 가격이 떨어지면 카운트 중지
                if(prices[i] > prices[j]) {
                    break;
                }
            }
            answer[i] = time;
        }
        return answer;
    }
}

주석으로 표시한 사항만 조심하면 되는 문제

programmers.co.kr/learn/courses/30/lessons/42579

각 노래들의 장르와 플레이 수를 담은 String[] genres, int[] plays가 주어진다.

배열의 인덱스를 각 노래의 고유번호로 한다.

이 중 몇 가지 노래를 뽑아 베스트 앨범을 만들고자 한다.

베스트 앨범 조건

1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)

2. 장르 별 총 재생 수가 많은 장르부터 뽑는다. 

3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.

4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

풀이 .

import java.util.*;

//1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)
//2. 장르 별 총 재생 수가 많은 장르부터 뽑는다.
//3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.
//4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

class Song implements Comparable<Song> {
    int index;
    int play;

    public Song() {}
    public Song(int index, int play) {
        this.index = index;
        this.play = play;
    }

    @Override
    public int compareTo(Song o) {
        if (this.play != o.play) {
            if (this.play > o.play) { return -1; }
            else { return 1; }
        } else {
            if (this.index < o.index) { return -1; }
            else { return 1; }
        }
    }
}

class Solution {
    public ArrayList<Integer> solution(String[] genres, int[] plays) {
        // 장르 별 총 재생 수 세기
        Map<String, Integer> jenreHm = new HashMap<String, Integer>();
        for(int i = 0; i < genres.length; i++) {
            String jenre = genres[i];
            if(jenreHm.get(jenre) == null) {
                jenreHm.put(jenre, plays[i]);
            }else {
                jenreHm.put(jenre, jenreHm.get(jenre) + plays[i]);
            }
        }

        // 총 재생 수의 내림차순으로 정렬
        // List에 옮겨 정렬한 후 LinkedHashMap으로 넘겨 순서 유지
        List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>();
        for(Map.Entry<String, Integer> entry : jenreHm.entrySet()) {
            list.add(entry);
        }
        Collections.sort(list, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        Map<String, Integer> sortedJenreHm = new LinkedHashMap<String, Integer>();
        for(Map.Entry<String, Integer> entry : list) {
            sortedJenreHm.put(entry.getKey(), entry.getValue());
        }

        // Map<String, ArrayList<Song>>으로 멀티 맵 구현
        Map<String, ArrayList<Song>> multiHm = new LinkedHashMap<String, ArrayList<Song>>();
        for(String jenre : sortedJenreHm.keySet()) {
            multiHm.put(jenre, new ArrayList<Song>());
        }

        // 장르 별 노래 저장. 이때 장르 별 총 재생 수 내림차순 정렬은 완료되어있음
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            multiHm.get(genre).add(new Song(i, plays[i]));
        }

        // 장르 별 최다 재생 곡 2개 뽑아서 저장
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(ArrayList<Song> aList : multiHm.values()) {
            Collections.sort(aList);
            // 장르에 곡이 하나 뿐이면 하나만 저장
            ansList.add(aList.get(0).index);
            if(aList.size() >= 2) {
                ansList.add(aList.get(1).index);
            }
        }
        return ansList;
    }
}

1. 최다 재생 수가 많은 장르부터 수록해야 하므로 hm을 통해 장르 별 총 새생 수 먼저 파악

2. LinkedList를 사용해 총 재생 수로 내림차순 정렬 후 LinkedHashMap으로 옮겨 그 순서를 유지 (그냥 HashMap은 입력 순서 유지되지 않아 정렬이 해쳐짐)

3. 장르 안의 노래들 사이에서도 정렬이 필요. Song 클래스를 만들어 정렬 기준 명시 (play 내림차순, index 오름차순)

4. Map<String, ArrayList<Song>>으로 멀티 맵 구현. 장르 별로 자신의 노래를 저장할 리스트를 갖는다.

5. 각 장르에 해당하는 Song을 모두 담고 이를 내림차순 정렬하여 인덱스 0, 1의 원소(상위 2곡)를 정답 리스트에 저장

너무 주먹구구식의 풀이가 아닌가 싶다. 이정도 방법도 생각하는데 꽤 오랜 시간이 걸렸다.

programmers.co.kr/learn/courses/30/lessons/42578

이차원 배열 String[][] clothes가 주어진다.

clothes : { {옷이름, 옷종류}, {옷이름, 옷종류}, ... {옷이름, 옷종류} }

주어진 옷들로 만들 수 있는 조합의 수를 반환하는 문제.

단, 각각의 옷은 입을 수도 안 입을 수도 있으나 아무것도 안 입는 경우는 없다.

풀이 .

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

class Solution {
    public int solution(String[][] clothes) {
        // clothes : [{옷이름, 옷종료}, {옷이름, 옷종류}, ... , {옷이름, 옷종류} ]
        int answer = 1;

        Map<String, Integer> hm = new HashMap<String, Integer>();
        for(String[] cloth : clothes) {
            String key = cloth[1];  // 옷 종류를 key로 사용

            if(hm.get(key) == null) {
                hm.put(key, 2);  // 안 입는 경우도 고려하여 2부터 시작
            }else {
                hm.put(key, hm.get(key) + 1);
            }
        }

        for(Integer num : hm.values()) {
            answer *= num;
        }
        answer--;  // 아무것도 안 입는 경우는 없음
        return answer;
    }
}

옷의 이름은 중요하지 않다.

옷의 종류를 key로 잡고 HashMap을 사용해 종류별로 몇 개의 옷이 있는지 센 다음 그걸 모두 곱하면 된다.

옷을 입지 않는 경우, 아무것도 입지 않는 경우에 대한 고려를 해줘야한다.

O(n)으로 처리 가능