프로그래머스 - 호텔 대실, 뒤에 있는 큰 수 찾기, 주차 요금 계산

🏨 프로그래머스 : 호텔 대실 

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

🏨  우선 순위 큐 2개를 가지고 푸는 문제로, 백준 11000 - 강의실 배정 문제와 유사하다고 느꼈다.

🏨  최소한의 객실만을 사용, 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소 필요

🏨  Room 클래스 : 들어온 시간, 나간 시간 계산하기 

• 처음에는 들어온 / 나간 시간 + 분을 다 해서 4개로 구성했는데, 그냥 처음부터 분으로 계산해서 비교하면 한 번에 비교 가능해서 편하다. 
• 13:10 -> 780 + 10 = 790 이런식으로! 

🏨 먼저 손님 들어오는 시간 기준으로 정렬한 우선순위 큐 reserve를 만들고, 시간을 계산해서 넣어준다. 

🏨 reserve 우선순위 큐에서 계속 하나씩 꺼내면서 돈다. 

🏨 rooms 우선순위 큐는 먼저 퇴실하는 순으로 정렬된 우선순위 큐로, 이 rooms의 사이즈 == 방 개수이다. 

 

🏨 이미 배정된 방이 있는데(room.isEmpty() 가 아님), 그 방의 퇴실시간 + 청소 10분 한게 현재 reserve에서 읽은 다음 예약의 시작 시간보다 작다면, 해당 방을 재사용해도 된다. 

🏨 따라서 이 경우에는 rooms.poll()을 해준다.

🏨 위 조건이 만족되지 않으면 rooms.poll() 하지 않고  넣어준다. 

 

🏨 전체 코드

import java.util.*;
class Solution {
    public int solution(String[][] book_time) {
        PriorityQueue<Room> reserve = new PriorityQueue<>((r1, r2) -> r1.start - r2.start);
        PriorityQueue<Room> rooms = new PriorityQueue<>((r1, r2) -> r1.end - r2.end);
        
        for (String[] str : book_time) {
            String[] in = str[0].split(":");
            String[] out = str[1].split(":");
            int inTime = Integer.parseInt(in[0]) * 60 + Integer.parseInt(in[1]);
            int outTime = Integer.parseInt(out[0]) * 60 + Integer.parseInt(out[1]);
            reserve.add(new Room(inTime, outTime));
        }
        
        while (!reserve.isEmpty()) {
            Room poll = reserve.poll();
            if (!rooms.isEmpty() && rooms.peek().end + 10 <= poll.start) {
                rooms.poll();
            }
            rooms.add(poll);
        }
        
        return rooms.size();
    }
    
    class Room {
        int start;
        int end;
        Room(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

 

 

---

 

 

🔎 프로그래머스 : 뒤에 있는 큰 수 찾기 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

🔎 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수( == 뒷 큰수)들을 차례로 담은 배열을 return하되, 뒷 큰수가 존재하지 않는 원소는 -1을 담기

🔎 문제를 보자마자 스택으로 풀어야겠다고 생각했다.   

 

🔎 뒤에 읽은 숫자가 더 크다면 바로 그 숫자가 정답 배열에 들어오고, 스택이 비지 않았고, 해당 숫자보다 더 큰 값이 나오기 전까지 계속 원소를 pop 해줌 + 정답 배열의 해당 원소 index 에 뒤에 읽은 숫자 넣고 스택에 넣어준다. 

🔎 아니라면 더 큰 수가 들어올때까지 차례로 스택에 넣는다. 

🔎 이때, 원소의 순서대로 뒷 큰수를 넣어주어야 하므로 Num 클래스 (int index, int value)를 만들고 Num 클래스를 스택에 담기 

 

🔎 전체 코드 

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        Stack<Num> stack = new Stack<>();
        int[] result = new int[numbers.length];
        stack.push(new Num(0, numbers[0]));
        for (int i = 1; i < numbers.length; i++) {
            if (stack.peek().value < numbers[i]) {
                while (!stack.isEmpty() && stack.peek().value < numbers[i]) {
                    Num pop = stack.pop();
                    result[pop.index] = numbers[i];
                }
            } 
            stack.push(new Num(i, numbers[i]));
        
        }
        
        while (!stack.isEmpty()) {
            Num pop = stack.pop();
            result[pop.index] = -1;
        }
        
        return result;
    }
    
    class Num {
        int index;
        int value;
        
        Num(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}

 

 

---

 

 

🚧 프로그래머스 : 주차 요금 계산

https://school.programmers.co.kr/learn/courses/30/lessons/92341

프로그래머스

 

🚧 또 문제 제대로 안 읽고 풀다가 코딩 다하고 다시 지우고 다시 푼 문제 ㅋ 

🚧 누적 주차시간을 다 카운트한 다음 마지막에 요금을 정산한다. 그리고 같은 차량이 여러 번 왔다갔다 할 수 있다. 

 

🚧 메인 로직 

• 진입할 때에는 map에 차량 번호 + 시간을 함께 넣어준다.
• 차가 나갈 때(읽은 값이 OUT)
  • map에서 진입시간을 꺼내서 총 몇 시간 머무른 것인지 계산하고 answer에 넣는다. 
  • 이때 answer에서 해당 차 번호가 존재한다면, 기존 값에 이번에 찍은 시간을 더해서 갱신해줘야 한다. 
  • 차량이 나가면 map에서 삭제한다. map은 현재 있는 차량들을 담는다고 생각하기 
• 마지막으로, IN만 있고 OUT은 없는 차량들(map에 남은 애들)은 23:59분 기준으로 계산해서 더해준다.
  • 이때도 answer에 있는지 없는지 확인 후 값 넣을 것 
• 그리고 시간 계산할 때 00:00 ~ 23:59까지니까 그냥 다 분으로 환산한 다음 계산해도 된다. 
• 여담으로, 꽤 HashMap / Set에서 iterator 돌리는 코드는 봤는데 이렇게 정 keySet을 stream().sorted로 정렬해서 꺼내야 하는 문제는 처음 풀어본 것 같아서 잘 알아둬야 겠다고 생각했다.... 

 

 

🚧 전체 코드  

import java.util.*;
import java.util.stream.Collectors;
class Solution {
        public int[] solution(int[] fees, String[] records) {
            Map<String, Integer> map = new HashMap<>();
            Map<String, Integer> answer = new HashMap<>();

            for (String str : records) {
                String[] temp = str.split(" ");
                String[] times = temp[0].split(":");
                int time = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
                if (temp[2].equals("OUT")) {
                    if (answer.containsKey(temp[1])) {
                        // 만약 이미 들어왔던 애가 또 들어왔다 나가는 애라면
                        answer.put(temp[1], answer.get(temp[1]) + time - map.get(temp[1]));
                    } else {
                        answer.put(temp[1], time - map.get(temp[1]));
                    }
                    map.remove(temp[1]);
                } else {
                    map.put(temp[1], time);
                }
            }

            for (String s : map.keySet()) {
                int time = 1439 - map.get(s);
                if (answer.containsKey(s)) {
                    answer.put(s, answer.get(s) + time);
                } else {
                    answer.put(s, time);
                }

            }

            List<String> keys = answer.keySet().stream().sorted().collect(Collectors.toList());
            int[] result = new int[keys.size()];
            for (int i = 0; i < keys.size(); i++) {
                int time = answer.get(keys.get(i));
                int money = fees[1];
                if (time > fees[0]) {
                    money += Math.ceil((double)(time - fees[0]) / fees[2]) * fees[3];
                }
                result[i] = money;
            }
            return result;
        }
        
    }