[java] 프로그래머스스쿨 연습문제 Lv.2 Greedy 문제 모음

1. 호텔 대실

코딩테스트 연습 - 호텔 대실 | 프로그래머스 스쿨 (programmers.co.kr)

풀이

1. 체크인 시간과 체크아웃 시간을 저장하기 위해 2차원 배열 schedule을 선언한다. 1-1. split과 parseInt를 사용해 순서대로 저장한다. 1-2. 시간*60+분 1-3. 체크아웃 시간을 저장할 때에는 청소시간 10분을 추가로 더한다. 2. schedule을 체크인 시간순으로 정렬하고, 체크인 시간이 같다면 체크아웃 시간으로 정렬한다. 3. 우선순위 큐를 선언하여 schedule의 checkout 시간을 정렬된 순서대로 삽입한다. 4. 만약 우선순위 큐의 첫 번째 원소가 다음 입실 시간보다 작거나 같다면 poll, 퇴실시간을 큐에 추가 5. 그렇지 않다면 큐에 퇴실시간을 add

회고

- 자바에서 우선순위 큐를 처음 써보는듯,, 회의실 배정같은 문제는 Greedy 대표 문제니까 잘 알아두자~~ - PriorityQueue : peek(), poll(), add() - 사실 그냥 배열로 버무려보려다가 개같이 실패함 ㅜㅜ 왜 안되는지 아직 이해 못하고있음

코드 (접은 글)

import java.util.*;

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

        int[][] schedule = new int[book_time.length][2];

        for (int i = 0; i < book_time.length; i++) {
            String[] checkIn = book_time[i][0].split("\\:");
            String[] checkOut = book_time[i][1].split("\\:");
            schedule[i][0] = Integer.parseInt(checkIn[0]) * 60 + Integer.parseInt(checkIn[1]);
            schedule[i][1] = Integer.parseInt(checkOut[0]) * 60 + Integer.parseInt(checkOut[1]) + 10;
        }

        Arrays.sort(schedule, (a, b) -> {
            if (a[0] > b[0]) return 1;
            else if (a[0] < b[0]) return -1;
            else {
                if (a[1] > b[1]) return 1;
                else return -1;
            }
        });

        PriorityQueue<Integer> rooms = new PriorityQueue<>();

        for (int[] timeTable : schedule) {
            if (rooms.size() == 0) {
                rooms.add(timeTable[1]);
                continue;
            }
            int emptyRoom = rooms.peek();
            if (timeTable[0] >= emptyRoom)
                rooms.poll();
            rooms.add(timeTable[1]);
        }
        return rooms.size();
    }
}

 

2. 요격 시스템

코딩테스트 연습 - 요격 시스템 | 프로그래머스 스쿨 (programmers.co.kr)

풀이

1. 범위를 바꿔나가기 위해 시작 위치(s)를 최솟값 0, 끝나는 위치(e)를 최댓값 100000000로 설정한다. 2. targets를 시작 위치에 대해 오름차순 정렬하고 값이 같다면 끝나는 위치에 대해 내림차순 정렬한다. 3. 반복문을 사용해 target의 값을 읽어가며 범위를 바꿔준다. 4. 앞선 미사일의 끝 위치가 다음 미사일의 끝 위치보다 크거나 같다면  4-1. s와 e를 다음 미사일의 위치로 바꾸고 continue; 5. 앞선 미사일의 끝 위치가 다음 미사일의 시작 위치보다 작거나 같다면 5-1. s와 e를 다음 미사일의 위치로 바꾸고 answer++; 6. 앞선 미사일에 다음 미사일이 겹친다면 6-1. s만 다음 미사일의 시작 위치로 바꿔준다.

회고

- 난 이런 개구간 범위가 등장하는 문제에 정말 약하다.... 범위 파악이 넘모 귀찮고 힘들다

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 1;
        int s = 0, e = 100000000;

        Arrays.sort(targets, (a, b) -> {
            if (a[0] > b[0]) return 1;
            else if (a[0] < b[0]) return -1;
            else {
                if (a[1] > b[1]) return 1;
                else return -1;
            }
        });

        for (int i = 0; i < targets.length; i++) {
            if (targets[i][1] <= e) {
                s = targets[i][0];
                e = targets[i][1];
                continue;
            }
            if (targets[i][0] < e && targets[i][1] >= e) {
                s = targets[i][0];
            }
            if (targets[i][0] >= e) {
                s = targets[i][0];
                e = targets[i][1];
                answer++;
            }
        }
        return answer;
    }
}