묘공단 (코딩 테스트 합격자 되기 파이썬편)
큐?
큐(queue)는 ‘줄을 서다’라는 뜻을 갖고있다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조이며, 즉 선입선출 또는 FIFO라고 한다. 스택과 마찬가지로 삽입하는 연산을 푸시, 꺼내는 연산을 팝이라고 합니다.
큐에서 데이터가 이동하는 과정
- 빈 큐를 하나 선언한다.
- 원소를 삽입한다. 빈 큐이므로 제일 앞에 삽입한다. 이어서 5를 삽입한다. 5는 2 다음으로 삽입했으니 2보다 뒤에 있다.
- 팝을 하면 5가 아닌 2가 먼저 나온다. 이어서 팝을 한 번 더 진행하면 5가 빠져나온다.
큐의 특성을 활용하는 두가지 방법
- 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에서 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다. 이러할 때 큐를 활용가능.
- 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스의 움직임을 처리할 때 큐를 활용 가능.
큐 구현하기
큐를 구현하는 방식에는 리스트를 활용하는 방식과 덱을 활용하는 방식 두가지가 있다.
- 리스트를 큐처럼 활용하기
푸시 연산은 append() 메서드를 활용, 팝 연산은 pop() 메서드를 활용한다.
queue = [ ]
# 푸시 연산
queue.append(1)
queue.append(2)
queue.append(3)
# 팝 연산
first_item = queue.pop(0)
print(first_item)
2.덱을 큐처럼 활용하기
덱(Double Ended Queue)은 양 끝에서 삽입이나 삭제할 수 있는 큐를 구현한 것이다. 이러한 양쪽에서 삽입이나 삭제를 할 수 있다는 특징 때문에 큐를 구현할 때는 덱을 사용하는게 좋다.
from collections import deque
queue = deque( )
# 푸시 연산
queue.append(1)
queue.append(2)
queue.append(3)
# 팝 연산
first_item = queue.popleft( )
print(first_item)
몸풀기
15. 요세푸스 문제
N명의 사람이 원 형태로 서있다. 각 사람은 1부터 N까지 번호표를 갖고 있다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앤다. N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution()함수를 구현해라.
제약조건
- N과 K는 1이상 1,000 이하의 자연수이다.N K return
N K return 5 2 3
from collections import deque
def solution(N, k):
queue = deque(range(1, N+1))
while len(queue) > 1:
for i in range(k-1):
queue.append(queue.popleft())
queue.popleft()
print(queue[0])
N = 5
k = 2
solution(N, k)
16. 기능 개발
프로그래머스팀에서는 기능 개선 작업을 수행 중이다. 각 기능은 진도가 100%일 때 서비스를 반영할 수 있다. 각 기능의 개발 속도는 모두 다르므로 뒤의 기능이 앞의 기능보다 먼저 개발될 수 있다. 이때 뒤의 기능은 앞의 기능이 배포 될때 같이 배포되어야한다. 배포 순서대로 작업 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 반환하도록 solution()함수를 완성해라
제약조건
- progresses와 speeds의 배열의 길이는 100 이하이다.
- 작업 진도는 100 미만의 자연수이다.
- 작업 속도는 100이하의 자연수이다.
- 배포는 하루에 한 번만 가능하며, 하루의 끝에 이루어진다고 가정한다. 진도율이 95%인 작업의 개발속도가 하루에 4%라면 배포는 2일뒤이다.
| progresses | speeds | return |
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
from collections import deque
def solution(progresses, speeds):
queue = deque(progresses)
speed_queue = deque(speeds)
run = False
result_item = 0
result = []
while len(queue) > 0:
for i in range(len(queue)):
queue.append(queue.popleft() + speed_queue[0])
speed_queue.append(speed_queue.popleft())
if queue[0] >= 100:
while queue and queue[0] >= 100:
queue.popleft()
result_item += 1
if result_item > 0:
result.append(result_item)
result_item = 0
print(result)
progresses = [95, 90, 99, 99, 80, 99]
speeds = [1, 1, 1, 1, 1, 1]
solution(progresses, speeds)
17. 카드 뭉치
다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고싶다.
- 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용한다.
- 한 번 사용한 카드는 다시 사용할 수 없다.
- 카드를 사용하지 않고 다음 카드로 넘어갈 수 없다.
- 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없다.
문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때 cards1과 cards2에 적힌 단어들로 goal을 만들 수 있다면 “Yes”, 만들 수 없다면 “No”를 반환하는 solution() 함수를 완성해라.
제약조건
- cards1과 cards2의 길이는 1이상 10이하이다.
- goal의 길이는 2이상 cards1+cards2 이하이다.
- 문자열들은 모두 알파벳 소문자로만 이루어져 있다.
| cards1 | cards2 | goal | result |
| ["i", "drink", "water"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | “Yes” |
| ["i", "water", "drink"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | “No” |
from collections import deque
def solution(cards1, cards2, goal):
queue = deque()
cards1_queue = deque(cards1)
cards2_queue = deque(cards2)
goal_queue = deque(goal)
result = ""
for i in range(len(goal)):
if len(cards1_queue) > 0:
word1 = cards1_queue.popleft()
if len(cards2_queue) > 0:
word2 = cards2_queue.popleft()
if len(goal_queue) > 0:
word3 = goal_queue.popleft()
if word3 == word1:
queue.append(word1)
goal_queue.append(word3)
cards2_queue.appendleft(word2)
elif word3 == word2:
queue.append(word2)
goal_queue.append(word3)
cards1_queue.append(word1)
elif word3 != word1 and word3 != word2:
result = "No"
if result != "No":
result = "Yes"
print(result)
cards1 = ["i", "water", "drink"]
#cards1 = ["i", "drink", "water"]
cards2 = ["want", "to"]
goal = ["i", "want", "to", "drink", "water"]
solution(cards1, cards2, goal)