일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 문자열
- SWEA
- 깊이우선탐색
- 자바스크립트
- 백준 알고리즘
- 브루트포스 알고리즘
- 백준알고리즘
- 그래프 이론
- 너비 우선 탐색
- 완전탐색
- SW Expert Academy
- BFS
- oracle
- 파이썬
- 오라클
- 다익스트라
- 다이나믹 프로그래밍
- Python
- 브루트포스
- 너비우선탐색
- 구현
- javascript
- 데이터베이스
- 프로그래머스
- DFS
- 그리디 알고리즘
- 스택
- 백트래킹
- DP
- 그래프 탐색
- Today
- Total
민규의 흔적
[Python 파이썬] 프로그래머스 - 과제 진행하기 본문
2024년 9월 24일
문제 링크 : 프로그래머스 - 과제 진행하기
문제 접근
주어진 데이터를 자신이 원하는 목적에 맞게 가공하여 활용할 수 있는지가 문제의 난이도를 좌우한다고 생각한다.
구현 문제는 문제에서 요구하는 바를 정확히 이해해야 한다.
1. plans의 요소들은 진행할 과제들에 대한 정보를 담고 있으며, 이는 [과제명, 과제 시작시간, 소요시간]으로 이루어져 있다.
2. 과제는 시작하기로 한 시각이 되면 시작한다.
3. 새로운 과제를 시작할 시간이 되었을 때, 기존에 진행하고 있던 과제가 있다면 해당 진행을 멈추고 새로운 과제를 시작한다.
4. 진행 중이던 과제를 끝냈을 때, 멈춰두었던 과제가 존재한다면 해당 과제를 이어서 진행한다. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작한다.
5. 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행해야 한다.
위 요구사항들을 토대로 수행해야 하는 작업들은 다음과 같다.
1. plans의 각 요소들을 과제 시작시간(start)를 기준으로 오름차순 정렬
start가 빠른 순서부터 과제를 수행하며, 시간이 흐름에 따라 모든 과정이 이루어지기 때문이다.
plans.sort(key=lambda x:x[1])
2. 데이터 가공
과제 시작시간(start)은 문자열 형태로 존재하며, "hh:mm"로 주어지기에 계산에 용이하게 하려면 통일해주는 작업이 필요하다.
나는 분 단위로 통일해 정수형으로 바꿔주는 작업으로 데이터 가공을 진행했다.
또한, 과제를 수행하는데 걸리는 시간(playtime)은 과제를 끝내기까지 남은 시간으로 취급하기로 의미를 살짝 변경하였다.
# 데이터 가공 -> 시작 시간을 분 단위로 통일, playtime은 과제를 끝내기까지 남은 시간으로 취급
start_hour, start_min = map(int, plans[idx][1].split(":"))
plans[idx][1] = 60 * start_hour + start_min
plans[idx][2] = int(plans[idx][2])
3. 시간의 흐름에 따라 요구사항에 맞게 과제 수행
말 그대로다. 요구사항을 잘 지키며 구현을 진행해주면 된다.
현재 어떤 과제를 진행하고 있을 때, 나는 3가지 상황을 겪게 될 수 있다.
1. 다음에 진행할 과제 시작 시간 전에 현재 수행 중인 과제를 끝낼 수 있을 때
만약 12:40에 현재 과제를 끝내고 다음 수행해야 할 과제는 12:50분에 시작한다면, 남은 10분을 활용할 수 있을 것이다.
무슨 의미냐면 중간에 멈춘 과제가 존재한다면 10분을 멈춘 과제에 활용할 수 있다는 의미이다.
물론 중간에 멈춘 과제가 없을 때에는 아무런 작업이 필요 없다.
2. 다음에 진행할 과제 시작 시간 전에 현재 수행 중인 과제를 끝낼 수 없을 때
만약 13:00에 시작해 60분 걸려야 끝낼 수 있는 과제를 시작했는데 13:30에 다음 과제를 시작해야 한다면, 과제를 끝내는데 필요한 시간인 60분에서 과제 수행에 사용한 30분은 차감한 이후, 30분이 남았음을 멈춘 과제들 리스트에 저장해 두어야 한다.
3. 지금 진행하는 과제가 마지막으로 새로 시작한 과제일 때 (plans의 마지막 요소)
이 과제는 끊김 없이 한 번에 진행할 수 있는 과제이다. 이 또한 고려해 주어야 한다.
이제 멈춘 과제들을 수행해야 한다.
3가지 상황을 고려해 plans의 모든 과제를 한 번씩 새로 시작했다면, 이제 멈춘 과제들을 우선순위에 맞게 해결해주어야 한다.
멈춘 과제들의 우선순위는 가장 최근에 멈춘 과제가 우선순위를 가지므로 멈춘 과제들 리스트의 마지막 요소들을 순서대로 pop 해주며 수행하면 된다.
위 고려사항들을 모두 충족해 코드를 작성하면 아래의 전체 코드가 된다!
전체 코드
def solution(plans):
complete = []
# 과제를 진행하다 끝내지 못한 과제들의 정보를 담아낼 2차원 배열
# [idx][0] = 과제 이름
# [idx][1] = 해당 과제를 끝내는데 남은 시간
not_complete = []
plans.sort(key=lambda x:x[1])
# 데이터 가공 -> 시작 시간을 분 단위로 통일, playtime은 과제를 끝내기까지 남은 시간으로 취급
start_hour, start_min = map(int, plans[0][1].split(":"))
plans[0][1] = 60 * start_hour + start_min
plans[0][2] = int(plans[0][2])
for idx in range(1, len(plans)):
start_hour, start_min = map(int, plans[idx][1].split(":"))
plans[idx][1] = 60 * start_hour + start_min
plans[idx][2] = int(plans[idx][2])
left_time = 0
# 과제를 시작했을 때, 다음 순번의 과제를 시작하기 전까지 끝낼 수 있는 경우
if plans[idx - 1][1] + plans[idx - 1][2] <= plans[idx][1]:
complete.append(plans[idx - 1][0])
# 이전 과제를 끝내고 다음 과제를 시작하는 사이의 남는 시간을 left_time에 저장
left_time += plans[idx][1] - (plans[idx - 1][1] + plans[idx - 1][2])
# 여유 시간이 존재하면 반복문 수행
while left_time > 0:
if not not_complete:
break
# 여유 시간동안 재시작할 과제를 다 끝내지 못한 경우
if not_complete[-1][1] > left_time:
not_complete[-1][1] -= left_time
break
# 여유 시간동안 재시작할 과제를 다 끝낼 수 있는 경우
else:
# 남은 여유 시간에서 재시작했던 과제를 수행한 시간 만큼 차감하여 다른 과제를 재시작
left_time -= not_complete[-1][1]
complete.append(not_complete.pop()[0])
# 과제를 시작했을 때, 다음 순번의 과제를 시작하기 전까지 못 끝내게 되는 경우
else:
not_complete.append([plans[idx - 1][0], plans[idx - 1][2] - (plans[idx][1] - plans[idx - 1][1])])
# plans의 마지막에 있는 과제는 시작하면 끝까지 진행하게 됨
complete.append(plans[-1][0])
# 아직 못 끝낸 과제들 중에선, 최근에 끝낸 과제부터 재시작해야함
while not_complete:
complete.append(not_complete.pop()[0])
return complete
if __name__ == "__main__":
plans = [["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]]
print(solution(plans))
풀이 후기
내 경험상 기업 코딩테스트의 구현 문제들은 이런 느낌의 데이터 가공이 필수적인 요소로 포함되어 있었다.
이런 문제가 실제 기업 코테를 준비하는 데에 많은 도움이 되리라 생각한다.
'프로그래머스' 카테고리의 다른 글
[Python 파이썬] 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (2) | 2024.09.24 |
---|---|
[Python 파이썬] 프로그래머스 - 땅따먹기 (1) | 2024.09.10 |
[Python 파이썬] 프로그래머스 - 귤 고르기 (0) | 2024.08.06 |
[Python 파이썬] 프로그래머스 - 네트워크 (0) | 2024.08.06 |
[Python 파이썬] 프로그래머스 - 베스트앨범 (0) | 2024.07.17 |