더 이상 물러설 곳이 없다

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 이라 시간초과가 나진 않았지만 굉장히 비효율적...

나중에 따로 내용 정리

이제까지 진행했던 테스트는 스프링 컨테이너의 간섭을 받지 않고 순수 자바 코드로만 동작하는 '단일 테스트'였다.

스프링 컨테이너와 함께 테스트를 실행하는 '통합 테스트'도 가능하다.

@SpringBootTest 를 통해 간단하게 처리 가능.

스프링 통합 테스트는 단일 테스트에 비해 시간이 오래 걸린다. 테스트 케이스가 많아질수록 그 차이는 커진다. 따라서 스프링에 의존하지 않는 단일 테스트 케이스를 만드는 능력이 중요하다.

스프링 통합 테스트를 진행할 때 @Transactional 을 통해 @AfterEach를 대체할 수 있다.

스프링과 직접 연동되는 테스트이기 때문에 테스트로 인해 디비에 데이터가 저장된 후 다시 테스트를 돌렸을 때 데이터 중복에 의해 오류가 발생할 수 있다. (사실 이건 굳이 통합 테스트가 아니어도 마찬가지)

@Transactional 은 각 테스트 케이스가 실행하기 전 트랜잭션을 생성하고 테스트가 종료되면 해당 트랜잭션을 롤백함으로써 데이터 @AfterEach의 기능을 대신할 수 있다. 

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%EC%9E%85%EB%AC%B8-%EC%8A%A4%ED%94%84%EB%A7%81%EB%B6%80%ED%8A%B8

생략

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()를 추가하여 정답 코드를 완성하였다.