2018 kakao blind recruitment
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17678
내가 생각한 문제 풀이
[시도1]
1) 셔틀 버스 리스트 생성
시간은 int로 바꿔서 푼다 : str로 푸는 것과 둘 중에 고민 했는데 0때문에 그쪽이 덜 번거로울 것 같았음
2) timetable 앞에서부터 태운다
3) 어디에 어떻게 콘을 끼울지
맨 뒤 버스만 보면 된다. 만약에 맨 뒤 버스에 자리가 있을 경우 맨 뒤 버스가 오는 시간과 같게. 맨 뒤 버스에 자리가 없을 경우 그 버스를 타는 가장 늦은 크루의 시간보다 1빠르게 도착
[시도2]
3개의 테케를 통과하지 못했다..
우선 내가 생각한 알고리즘으로 돌려 보고 분명히 모든 케이스를 커버하지 못할 거라고 생각해서 상황에 맞게 수정해야겠다고 생각했는데 그게 알고리즘의 전부였다.
이 때 포기하고 해설을 봤다
알고리즘의 전부인지는 해설을 보고 알았고, 어디 부분에서 에러가 났는지 찾으려고 코드를 다시 살펴보면서 쓸데없이 이중 반복문을 쓴 부분을 고쳤다. 결론적으로
timetable을 sort해 주어야 하는데, sort하지 않아서
"도착 순서대로 태우고 출발" 이라는 부분을 놓쳤다
예를 들어서 09:00버스에 tiemable이 [09:00 09:10 08:59] 이렇게 있다면 sort를 하지 않았기 때문에 버스에 09:00 크루가 타는 것으로 된다.
한 대만 있는 경우에는 상관없는데 버스가 여러대 있는 경우에는 연쇄적으로 에러를 발생시킨다.
시간 / 결과 / 패착
소요 시간 : 40분
결과(정확도) : 87/100
패착 :
정렬 안함
timetable이 순서대로 주어져 있지 않다는 것을 테스트케이스를 보면 알 수 있는데 안했다.. 심지어 풀이 노트에는 sort라고 적혀있었던 걸 보면 해야겠다고 생각했는데 시간으로 변환하고 sort하는 과정에서 번거롭다고 무의식적으로 생각해서 ? 아니면 걍 까먹어서 정렬을 안한 것 같다.
문제 해설
다른 풀이들의 경우 버스에 어떤 시간을 태울지 dictionary를 만들지 않고
간결하게 몇 명을 태울지만 카운트한다. 이 경우 리스트만 가지고도 구현할 수 있다.
코드
def timechangetoint(time):
hour = int(time[0:2]) * 60
minute = int(time[3:5])
return hour + minute
def intchangetotime(inttime):
hour = str(inttime // 60)
minute = str(inttime % 60)
if len(hour) == 1:
hour = '0'+hour
if len(minute) == 1:
minute = '0'+minute
time = hour + ':' + minute
return time
def solution(n, t, m, timetable):
bus = {}
start = 540
for i in range(n):
bus[start] = []
start += t
for i in range(len(timetable)):
new = timechangetoint(timetable[i])
timetable[i] = new
timetable.sort()
for time in timetable:
for b in bus: # 버스 시간 처음부터 탐색 :
if time <= b and len(bus[b]) < m: # 조건(크루원이 먼저 와야 되고 버스 좌석 있어야) 맞으면
bus[b].append(time) # 추가
break
con = list(bus.keys())[-1]
if len(bus[con]) < m:
return intchangetotime(con)
else:
return intchangetotime(max(bus[con])-1)
추가 공부
zfill
파이썬 문자열 앞 0으로 채우기
zfill(자릿수)
#002
"2".zfill(3)
#50000
"50000".zfill(5)
#00123
"123".zfill(5)rjust(width, [fillchar])
원하는 문자를 따로 지정해 줄 수 있다. zfill은 rjust(n, "0")인 거쥐
#002
"2".rjust(3, "0")
#"aaa1234"
"1234".rjust(7, "a")tip for me
완전히 이해하기 위해서 모든 테케를 시뮬해봤기 때문에 문제를 풀 수 있었던 것 같다. 시뮬을 더 확실하게 하고 귀납적으로 알고리즘을 정의하더라도 딱딱 뭔지알지 ?
시뮬레이션 돌리면서
어떻게 풀지 생각했다면 검증
모른다면 귀납적으로 방법 생각
그냥 무난한 문제 !..
