코드숨 알고리즘 day1 큐
코드숨 알고리즘 for 코딩 테스트 - DAY1 : QUEUE
카드2
문제에서 하라는대로 list를 사용해서 구현했으나 시간초과 파이썬 collections에 내장된 deque로 바꿔주니 시간이 통과되었다.
def solution(N):
card = deque([n for n in range(1, N + 1)])
while len(card) > 1:
card.popleft()
move_card = card.popleft()
card.append(move_card)
return card[0]
다른 아이디어가 없을까 생각했는데 짝수만 남을때까지 홀수가 다 사라져서 처음 큐를 만들때 짝수만 만들도록 바꿨다. 시간이 아주 조금 단축되었다. 시간복잡도는 동일하고 자료 양만 줄었기 때문이다.
from collections import deque
def solution(N):
if N == 1:
return 1
card = deque([n for n in range(2, N + 1, 2)])
if len(card) and N % 2 != 0:
num = card.popleft()
card.append(num)
while len(card) > 1:
card.popleft()
move_card = card.popleft()
card.append(move_card)
return card[0]
다른 사람들이 푼 것을 보니 다른 규칙성도 있었는데 왜 그런 규칙이 도출되었는지 솔직히 잘 이해가 안가서 자료구조 큐를 사용한 것에 의의를 두기로 했다.
요세푸스 문제
이 문제도 마찬가지로 문제에서 말하는 규칙대로 그대로 구현을 했다. 맨 위에 K번째 사람이 올 때까지 사람을 뒤로 넣어주고 K번째 사람이 오면 결과 리스트에 담아주도록 구현을 했다. 그 결과 자료를 빼고 삽입하고 매 라운드마다 K번의 일을 반복해야하기 때문에 효율성이 떨어졌다. 시간복잡도가 Big-O(N*K) 인거 같다.
def solution(N, K):
q = [n for n in range(1, N + 1)]
result = []
index = 0
for i in range(N):
index += K - 1
# if index >= len(q):
index %= len(q)
result.append(str(q.pop(index)))
print('<' + ','.join(list(map(str, result))) + '>')
return result
다음 아이디어로는 자료를 직접 넣고 빼지말고 인덱스를 움직이기로 했다. 이렇게 되면 매 라운드 해당 인덱스만 보면 되기 때문에 시간복잡도가 Big-O(N)이 되서 더 효율적이다.
from collections import deque
def solution(N, K):
q = deque([n for n in range(1, N + 1)])
result = []
while q:
for _ in range(K - 1):
num = q.popleft()
q.append(num)
result.append(q.popleft())
print('<' + ', '.join(list(map(str, result))) + '>')
return result
프린터 큐
큐에 순서와 중요도를 튜플로 담는다. 현재 순서를 0(제일 앞)으로 바라보고 큐 가장 위 자료부터 살핀다. 현재 가리키고 있는 문서의 중요도보다 중요도가 높은 문서가 있으면 현재 문서를 큐에 넣었다. 현재 문서보다 중요도가 높은 문서가 없다면 위치를 1 더한다. 만약 해당 자료의 인덱스와 순서가 궁금한 자료의 인덱스가 같다면 즉, 내가 궁금한 자료라면 출력하고 리턴.
n, m = map(int, input().split())
priorities = list(map(int, input().split()))
queue = [(i, p) for i, p in enumerate(priorities)]
answer = 0
print(queue)
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == m:
print(answer)
break
후기
프로그래머스에 익숙하고 백준에서 처음 문제를 풀다보니 함수를 만들고 결과를 return하는 형식이 아니어서 그런 부분에 시간을 많이 뺐겼다. 문제가 틀리는 대부분의 이유가 print 찍을 때 띄어쓰기같은 것들이나 input이 어떻게 들어오는지 이해가 좀 안되었다. 특히 마지막 문제에 입력값이 이해가 안되서 해맷다.
알고리즘 실력이 안풀다보니 금새 다시 줄어들었다. 다시 열심히 해야지