[구현] 동영상 재생기 (Lv.1)
걸린 시간
25분
접근 방식
단순 구현 문제지만 여러개의 조건을 잘 분기해야하는 문제였다.
비디오 길이가 분:초 형식의 문자열이기에 이를 단순 초 데이터인 int형 데이터로 바꿔주는 함수를 구현해 풀었다.
정답 코드
def decode(time):
m, s = time.split(":")
return int(m)*60 + int(s)
def encode(time):
m = time // 60
s = time % 60
return '{:02d}:{:02d}'.format(m,s)
def solution(video_len, pos, op_start, op_end, commands):
time = decode(pos)
if decode(op_start) < time < decode(op_end):
time = decode(op_end)
for c in commands:
if c == "prev":
time -= 10
if c == "next":
time += 10
if time < 0:
time = 0
if time > decode(video_len):
time = decode(video_len)
if decode(op_start) <= time <= decode(op_end):
time = decode(op_end)
return encode(time)배운점
항상 헷갈리는 문자열 포맷팅이다
'{:02d}:{:02d}'.format(m,s)[이분탐색] 퍼즐 게임 챌린지 (Lv.2)
걸린 시간
45분
접근 방식
단순하게 최대 숙련도를 설정하고 -1씩 하면서 다 조사하는 브루트포스로 풀려고 했지만 시간초과가 나와 이분탐색으로 전환했다.
정답 코드
def is_possible(level, diffs, times, limit):
l = len(diffs)
time_prev = 0
time_cur = 0
time_total = 0
for i in range(l):
time_cur = times[i]
time_total += (diffs[i]-level if diffs[i] > level else 0) * (time_prev + time_cur) + time_cur
time_prev = time_cur
if time_total > limit:
return False
else:
return True
def solution(diffs, times, limit):
level_min = max(diffs)
level_max = 1
while level_max <= level_min:
level_mid = (level_min + level_max) // 2
if is_possible(level_mid, diffs, times, limit):
level_min = level_mid - 1
else:
level_max = level_mid + 1
return level_max배운점
이분탐색의 low, mid, high를 설정하는 것이 꽤나 헷갈린다.
정확한 값을 찾는 경우
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2 # 오버플로우 방지용 표현 (Python은 안전하지만 습관화)
if arr[mid] == target:
return mid # 정답 발견!
elif arr[mid] < target:
low = mid + 1 # mid보다 오른쪽 탐색
else:
high = mid - 1 # mid보다 왼쪽 탐색
return -1 # 값을 찾지 못한 경우"조건을 만족하는 최솟값" 또는 "조건을 만족하는 최댓값"을 찾는 유형
조건을 만족하는 최솟값 찾기 (Lower Bound)
low = 최소_가능_값
high = 최대_가능_값
while low < high:
mid = (low + high) // 2
if is_possible(mid): # 조건을 만족한다면?
# 더 작은 값도 만족하는지 확인하기 위해 왼쪽으로 좁힘 (mid 포함)
high = mid
else:
# mid는 조건을 만족하지 못하므로 완전히 제외하고 오른쪽으로
low = mid + 1
# 두 포인터가 만난 지점(low 또는 high)이 정답
return low조건을 만족하는 최댓값 찾기 (Upper Bound)
low = 최소_가능_값
high = 최대_가능_값
while low < high:
# 💡 무한 루프 방지를 위해 올림 처리 (+1)
mid = (low + high + 1) // 2
if is_possible(mid): # 조건을 만족한다면?
# 더 큰 값도 만족하는지 확인하기 위해 오른쪽으로 좁힘 (mid 포함)
low = mid
else:
# mid는 조건을 만족하지 못하므로 완전히 제외하고 왼쪽으로
high = mid - 1
return low[구현?] 충돌위험 찾기 (Lv.2?)
걸린 시간
86분
접근 방식
routes에서 이동 순서를 단위 시간 별로 다 넣어주는 이동경로 배열을 만들어주고,
다 하나씩 돌려가면서 현재 위치를 갱신하며 로봇이 같이 있는 위험한 위치의 개수를 체크하는 방식으로 구현했다.
정답 코드
def is_danger(locs):
result = 0
locs_list = [locs[i][0]*100+locs[i][1] for i in range(len(locs))]
# 현 위치 중 로봇이 2개 이상인 위치의 개수
set_list = list(set(locs_list))
for val in set_list:
if locs_list.count(val) > 1:
result += 1
return result
def solution(points, routes):
answer = 0
locs = []
schedules = []
for route in routes:
locs.append(points[route[0]-1][:])
for route in routes:
schedule = []
for idx in range(len(route)-1):
# a(루트의 현 위치) (points[route[idx]]) / b(루트의 목적지) (points[route[idx]])
ax, bx = points[route[idx]-1][1], points[route[idx+1]-1][1]
ay, by = points[route[idx]-1][0], points[route[idx+1]-1][0]
schedule.extend([(1 if by > ay else -1) for _ in range(abs(by-ay))] + [(2 if bx > ax else -2) for _ in range(abs(bx-ax))])
schedules.append(schedule)
time = 0
for schedule in schedules:
time = max(time, len(schedule))
cnt = 0
for idx in range(time):
# 현재 위치 위험감지 (스타트포함)
cnt += is_danger(locs)
for i, schedule in enumerate(schedules):
# 만약 끝난 스케줄이면 스킵
if idx > len(schedule) - 1:
locs[i] = [(i+1)*-1, (i+1)*-1]
continue
# x좌표 이동
if schedule[idx] % 2 == 0:
locs[i][1] += (1 if schedule[idx] == 2 else -1)
# y좌표 이동
else:
locs[i][0] += (1 if schedule[idx] == 1 else -1)
# 마지막 위치 위험감지
cnt += is_danger(locs)
return cnt배운점
locs.append(points[route[0]-1][:])여기서 얕은복사 때문에 [:]로 깊은 복사 해야했다.
이거땜에 30분이 날라갔다.
append에 넣는 값은 어떤 값을 참조하는 식이 아닌 복사하는 식으로 해야한다는 것을 염두해주자.
