[프로그래머스 - 셔틀버스 ] 성능 개선해보기

 

 

문제

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

프로그래머스

 

 

초기 풀이

1. Crew 객체 정의 (int time,boolean isCorn 유무 필드)

 

2. 도착 시각 배열 Crew객체 리스트로 변환 (isCorn false로 초기화)

 

3. isPossible(int 콘 도착시각) 함수 정의

 

4. isPossible함수 안에서 콘 객체 생성(isCorn = true) 후 정렬(1. time 오름차순, 2. isCorn = false 먼저,

조건 중 corn 은 같은 시간 중 가장 마지막에 있었다는 조건이 있었으므로, isCorn = true를 가장 뒤에 배치한다.)

 

5. 해당 시각에 도착 시 콘이 탈 수 있는지 판별

 

6. 콘이 도착 가능한 시각 중 '최댓값' 탐색 -> 이분탐색

 

 

 

코드

import java.util.*;

class Solution { //13:20 - 14:30
    class Crew{
        int time;
        boolean isCorn;
        
        Crew(int time, boolean isCorn){
            this.time = time;
            this.isCorn = isCorn;
        }
    }
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        int result = 0;
        List<Crew> arriveTime = new ArrayList<>();
        
        for(String now : timetable){
            String[] time = now.split(":");
            arriveTime.add(new Crew(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]), false));
        }
        
        ///timetable 시간순 정렬, 한번 하고, 

        //도착가능 최소시각 1분 최대시각 540 + n*t (이이후는 아예 못탐)
        int min = 1;
        int max = 540 + n * t;
        
        while(min <= max){
            int mid = (min + max) / 2;
            //가능하면 저장 후 더늦은 범위 탐색
            if(isPossible(mid,n,t,m,arriveTime)){
                result = Math.max(result, mid);
                min = mid + 1;
            } else{ //불가능하면 더 빠른범위 탐색
                max = mid-1;
            }
        }
        answer = String.format("%02d:%02d", result/60, result%60);
        return answer;
    }
    
    private boolean isPossible(int cornArriveTime,int n, int t, int m, List<Crew> arriveTime){
        List<Crew> tmp = new ArrayList<>(arriveTime);
        tmp.add(new Crew(cornArriveTime,true));
        Collections.sort(tmp, (a,b) ->{
            if(a.time == b.time) return Boolean.compare(a.isCorn,b.isCorn);
            return a.time - b.time;
        });
        int shuttleSort = 0;
        int riderIdx = 0;
        
        while(shuttleSort < n){
            for(int i =0; i< m; i++){
                //탈수있다면
                if(tmp.get(riderIdx).time <= 540 + t*shuttleSort){
                    if(tmp.get(riderIdx).isCorn) return true;
                    riderIdx++;
                } else{ //탈수없다면 다음버스(for문 탈출)
                    break;
                }
            }
            shuttleSort++;
        }    
       return false;
    }
}

 

 

결과

 

통과하긴 하였으나, sPossible(mid, ...)호출할 때마다 매번 리스트를 새로 만들고 배열을 다시 정렬하는게 비효율적이라고 생각

그래서 개선할 수 있는 방법과, 다른 풀이방법을 찾아보았다.

 

 

 

 

시간 복잡도

• 1. 이진 탐색: log(max-min) ≈ 10
• 2. isPossible 1회당
  • 복사 O(N)
  • 정렬 O(N log N)
  • 버스탑승 O(N)

-> O(log T · N log N)

 

 

 

 

 

 

 

 

 

 

개선코드 1. 콘의 위치만 binarySearch로 계산 

 

• cornArriveTime을 실제 리스트에 삽입하지 않고, binarySearch로 삽입할 위치만 찾은 뒤
  탑승시킬 때 그 위치에 콘이 있다고 가정해서 처리.

시간복잡도

• 초기 정렬: O(N log N)
• binarySearch: O(log N)
• 버스탑승: O(N)
• 이진 탐색 반복: O(log T) ≈ 10
  → 전체: O(N log N + N log T)

 

 

 

코드

import java.util.*;

class Solution {
    class Crew {
        int time;
        boolean isCorn;

        Crew(int time, boolean isCorn) {
            this.time = time;
            this.isCorn = isCorn;
        }
    }

