구현
https://school.programmers.co.kr/learn/courses/30/lessons/176962
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
! 중복된 코드기 때문에 해당 어떤 부분에서 틀렸는지는 아래 설명란에서 설명하겠습니다.!
코드 (틀린 코드 41.7점)
# 점수 41.7점
def solution(plans):
answer = []
for idx, value in enumerate(plans):
h = int(value[1].split(":")[0])
m = int(value[1].split(":")[1])
plans[idx][1] = (h * 60) + m
plans[idx][2] = int(value[2])
# 시간이 빠른 순서대로 정렬
plans.sort(key=lambda x : -x[1])
# 진행해야될 과제가 있을때까지
current = None
start = 0
end = 0
wait = []
new = []
while plans:
p = plans.pop()
# 진행중인 과제가 아직 없다면 현재 가지고 온 과제를 진행시킨다.
if current is None:
current = p
start = p[1]
end = start + p[2]
continue
# 일단 고려해야되는거는
# 현재 진행하는 과제가 끝나는 시간 전에 진행해야될 과제라면 현재 진행하고 있는 과제는 잠시 멈춰둔다.
if p[1] < end:
com = abs(start-p[1])
current[2] -= com
wait.append(current)
current = p
start = p[1]
end = start + p[2]
continue
else:
# 잠시 멈춰둔 과제가 있다면 멈춰둔 과제를 진행하는데
answer.append(current[0])
if p[1] > end:
current = wait.pop()
start = end
end = start + current[2]
if p[1] < end:
current[2] -= abs(p[1] - start)
wait.append(current)
current = p
start = p[1]
end = start + p[2]
continue
elif p[1] == end:
if wait:
current = p
start = p[1]
end = start + p[2]
continue
else:
current = p
start = p[1]
end = start + p[2]
continue
if current is not None:
wait.append(current)
for idx in range(len(wait)-1, -1, -1):
answer.append(wait[idx][0])
# if current is not None:
return answer
코드 (틀린 코드 66.7점)
# 66.7점
def solution(plans):
answer = []
for idx, value in enumerate(plans):
h = int(value[1].split(":")[0])
m = int(value[1].split(":")[1])
plans[idx][1] = (h * 60) + m
plans[idx][2] = int(value[2])
# 시간이 빠른 순서대로 정렬
plans.sort(key=lambda x : -x[1])
# 진행해야될 과제가 있을때까지
current = None
start = 0
end = 0
wait = []
# 일단 처음부터 가져오지 않고 정렬되어 있는것부터 가져오면 되는거지
while plans:
p = plans[-1]
# 현재 진행중인 과제가 없으면 진행한다.
if current is None:
plans.pop()
current = p
start = current[1]
end = start + p[2]
continue
if p[1] < end:
plans.pop()
com = abs(start - p[1])
current[2] -= com
wait.append(current)
current = p
start = p[1]
end = start + p[2]
continue
else:
answer.append(current[0])
if p[1] == end:
if wait:
plans.pop()
current = p
start = p[1]
end = start + p[2]
continue
# 대기 목록이 없으면 현재과제를 진행하면된다.
else:
plans.pop()
current = p
start = p[1]
end = start + p[2]
continue
else:
current = wait.pop()
start = end
end = start + current[2]
continue
if current is not None:
wait.append(current)
for idx in range(len(wait)-1, -1, -1):
answer.append(wait[idx][0])
return answer
정답코드
# 100점
def solution(plans):
answer = []
for idx, value in enumerate(plans):
h = int(value[1].split(":")[0])
m = int(value[1].split(":")[1])
plans[idx][1] = (h * 60) + m
plans[idx][2] = int(value[2])
# 시간이 빠른 순서대로 정렬
plans.sort(key=lambda x : -x[1])
# 진행해야될 과제가 있을때까지
current = None
start = 0
end = 0
wait = []
# 일단 처음부터 가져오지 않고 정렬되어 있는것부터 가져오면 되는거지
while plans:
p = plans[-1]
# 현재 진행중인 과제가 없으면 진행한다.
if current is None:
plans.pop()
current = p
start = current[1]
end = start + p[2]
continue
# 현재 진행중인 과제가 있다면
# 진행중인 과제를 가지고 왔을때 현재 진행중인 과제가 끝나는 시간 안에 있어 새로운 과제를 진행해야 될때
if p[1] < end:
plans.pop()
com = abs(start - p[1])
current[2] -= com
wait.append(current)
current = p
start = p[1]
end = start + p[2]
continue
else:
answer.append(current[0])
if p[1] == end:
if wait:
current = plans.pop()
start = current[1]
end = start + current[2]
continue
else:
current = plans.pop()
start = current[1]
end = start + current[2]
continue
else:
# 만약에 과제를 끝냈을때 잠시 멈춘 과제가 있다면 멈춰둔 과제를 이어서 진행한다.
if wait:
current = wait.pop()
start = end
end = start + current[2]
continue
# 만약에 과제를 끝냈을때 잠시 멈춘 과제가 없다면 현재 과제로 진행한다.
else:
current = plans.pop()
start = current[1]
end = start + current[2]
continue
if current is not None:
wait.append(current)
for idx in range(len(wait)-1, -1, -1):
answer.append(wait[idx][0])
return answer
설명
이번 문제는 문제에서 주어진 '구현' 조건만 정확하게 구현하면 되는 단순 구현 문제라고 보인다. 하지만 저 단순 구현문제가 해석을 조금이라도 잘못하게 된다면 전혀 다른 방향으로 구현이 돼버린다. 따라서 첫 번째 틀린 코드부터 정답 코드까지 어떤 부분에서 달랐고 어떠한 논리가 허점이 있었는지 간략하게 설명해보려고 한다. 위에 코드들은 대부분 중복된 코드가 많기 때문에 사실 좋은 코드라고 볼 수는 없다. 더 효율적인 코드가 있을 수 있기 때문에 논리의 흐름 정도로 보면 좋을 것 같다.
첫 번째 코드와 두 번째 코드는 가장 중요한 구현논리인 아래 조건에 위배된다.
- 진행 중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
- 만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
읽었을 때 어떻게 생각이 들었는지 한번 적어보는 것도 좋은 것 같다. 우선 첫 번째 코드와 두 번째 코드는 저 두 조건을 만족하지 못한다. 왜냐하면 진행 중이던 과제를 끝냈을 때 그리고 만약 과제를 끝낸 시각일 때 이렇게 둘로 나눠서 생각해야 되는데 첫 번째와 두 번째 코드는 섞이거나 논리적으로 꼬인 문장으로 작성되었다. 따라서 문장의 구분을 정확히 이해하지 못한 상태로 가볍게 이해하고 넘어갔기 때문에 논리적인 허점이 많이 드러나는 코드를 작성한게 첫 번째와 두 번째 코드라고 볼 수 있다. 그럼 이제 이렇게 둘로 나눠서 생각했을 때 '과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면' 이 부분을 잘 살펴야 한다. 진행 중이던 과제를 끝냈을 때와 과제를 끝낸 시각에 둘의 차이가 무엇일까. 처음에 이 둘을 한 번에 구현하려다가 계속 논리가 꼬여서 부분점수만 받게 되었는데 가장 큰 차이점은 진행 중이던 과제가 끝났다라는 건 결국 아래 두 가지다.
1. 다음 진행할 과제의 시작시간이 현재 진행 중인 과제의 끝시간과 같을 때
2. 다음 진행할 과제의 시작시간이 현재 진행 중인 과제의 끝시간 보다 클 때
(이미 진행하고 있는 과제가 끝났을 때 다음 과제를 바로 실행하지 않는다.)
위 문장을 다시 한번 쉽게 풀어써보자 과제가 끝나는 시간은 시작 시간 + playtime 즉 과제 진행시간이다. 그랬을 때 한 타임라인이라고 생각해 본다면 다음 과제를 수행해야 할 때 기존에 진행 중인 과제의 시간대 즉 기존에 과제가 끝나는 시간 전에 다음 과제를 수행해야 될 때 기존의 과제는 대기하고 새로운 과제를 수행해야 된다고 한다. 그렇다면 위 1번 조건을 살펴보자 현재 진행 중인 과제의 끝시간과 같다는 건 기존 과제가 끝이 났을 때 새로운 과제가 시작된다는 뜻이기도 하며 조건에서 새로운 과제가 끝나고 새로운 과제의 시작시간이 같을 경우 기존 과제는 마친 걸로 한다는 조건에도 만족해야 한다. 결국 아래와 같이 정리할 수 있다.
1번 조건에서는 과제의 끝시간이 같을 때 새로 시작해야 되는 과제와 멈춰둔 과제 모두 있다면 새로 시작하는 과제로 진행해주고 과제의 끝시간이 같을때 새로 시작해야 되는 과제는 있지만 멈춰둔 과제는 없다면 새로 시작하는 과제로 진행해 준다.
2번 조건 같은 경우에는 1번과 많이 헷갈릴 수 있다. 현재 진행 중인 과제의 끝시간보다 크다는 것은 곧 기존에 진행하고 있었던 과제가 끝나고 나서 바로 실행하지 않는다는 것을 의미하며 결국 남는 시간이 존재한다는 것이기도 하다. 그렇다면 그 남는 시간자체는 문제에서는 기존에 멈춘 최신과제를 진행하라고 했기 때문에 둘로 나눠서 생각해 보면 간단하다. 대기하고 있는 과제가 있을 때 또는 대기하고 있는 과제가 없을 때 그럼 이건 곧 예제 1번 케이스가 통과되는 경우라고 볼 수 있다. 결국 이 문제에서의 핵심은 저 문장을 어떤 방식으로 해석했는지에 따라 생각이 많이 달라질 수 있을 것 같다는 생각을 하기도 했다. 논리적인 모순이 정말 잘 드러나는 문제기도 했으며 문제의 구현을 위해서 무작정 먼저 리스트에서 뽑지 않고 체크한다는 접근 방식으로 접근해 본다는 새로운 방식도 적용해 본 문제기도 했다. 정답코드와 가장 큰 차이점이라면 해당 구현 방법과 그리고 1,2번 조건을 나눠서 정확하게 구현하는 것이 가장 큰 차이점이라고 생각한다.
'알고리즘' 카테고리의 다른 글
| [백준] 3190 뱀 [풀이해설 + 코드 + 놓쳤던 점들] (0) | 2023.07.28 |
|---|---|
| [백준] 1753 최단경로 [다익스트라와 BFS차이를 한번 생각해보자 + 코드 없음] (0) | 2023.07.25 |
| [프로그래머스] Lv.2 미로탈출 [논리적 허점 + 코드 + 해설] (0) | 2023.07.18 |
| [백준] 토마토 [찾지 못한 부분 + 코드 + 해설] (0) | 2023.07.16 |
| [프로그래머스] Lv.2 리코쳇 로봇 [풀지 못했던 이유 + 코드 + BFS가 왜 최단 경로를 보장할까] (1) | 2023.07.14 |