더 이상 물러설 곳이 없다

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

세 명의 수포자가 모의고사를 치른다. 각 수포자들은 각각 다른 패턴으로 정답을 찍는다.

모의고사의 정답지 int[] answers가 주어질 때, 정답을 가장 많이 맞춘 수포자를 배열에 담아 반환해야한다.

단, 공동 1위가 나온다면 수포자 번호의 오름차순으로 담아 반환한다.

풀이 .

import java.util.*;

class Solution {
    public List<Integer> solution(int[] answers) {
        ArrayList<Integer> answer = new ArrayList<>();

        int[] a = {1, 2, 3, 4, 5};
        int[] b = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

        int[] score = new int[3];  // 각 수포자들의 점수 체크
        for(int i = 0; i < answers.length; i++) {
            if(a[i % a.length] == answers[i]) score[0]++;
            if(b[i % b.length] == answers[i]) score[1]++;
            if(c[i % c.length] == answers[i]) score[2]++;
        }

        int max = Math.max(score[0], Math.max(score[1], score[2]));
        if(max == score[0]) answer.add(1);
        if(max == score[1]) answer.add(2);
        if(max == score[2]) answer.add(3);
        return answer;
    }
}

나머지 연산을 잘 써야하는 문제.

n % m 의 결과는 0 ~ m-1만 나온다는 것을 기억하자.

i % a.length 의 결과는 0 ~ a.length-1을 반복한다. 따라서 a[]의 인덱스 범위 내에서만 반복을 돌게 된다.

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

숫자들의 배열 int[] numbers가 주어진다.

숫자들을 이어붙였을때(String의 합처럼) 만들 수 있는 가장 큰 수를 반환해야한다.

풀이 .

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);  // 주의, String 끼리는 부등호 연산 사용할 수 없음
            }
        });

        // 예외처리, 맨 앞칸이 0이면 00~0의 형태. 즉, 0
        if(arr[0].equals("0")) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for(String str : arr) {
            sb.append(str);
        }
        return sb.toString();
    }
}

String에 대한 Comparator를 새로 만들어서 문제를 해결했다.

주의할 점은 compare()에서 반드시 compareTo()를 사용해야 한다는 점이다.

return (o1 + o2) < (o2 + o1) ? 1 : -1 을 사용하려고 했으나 String 끼리는 부등호 연산을 사용할 수 없었다.

비슷한 경우로 int 끼리는 compareTo()를 사용할 수 없다. 만약 사용하고 싶다면 Integer를 사용해야한다.

결과 출력에 굳이 StringBuilder를 사용하지 않고 + 연산으로 처리해도 된다.

하지만 시간차가 심하기 때문에 웬만해선 StringBuilder를 사용하는 것이 좋다.

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

int[] array, int[][] commands가 주어진다.

commands 의 각 행에는 명령을 위한 3개의 int가 들어있다.

[begin, end, K]

명령에 대한 답은 array에서 [begin번째 ~ end번째]만큼을 잘라내고 그 중 K번째로 큰 값이다.

(단, begin, end는 인덱스를 나타내지 않는다. 1부터 시작하는 순서를 나타낼 뿐이다.)

commands 의 각 명령들에 대한 답을 담은 배열을 반환해야한다.

풀이 . 

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        int ansIdx = 0;
        for(int[] command : commands) {
            int begin = command[0];
            int end = command[1];
            int k = command[2];

            int[] temp = new int[end - begin + 1];
            int idx = 0;
            for(int i = begin - 1; i <= end - 1; i++) {  // 인덱스와 순서 혼동 주의
                temp[idx++] = array[i];
            }
            Arrays.sort(temp);
            answer[ansIdx++] = temp[k - 1];
        }

        return answer;
    }
}

 문제에서 시키는 그대로 따라하면 된다.

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

수행할 명령어들이 담긴 배열 String[] operations가 주어진다.

주어진 명령을 모두 수행한 뒤 남아있는 값 중 최대값, 최소값을 담은 배열을 반환해야한다.

단, 남아있는 값이 하나도 없을 경우 최대값, 최소값은 0으로 한다.

명령

I 숫자 : 숫자 입력

D 1 : 입력된 숫자 중 최대값 삭제

D -1 : 입력된 숫자 중 최소값 삭제

풀이 .

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(String operation : operations) {
            StringTokenizer st = new StringTokenizer(operation);
            switch(st.nextToken()) {  // work
                case "I" :  // input
                    int input = Integer.parseInt(st.nextToken());
                    minHeap.add(input);
                    maxHeap.add(input);
                    break;
                case "D" :  // delete
                    if(minHeap.isEmpty()) {
                        continue;
                    }
                    if(st.nextToken().equals("1")) {  // 최대값 삭제
                        int max = maxHeap.poll();
                        minHeap.remove(max);
                    }else {  // 최소값 삭제
                        int min = minHeap.poll();
                        maxHeap.remove(min);
                    }
                    break;
            }
        }

        if(minHeap.isEmpty()) {  // 예외처리
            answer[0] = 0;
            answer[0] = 0;
        }else {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }
        return answer;
    }
}

최대값과 최소값을 동시에 다루기 위해 두 개의 PriorityQueue를 사용하였다.

각 명령을 두 pq에 함께 수행한 뒤 최대, 최소를 반환하면 된다.

pq.remove(Object o)가 가능한 것을 알게 되었다.

백준에선 자주 쓰이지만 프로그래머스에서 StringTokenizer 를 사용한 것은 처음이었다.

(StringTokenizer 를 사용해 " "으로 split한 문자열들을 얻을 수 있다. 다른 것으로 split 하고 싶다면 두 번째 매개변수로 줄 수 있다.)

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를 감안해서 짤 수 있었으면 좋겠는데 잘 안 된다.