    public String solution(int n, int t, int m, String[] timetable) {
        int result = 0;
        List<Crew> arriveTime = new ArrayList<>();

        // 1. 입력 크루 저장
        for (String now : timetable) {
            String[] time = now.split(":");
            arriveTime.add(new Crew(
                Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]),
                false
            ));
        }

        // 2. 한 번만 정렬
        arriveTime.sort((a, b) -> a.time - b.time);

        // 3. 이진 탐색 (콘이 탈 수 있는 가장 늦은 시각)
        int min = 1;
        int max = 540 + n * t;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (isPossible(mid, n, t, m, arriveTime)) {
                result = Math.max(result, mid);
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        return String.format("%02d:%02d", result / 60, result % 60);
    }

    private boolean isPossible(int cornArriveTime, int n, int t, int m, List<Crew> arriveTime) {
        // 1. 콘의 삽입 위치 찾기
        int pos = Collections.binarySearch(arriveTime, new Crew(cornArriveTime, true),
            (a, b) -> {
                if (a.time == b.time) return Boolean.compare(a.isCorn, b.isCorn);
                return a.time - b.time;
            });
        if (pos < 0) pos = -(pos + 1);

        // 2. 시뮬레이션 (pos에 콘이 있다고 가정)
        int idx = 0; 

        for (int bus = 0; bus < n; bus++) {
            int departure = 540 + bus * t;
            int count = 0;

            while (count < m) {
                // 콘 먼저 고려
                if (idx == pos && cornArriveTime <= departure) {
                    return true;
                }

                // 일반 크루 태움
                if (idx < arriveTime.size() && arriveTime.get(idx).time <= departure) {
                    idx++;
                    count++;
                } else break;
            }
        }
        return false;
    }
}

 

 

 

 

결과

 

 

 

 

 

 

 

 

 

개선코드 2. 그리디로 풀기

이 문제(셔틀버스)는 사실 크게 보면 “마지막 셔틀버스에 콘이 어떻게 타느냐”를 따지는 문제

즉 탑승 가능 여부를 이진탐색으로 보는것보다, 마지막 버스만 따지면 된다.

• n번의 셔틀버스가 09:00부터 t분 간격으로 옴.
• 각 버스는 최대 m명까지만 태울 수 있음.
• 크루들은 timetable에 주어진 시간에 도착해서 먼저 도착한 순서대로 버스에 탐.
• 콘이 마지막 셔틀을 타려면 언제 도착해야 하는가?

풀이

1. 크루들 시간순 정렬

2. 각 버스별로 정원만큼 태움 (버스마다 “도착 시간이 출발 시간 이하”인 사람 중에서 최대 m명 태움)

3. 마지막 버스에서 콘의 도착 시간 결정

• 정원이 남아있다 → 콘은 마지막 버스 출발 시간에 와도 탈 수 있음
• 정원이 꽉 찼다→ 콘은 마지막으로 탄 사람보다 1분 더 빨리 와야 함

 

 

 

시간 복잡도

1. 정렬 : Collections.sort → O(N log N)
2. 버스탑승 :  O(N)

-> O(N log N + N) = O(N log N)

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        // 1. 크루 도착 시간을 분으로 변환
        List<Integer> crew = new ArrayList<>();
        for (String time : timetable) {
            String[] sp = time.split(":");
            int minutes = Integer.parseInt(sp[0]) * 60 + Integer.parseInt(sp[1]);
            crew.add(minutes);
        }
        Collections.sort(crew); // 2. 한 번만 정렬

        int busTime = 540; // 첫 셔틀 09:00 (540분)
        int idx = 0;       // 현재 태울 크루 인덱스

        // 3. 각 버스 출발 시각마다 탑승 시뮬레이션
        for (int bus = 0; bus < n; bus++) {
            int cnt = 0; // 이번 버스 탑승 인원

            while (cnt < m && idx < crew.size() && crew.get(idx) <= busTime) {
                idx++;
                cnt++;
            }

            // 4. 마지막 버스라면 콘의 도착 시간 결정
            if (bus == n - 1) {
                if (cnt < m) {
                    // 정원 안 찼음 → 버스 출발 시간에 맞춰 와도 됨
                    return String.format("%02d:%02d", busTime / 60, busTime % 60);
                } else {
                    // 정원 꽉 참 → 마지막 크루보다 1분 일찍 와야 함
                    int lastCrew = crew.get(idx - 1) - 1;
                    return String.format("%02d:%02d", lastCrew / 60, lastCrew % 60);
                }
            }

            busTime += t; // 다음 버스 출발 시간
        }

        return ""; // 도달 안 함
    }
}

 

 

 

 

결과