문제
프로그래머스 - 구명보트
🧮 문제 링크입니다! 🧮
문제 풀이
추상화한 알고리즘 시나리오입니다.
각 단계마다 다른 전략을 선택할 수 있습니다!
1) priorities 배열을 비교하기 좋게 정제한다.
2) priorities 배열의 max값을 찾아서 현재 배열의 첫번째 원소이면 pop하고 실행 횟수인 cnt값을 하나 증가시킨다.
3) max값이 첫번째 원소가 아니면 첫번째 원소를 pop하고 배열 마지막에 다시 append한다.
4) 만약 2단계에서 pop한 원소가 location의 원소라면 cnt를 리턴한다.
location을 어떻게 처리해야 priorities 배열에서의 위치를 따라갈 수 있을까 고민하다가 Trace용 Queue를 하나 더 생성하는 방법으로 풀어보았습니다.
매번 두 개의 queue를 함께 연산해야하기 때문에 코드를 작성하면서도 이것 좀 별로다..라고 느꼈습니다.
정답 처리가 되기는 했지만 시간, 공간 복잡도가 너무 컸습니다.
그래서 언제나 그렇듯 다른 분들의 답안을 구경하러 다녔습니다.
그렇게 찾은 새로운 방법은 바로 Priority Queue를 생성하는 것입니다.
기존의 priorities는 그대로 두고, 우선순위를 내림차순으로 정리한 search라는 큐를 하나 더 만들어서 max를 비교합니다.
queue에 대한 반복적인 연산이 아예 없기 때문에 매우 빠르다고 느꼈습니다.
그런데 좀 새로웠던 부분은 for-else 구문을 활용한 것입니다.
while True:
for i, priority in enumerate(priorities):
cur = search[s]
if priority == cur:
s += 1
cnt += 1
if i == location:
break
else: # for문을 다 돌았을 경우 다시 while문으로 간다.
continue
break # for문에서 break한 경우 while문도 break 한다.
return cnt위의 소스 코드는 priorities 배열을 순회하면서 search 배열의 최댓값과 매칭하는 부분입니다.
if i == location: 일 경우 for문과 while문을 다 빠져나와서 return cnt 가 실행되어야 합니다.
if i == location: 아래의 break 가 실행되면 for문 아래의 else 부분이 실행되지 않습니다.
그렇기 때문에 else 아래에 break 를 하나 더 추가하여 while문까지 빠져나올 수 있도록 하였습니다.
이미 작성된 코드를 분석하는 입장에서는 GOOD.이라고 간단히 말하고 끝낼 수도 있겠지만, 실전에서 코드를 짜야하는 상황이 닥쳐도 당황하지 않고 차분히 모든 분기를 생각할 수 있도록 머리에 잘 새겨야겠습니다.
저는 여기에서도 만족하지 못하고 정답을 조금 더 살펴보았습니다.
any 함수를 사용한 아주 짧은 코드가 눈에 들어왔습니다.
저는 any 함수를 처음 봤습니다. 근데 아주 유용한 함수더군요.
🧏 any()와 all()
argument로 iterable한 객체를 받고, 이 객체를 순회하며 조건을 검사한 뒤 True/False를 리턴한다.any() : 하나라도 True면 True 리턴
all() : 모든 element가 True여야 True 리턴
위에서 한 것처럼 정렬한 priority queue를 생성하지 않고도 원소의 대소 비교를 할 수 있다는 게 any 함수의 장점인 것 같습니다.
이렇게 마지막 방법에서는 priorities 배열을 enumerate한 queue를 만들고, 하나씩 순회하며 any 함수로 max 여부를 확인합니다.
코드가 짧아서 가독성도 좋고 멋도 있지만 queue 연산이 있기 때문에 두번째 방법보다는 속도가 느린 것 같습니다.
소스 코드
3가지 방법을 전부 작성해두었습니다! 하나만 고르셔야합니다!
Method 1: Trace용 Queue 생성
Method 2: Priority Queue 생성
Method 3: any 함수 사용
from collections import deque
def solution(priorities, location):
# Method 1: Trace용 Queue 생성
queue = deque(priorities)
trace = deque([0 for _ in range(len(priorities))])
trace[location] = 1
cnt = 0
while queue:
if max(trace) == 0:
break
if max(queue) == queue[0]:
queue.popleft()
trace.popleft()
cnt += 1
else:
queue.append(queue.popleft())
trace.append(trace.popleft())
return cnt
# Method 2: Priority Queue 생성
cnt = 0
search, s = sorted(priorities, reverse=True), 0
while True:
for i, priority in enumerate(priorities):
cur = search[s]
if priority == cur:
s += 1
cnt += 1
if i == location:
break
else: # for문을 다 돌았을 경우 다시 while문으로 간다.
continue
break # for문에서 break한 경우 while문도 break 한다.
return cnt
# Method 3: any 함수 사용
queue = deque([(i, p) for i, p in enumerate(priorities)])
cnt = 0
while queue:
cur = queue.popleft()
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
cnt += 1
if cur[0] == location:
return cnt