[JavaScript] Programmers 셔틀버스 (JS)

SanE·2024년 2월 14일
2018 Kakao BlindJavaScriptalgorithmprogrammers

Algorithm

목록 보기
48/127

셔틀버스

📚 문제 설명

문제에 대한 설명은 너무 길기 때문에 아래 입출력을 보면서 설명하겠다.
아래 표에서
n 은 버스의 수
t 는 배차 간격
m 은 버스에 태울 수 있는 최대 인원
timetable 은 주인공을 제외한 사람들이 버스 정류장에 나오는 시간이다.

ntmtimetableanswer
115["08:00", "08:01", "08:02", "08:03"]"09:00"
2102["09:10", "09:09", "08:00"]"09:09"
212["09:00", "09:00", "09:00", "09:00"]"08:59"
115["00:01", "00:01", "00:01", "00:01", "00:01"]"00:00"
111["23:59"]"09:00"
106045["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]"18:00"

이 문제에서 몇가지 조건이 있는데 그건 아래와 같다.

조건 1 - 버스는 무조건 09:00 에 첫 차가 있다.
조건 2 - 23 : 59 분에는 모든 인원은 다시 집으로 돌아간다.
조건 3 - 주인공은 게으르기 때문에 최대한 늦게 가는 것을 선호한다.
조건 4 - 주인공과 같은 시간에 줄을 서기 위해 온 사람이 있을 경우 주인공은 항상 그 사람보다 뒤에 선다.
조건 5 - 사람들은 00:00 부터 23:59 사이에 와서 줄을 선다.
조건 6 - 버스 도착시간과 똑같이 도착하면 버스를 탈 수 있다.

그럼 위의 조건을 준수하여 표를 해석해 보자

ntmtimetableanswer
115["08:00", "08:01", "08:02", "08:03"]"09:00"
  • 첫번째 입력에 경우 5 명의 사람을 태우는 버스가 1 대가 1 분의 간격을 두고 온다는 뜻이다.
    • timetable 변수에 4명의 사람이 있고 모두 9시 전에 왔다.
    • 그럼 처음이자 마지막 버스인 09:00 에 사람을 모두 태우고 주인공까지 타면 딱 5 명이 전부 갈 수 있다.
    • 따라서 주인공은 버스의 도착 시간과 같은 09:00 에 도착하면 된다.
ntmtimetableanswer
2102["09:10", "09:09", "08:00"]"09:09"

그럼 위의 과정도 똑같이 진행하면 된다.

  • 첫번째 입력과 똑같이 해석을 진행 한다. (2명을 태우는 버스 2대가 10분 간격으로)
    • 우선 첫번째 버스가 09:00 에 도착했다고 가정하자
    • 첫차가 왔을 때 대기중은 인원은 08:00 에 미리 와 있던 사람 한명이다. 따라서 버스는 한명만 타고 간다.
    • 그 후 , 두번째 버스가 09:10 에 도착 했을 때, 사람이 2명이 있다.
    • 그런데 버스는 2명만 탈 수 있다. 그럼 주인공이 최대한 늦게 도착을 하고 싶으면, 09:09 에 도착해야 한다.
      • 주인공이 09:10 에 도착하면 위의 조건 4 때문에 ["09:10", "09:09"] 이렇게 사람들이 대기중
ntmtimetableanswer
106045["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]"18:00"

그럼 이제 나머지는 위의 과정대로 진행하면 되고 마지막 입력만 설명하고 풀이로 넘어가겠다.

  • 모든 사람이 23:59 에 와서 대기 중이다.
  • 그러나 버스는 18:00 이 마지막 버스
  • 따라서 주인공은 마지막 버스 시간에 와서 버스를 타면 된다.

👨🏻‍💻 풀이 과정

이 문제를 보고 나는 가장 먼저 JavaScript 에 있는 Date() 를 생각했다.
따라서 모든 시간을 Date() 객체로 저장을 진행한 후, 변수들에 저장되어 있는 시간을 비교하며, 문제를 풀기로 했다.
전체적인 로직은 다음과 같다.

변수 생성 및 정렬 작업

  • 버스 도착 시간을 BusArrive 배열에 Date() 객체를 이용하여 저장
  • 사람들이 도착하는 시간 timetable 을 sort() 를 이용해 순서대로 정렬
  • 사람들의 도착 시간 timetable 또한 Date() 객체로 저장

변수 생성, 정렬 코드

	// 로컬 환경에서 풀이하기 위한 변수 입력
    let n = 10;
    let timetable = ["09:00", "09:10", "09:20", "09:30", "09:40", "09:50", "10:00", "10:10", "10:20", "10:30", "10:40", "10:50"];
    let t = 25;
    let m = 1;
	// sort()를 이용해 정렬 후 
    timetable = timetable.sort((a,b) => {
        return a <= b? -1:1;
    }).map(v => v.split(':').map(Number));
	// 버스 도착 시간 배열 생성
    let BusArrive = [];
	// 버스 도착 시간 입력
    for (let i = 0; i < n; i++) {
        let bus = new Date();
        bus.setHours(9, t * i);
        BusArrive.push(bus);
    }
	// timetable 의 모든 배열 값을 Date() 객체로
    timetable = timetable.map(v => {
        let UserTime = new Date();
        UserTime.setHours(v[0], v[1]);
        return UserTime;
    });

메인 로직

  • 반복문 진행 BusArrive 배열을 돌며 버스 도착 시간을 확인
    • 버스 도착 시간에 이미 도착해 있는 사람들은 timetable 에서 제거
    • 만약 마지막 버스일 때, 가정문 실행
    • 남아 있는 사람이 m 보다 많고, timetable 의 m 번째 사람이 버스 도착 시간 이전에 왔다면
      • 주인공은 m 번째 사람보다 일찍 와야 마지막 버스를 탄다.
    • 만약 위의 가정 외의 상황이라면
      • 주인공은 BusArrive 마지막 시간에 도착을 하면 마지막 버스를 탈 수 있다.

메인 로직 코드

    const takeBus = () => {
      	// 주인공이 버스를 타야하는 시간
        let myTime = new Date();
        for (let i = 0; i < BusArrive.length; i++) {
          	// 버스에 타는 사람 수
            let cnt = 0;
          	// 만약 마지막 버스가 아니라면
            if (i !== BusArrive.length - 1) {
              // 버스가 만차가 될 때까지
                while (cnt < m) {
                  	// 만약 timetable 맨 앞(가장먼저 도착) 사람이 버스 도착 시간보다 빨리 왔다면,
                    if (timetable[0] <= BusArrive[i]) {
                      	//인원 증가
                        cnt++;
                      	//맨 앞 사람 제거
                        timetable.shift();
                      // 만약 맨 앞(가장먼저 도착) 사람이 버스 시간보다 늦게 왔다면 break
                    } else break;
                }
              // 만약 마지막 버스라면
            } else {
              	// m번째 사람이 도착 시간보다 일찍 왔다면,
              	// 그리고 time table에 인원이 m보다 크다면,
              	// 위의 조건 대로라면, 주인공은 무조건 m번째 사람보다 1분 일찍 와야한다.
                if (timetable[m - 1] <= BusArrive[i] && timetable.length >= m) {
                    myTime = timetable[m - 1];
                    myTime.setMinutes(myTime.getMinutes() - 1);
                  // 만약 그 외의 상황이라면 주인공은 마지막 버스 시간에 맞춰 오면 됨
                } else {
                    myTime = BusArrive[i];
                }
            }
        }
      	// padStart 함수를 이용해 1 이 아닌 01 로 출력 되도록 수정
        return `${myTime.getHours().toString().padStart(2, '0')}:${myTime.getMinutes().toString().padStart(2, '0')}`;
    };
	// 로컬 환경에서 확인하기 위해 콘솔 창을 확인
    console.log(takeBus());

그럼 위의 함수대로 전체 코드를 확인하면 다음과 같다.

    // 로컬 환경에서 풀이하기 위한 변수 입력
    let n = 10;
    let timetable = ["09:00", "09:10", "09:20", "09:30", "09:40", "09:50", "10:00", "10:10", "10:20", "10:30", "10:40", "10:50"];
    let t = 25;
    let m = 1;
    // sort()를 이용해 정렬 후
    timetable = timetable.sort((a,b) => {
        return a <= b? -1:1;
    }).map(v => v.split(':').map(Number));
    // 버스 도착 시간 배열 생성
    let BusArrive = [];
    // 버스 도착 시간 입력
    for (let i = 0; i < n; i++) {
        let bus = new Date();
        bus.setHours(9, t * i);
        BusArrive.push(bus);
    }
    // timetable 의 모든 배열 값을 Date() 객체로
    timetable = timetable.map(v => {
        let UserTime = new Date();
        UserTime.setHours(v[0], v[1]);
        return UserTime;
    });

    const takeBus = () => {
        // 주인공이 버스를 타야하는 시간
        let myTime = new Date();
        for (let i = 0; i < BusArrive.length; i++) {
            // 버스에 타는 사람 수
            let cnt = 0;
            // 만약 마지막 버스가 아니라면
            if (i !== BusArrive.length - 1) {
                // 버스가 만차가 될 때까지
                while (cnt < m) {
                    // 만약 timetable 맨 앞(가장먼저 도착) 사람이 버스 도착 시간보다 빨리 왔다면,
                    if (timetable[0] <= BusArrive[i]) {
                        //인원 증가
                        cnt++;
                        //맨 앞 사람 제거
                        timetable.shift();
                        // 만약 맨 앞(가장먼저 도착) 사람이 버스 시간보다 늦게 왔다면 break
                    } else break;
                }
                // 만약 마지막 버스라면
            } else {
                // m번째 사람이 도착 시간보다 일찍 왔다면,
                // 그리고 time table에 인원이 m보다 크다면,
                // 위의 조건 대로라면, 주인공은 무조건 m번째 사람보다 1분 일찍 와야한다.
                if (timetable[m - 1] <= BusArrive[i] && timetable.length >= m) {
                    myTime = timetable[m - 1];
                    myTime.setMinutes(myTime.getMinutes() - 1);
                    // 만약 그 외의 상황이라면 주인공은 마지막 버스 시간에 맞춰 오면 됨
                } else {
                    myTime = BusArrive[i];
                }
            }
        }
        // padStart 함수를 이용해 1 이 아닌 01 로 출력 되도록 수정
        return `${myTime.getHours().toString().padStart(2, '0')}:${myTime.getMinutes().toString().padStart(2, '0')}`;
    };
    // 로컬 환경에서 확인하기 위해 콘솔 창을 확인
    console.log(takeBus());

아래와 같이 무사히 통과를 하게 된다.

💡오류 발생

문제 확인

그런데 여기서 한가지 문제가 발생하는데 로컬 환경에서 실행을 하면 매번 결과가 조금씩 바뀌게 된다.

ntmtimetableanswer
10251["09:00", "09:10", "09:20", "09:30", "09:40", "09:50", "10:00", "10:10", "10:20", "10:30", "10:40", "10:50"]"10:29"

예를 들어 위와 같은 입력을 주고, 실행을 위의 코드를 실행 시키면
아래와 같이 나와야 하는 10:29 의 값이 아닌 10:19 의 값이 나오게 된다.

그리고 코드를 변경하지 않고 몇번을 더 실행 시키면
아래와 같이 올바른 결과가 출력이 되기도 한다.

해결 과정

따라서 이 문제가 뭐 때문에 발생하는 문제인지 알기 위해 변수들부터 체크를 해보았다.

  • 우선 timetable 변수에 저장된 Date() 객체들을 확인 했다.
    • getHours() 와 getMinutes() 로 확인한 값 모두 정상
  • BusArrive 값 확인
    • getHours() 와 getMinutes() 로 확인한 값 모두 정상
  • 메인 로직 확인
    • 가정문에 들어가 있는 로직 확인
    • 내가 생각한 것 외의 반례가 있는지 확인

여기까지 확인 했을 때 도저히 이해가 되지 않았다.

그런데 여기서 문제가 되는 답이 10:19 인데 그렇다면 메인 로직에서 가정문 속에 부등호를 이용해 Date() 객체들을 서로 비교하는 부분이 문제일 것이라고 생각했다.
그래서 가장 근본적인 Date() 객체에 대해 자세히 확인했고,
여기서 문제를 찾을 수 있었다.

결론

문제의 결론부터 말하고 시작하자면 new Date() 로 선언 당시에 들어 있던 밀리초(millisecond) 때문인 것 같다.

new Date() 로 선언을 하면 현재 로컬 시간을 기준으로 값이 들어가게 된다.
그래서 각각의 Date() 객체, 즉 timetable 과 BusArrive 내부 값을 확인 했을 때
시간과 분, 초를 확인 했을때는 내가 원하는대로 알아서 잘 초기화되어서 들어가 있지만,

밀리초(millisecond) 의 경우 처음 선언 당시의 밀리초(millisecond)가 들어가 있었고,
이 값 때문에 연도, 시간, 분, 초 가 서로 일치 해도 부등호 > < = 를 이용해 비교를 진행하면,
밀리초(millisecond) 때문에 다르게 나오는 것이다.

그렇다면 내가 작성한 코드에서는 초(second)는 초기화하지 않았는데 왜 초기화가 되어서 들어갈까?
나는 이 이유를 2개지라고 생각했다.

  • 변수가 선언 되는 서로 사이 간격이 초(second) 단위가 아니기 때문
    • 변수가 선언되는 당시의 시간은 위의 코드에서는 초 단위까지는 걸리지 않고 밀리초(millisecond) 단위의 차이만 생겼다
  • 변수를 선언 할 때 Date()에 있는 내장 함수인 set 종류의 문제
    • set 종류의 내장 함수를 확인하면, 알 수 있지만, 내가 만약 10시라고 선언을 하면 00분까지 함께 저장이 된다.
    • 따라서 내가 초기화를 해준 단위의 아래까지는 0으로 초기화를 해준다고 생각할 수도 있을 것 같다.
    • 예를 들어 setHours(9) 를 하면 9시 00분이 저장이 된다는 것이다.

정확한 이유가 무엇이 되었든, 처음 선언할 때

	//기존처럼 이렇게 선언하는 것이 아니라
	let bus = new Date();

	// 아래와 같이 (연도, 월, 일, 시간, 분, 초)를 지정하여 선언하면 해결된다.
    let bus = new Date(2024, 0, 4, 0, 0, 0);

전체 코드

// 로컬 환경에서 풀이하기 위한 변수 입력
    let n = 10;
    let timetable = ["09:00", "09:10", "09:20", "09:30", "09:40", "09:50", "10:00", "10:10", "10:20", "10:30", "10:40", "10:50"];
    let t = 25;
    let m = 1;
    // sort()를 이용해 정렬 후
    timetable = timetable.sort((a,b) => {
        return a <= b? -1:1;
    }).map(v => v.split(':').map(Number));
    // 버스 도착 시간 배열 생성
    let BusArrive = [];
    // 버스 도착 시간 입력
    for (let i = 0; i < n; i++) {
        let bus = new Date(2024, 0, 4, 0, 0, 0);
        bus.setHours(9, t * i);
        BusArrive.push(bus);
    }
    // timetable 의 모든 배열 값을 Date() 객체로
    timetable = timetable.map(v => {
        let UserTime = new Date(2024, 0, 4, 0, 0, 0);
        UserTime.setHours(v[0], v[1]);
        return UserTime;
    });
    timetable.getMinutes()
    const WhenShouldGo = () => {
        // 주인공이 버스를 타야하는 시간
        let myTime = new Date(2024, 0, 4, 0, 0, 0);
        for (let i = 0; i < BusArrive.length; i++) {
            // 버스에 타는 사람 수
            let cnt = 0;
            // 만약 마지막 버스가 아니라면
            if (i !== BusArrive.length - 1) {
                // 버스가 만차가 될 때까지
                while (cnt < m) {
                    // 만약 timetable 맨 앞(가장먼저 도착) 사람이 버스 도착 시간보다 빨리 왔다면,
                    if (timetable[0] <= BusArrive[i]) {
                        //인원 증가
                        cnt++;
                        //맨 앞 사람 제거
                        timetable.shift();
                        // 만약 맨 앞(가장먼저 도착) 사람이 버스 시간보다 늦게 왔다면 break
                    } else break;
                }
                // 만약 마지막 버스라면
            } else {
                // m번째 사람이 도착 시간보다 일찍 왔다면,
                // 그리고 time table에 인원이 m보다 크다면,
                // 위의 조건 대로라면, 주인공은 무조건 m번째 사람보다 1분 일찍 와야한다.
                if (timetable[m - 1] <= BusArrive[i] && timetable.length >= m) {
                    myTime = timetable[m - 1];
                    myTime.setMinutes(myTime.getMinutes() - 1);
                    // 만약 그 외의 상황이라면 주인공은 마지막 버스 시간에 맞춰 오면 됨
                } else {
                    myTime = BusArrive[i];
                }
            }
        }
        // padStart 함수를 이용해 1 이 아닌 01 로 출력 되도록 수정
        return `${myTime.getHours().toString().padStart(2, '0')}:${myTime.getMinutes().toString().padStart(2, '0')}`;
    };
    // 로컬 환경에서 확인하기 위해 콘솔 창을 확인
    console.log(WhenShouldGo());

위와 같이 가꾸면 이존에 있던 문제도 해결되고, 채점도 무사히 통과하게 된다.

🧐 후기

위와 같은 문제들을 해결하고 테스트를 통과한 후에 다른 사람들의 코드를 확인해 봤다.
그런데 다른 사람들의 경우 모든 시간을 분 단위로 만든 후에 서로 비교하여 문제를 푸는 것을 확인했다.
무슨 풀이가 더 옳은 풀이인지는 잘 모르겠지만, 나는 내 풀이대로 풀면서 Date() 객체에 대해 더욱 더 잘 알게 된것 같아서 좋았다.

profile
SanE
JavaScript를 사용하는 모두를 위해...
이전 포스트

[JavaScript] 백준 9935 문자열 폭발 (JS)

다음 포스트

[JavaScript] 백준 9251 LCS (JS)

0개의 댓글