강의로 돌아가기
전현서

카카오 문제치고는 뭔가 악랄하지는 않은 문제 해설

카카오문제 레벨3치고는 함정카드가 거의 안깔려있는 문제입니다.
오히려 염려가 되는 상황을 고려를 안해도 문제가 풀립니다.
그냥 문제를 코드를 구현만 하면, 풀 수 있는 심플한 문제같습니다.

시간 문제는 이제 대부분 제일 적은단위로 변환하여 푸는 것이 제일 계산이 쉽고 효율적입니다.
해당 문제에서는 전부 분으로 환산하여 계산하는 것이 좋을 것 같군요.
0~1439분 범위의 값으로 변환이 될겁니다.

마찬가지로, 역연산도 필요하겠죠? 답이 요구하는 형태 처음에 주어지는 문자열 형태의 HH:MM 과 같은 형식이니 말이죠.

문자열을 분으로 변환.

def convert_min(s):
    h, m = s.split(':') # ':'를 기준으로 시와 분 분리하기.
    return int(h) * 60 + m #시에 60을 곱하여 분으로 변환후 분과 합산뒤 반환.

분을 문자열로 변환.

def convert_string(m):
    h = m // 60
    m = m % 60
    return '{0:02d}:{1:02d}'.format(h, m)

파이썬 코드로는 대충 위와 같이 표현할 수 있습니다.
문법적인 오류가 있을 수도 있습니다.

이렇게 위와 같이 간단히 문자열에서 분으로, 분에서 문자열로 바꾸는 것이 가능하다면,
나머지는 쉬울 것이다.

전체적인 알고리즘은 아래와 같다.

  • timetable의 데이터를 전부 문자열에서 분으로 변환.
  • 분으로 변환된 timetable을 오름차순으로 정렬.
  • 540분부터 n-1번 t만큼의 step으로 for문을 반복적으로 돌림.
  • timetable[0]의 데이터가 현재 for문변수보다 이하일 경우, 카운트함. 그리고 해당 값을 삭제.
  • 카운트가 m이 되면 다음 버스로 넘김.
  • 막차가 왔을 경우, 콘이 최대한 뒤로 탈 수 있게 유도함.

이 문제에서 콘이 제일 뒤늦게 도착해도 버스를 탈 수 있는 조건들.

  • 콘은 항상 제일 막차만 고집한다.
  • 막차가 도착한 시간에 대기열에 있는 사람이, m보다 작으면 콘은 버스도착시간에 맞춰 도착함.
  • m보다 클경우, 마지막 순번보다, 1분 더빨리 도착해버림.
  • 콘이 막차를 못타는 테스트케이스는 존재도 하지 않음(이거 뭐임?)

위와 같은 알고리즘대로 코드를 구현하면 문제를 풀 수 있게 해놨습니다.
조건 중에서 콘은 항상 막차만 탈 수 있다는 조건이라, 대충해도 통과합니다.
반례라는게 존재하지 않게 만든 문제입니다.
약간, 허술한 감이 없잖아 있습니다.

아래부터는 저의 주관적인 생각입니다만,
콘이 막차를 못타는 경우가 존재해야합니다.
막차가 왔지만, 수용인원 m이 1명일 경우이죠.
그런 경우에, 대기열에 있는 사람이 도착시간과 일치하게 도착한사람이 존재한다면,
콘은 항상 동시간대에 도착한 사람중에 제일 뒤늦게 오므로, 막차를 타지 못하게 됩니다.
이런 경우는 막차의 하나 전차의 제일 뒤에 타야하는 것이 맞을 텐데..
이 문제는 그런 테스트케이스를 고려하지 않은 것 같습니다.
아마 저와 같은 생각을 하고, 코드를 짜신 분들이 다수 존재할 것 같습니다.

2 개의 답변
서병일

n=2, t=1, m=2, ["09:00", "09:00", "09:00", "09:00"], "08:59"
예제로 주어진 이 경우에, 첫차는 9:00, 막차는 9:01이니까, 콘은 막차가 아닌 첫차에 탑승했습니다. 오해가 있으신 것 같아요... 마지막 탑승자보다 1분 더 빨리 도착하더라도 마지막 탑승자가 여러 명이면 막차가 아닌 앞차들을 탈 가능성이 생기네요. 하지만 중요한 건 어떤 버스냐가 아니라, 시간이니까 문제가 풀리셨을 듯 합니다.

  • 서병일

    사실, 14, 15, 16에서 막혀 전현서님 글을 읽다가 제가 답변 달면서 오히려 문제가 단순함을 깨닫고 통과했습니다. 감사합니다!^^

    서병일―2022.10.21 15:28
박형균

수용인원이 1명 이라도, 그 인원보다 1분 일찍오면 탈 수 있습니다. 문제의 조건이 "크루원은 도착시간은 00:01 <= time <= 23:59 이다." 이므로 콘은 항상 버스를 탈 수 있습니다. 해당 조건이 만약 00:00 <= time <= 23:59 라면 n = 1, t = 1, m = 1, ["00:00"] 이 경우처럼 콘이 못타는 경우가 발생하기는 합니다. 따라서 문제에는 모든 테스트케이스를 고려하고 있는것으로 보여집니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다.