java 프로그래머스 2018 카카오 블라인드 1차 셔틀버스 풀이 | Map, Queue 활용

 

 

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

프로그래머스

 

# 문제 풀이 전 생각했던 것들

1. 매개변수로 주어지는 시간들이 문자열로 주어지기 때문에 :을 기준으로 split하고 모두 분(minute)으로 변환하는 메소드가 필요하다고 생각했다. 그리고 반환형이 다시 시간형이기 때문에 분으로 환산한 시간을 00:00 형식으로 변환하는 메소드도 만들어줘야겠다고 생각했다. 

 

2. 셔틀의 최대 개수가 10개고, 셔틀 별 정원의 수가 45명이니 사이즈가 작다고 생각했다. 그리고 나는 항상 이렇게 대기열, 줄서기 등의 문제가 나오면 자연스레 큐 자료구조가 생각나기 때문에 셔틀버스 시간 별로 큐를 만들어서 해당 시긴까지 도착했던 사람들을 큐에 넣어야겠다고 생각했던것 같다. 따라서 셔틀버스 도착시간(분으로 환산한 Integer 타입)을 키로 가지고, 도착한 사람들의 대기열을 value로 가지기 위해 Queue<Integer>를 만들어야겠다고 생각했다. 

 

3. 정답으로 요구한게 가장 늦은 시간을 도출해달라는 것이기 때문에, 정원이 미달이면 셔틀 도착시간과 동일하게 도착하면 되지만 정원이 초과될 경우 해당 큐에 있는 사람들 중 가장 늦게 온 사람보다 1분 더 일찍 와야한다. 

 

 

# 제출 코드 

import java.util.*;
class Solution {
    public int parseTime(String time){
        String[] parse = time.split(":");
        return Integer.parseInt(parse[0]) * 60 + Integer.parseInt(parse[1]);
    }
    public String parseString(int minute){
        int hours = minute / 60;
        int minutes = minute % 60;
        return String.format("%02d:%02d", hours, minutes);
    }
    public String solution(int n, int t, int m, String[] timetable) {       
        String answer = "";
        String startTime = "09:00";
        int nextTime = parseTime(startTime);
        int lastTime = 0;
        TreeMap<Integer, Queue<Integer>> mapping = new TreeMap<>(); // 셔틀 시간에 도착 시간 매핑
        
        // t분 간격 별 셔틀버스 도착 시간을 key로 하는 map 초기화하기 
        for(int bus=0; bus<n; bus++){
            mapping.put(nextTime, new LinkedList<Integer>());
            lastTime = nextTime;
            nextTime += t;
        }
        
        // 도착 시간 셔틀 시간에 배정
        Arrays.sort(timetable);
        for(String time : timetable){
            int arrivedTime = parseTime(time);
            Set<Map.Entry<Integer, Queue<Integer>>> entrySet = mapping.entrySet();
            for (Map.Entry<Integer, Queue<Integer>> element : entrySet){
                int busTime = element.getKey();
                if(busTime >= arrivedTime){// 셔틀 도착시간 이전에 온 사람이면
                    Queue<Integer> waiting = mapping.get(busTime);
                    if(waiting.size() >= m) continue;// 셔틀 정원 초과 시 다음 셔틀로 접근하기 위해 continue
                    waiting.offer(arrivedTime);// 셔틀에 탑승
                    break;// 다음 도착 사람으로 순회하기 위해 break
                }
            }
        }
        
        // 정답 도출을 위한 마지막 셔틀 확인
        Map.Entry<Integer, Queue<Integer>> lastEntry = mapping.lastEntry();
        Queue<Integer> lastQueue = lastEntry.getValue();
        
        if(lastQueue.size() < m) // 마지막 셔틀 정원이 덜 찼다면 이 마지막 버스 출발 시간에 탑승
            return parseString(lastEntry.getKey());
        
        int cnt = 0;
        for(int time : lastQueue){
            cnt++;
            answer = parseString(time-1); // 마지막 사람보다 1분 빨리 도착한 시간대로 저장 
            if(cnt == m) break;
        }
        return answer;
    }
}

 

 

input으로 들어오는 timetable의 시간을 분으로 환산해서 t간격별로 셔틀 도착시간들을 생성하고 해당 값을 key로, Queue를 value로 가지는 map을 초기화한다.

 

나중에 map을 hashMap에서 treeMap으로 수정하게 됐다. 문제가 요구하는 것이 셔틀을 가장 늦게 타고 출근할 수 있도록 하는 것이기 때문에, 가장 마지막에 출발하는 셔틀의 Queue를 쉽게 가져오기 위해 map의 순서를 보장하는 TreeMap으로 바꿔 내장함수인 lastEntry()를 사용했다.

 

input으로 들어온 timetable이 정렬되어있다는 명시가 없기 때문에 빠른 순서대로 Queue에 들어갈 수 있게 먼저 정렬을 해줘야한다. 그리고 정원만큼 들어갈 수 있도록 continue와 break로 정의해줬다. 

 

# 결과 

 

효율적인 구조인지는 모르겠지만 사이즈가 작아 map, queue로 만들어 이중포문 순회를 해도 된다고 생각했다.

문제에서 주어지지 않은 테스트 케이스들을 생각해내는게 어려웠다