묘공단 (코딩 테스트 합격자 되기 파이썬편)

큐?

큐(queue)는 ‘줄을 서다’라는 뜻을 갖고있다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조이며, 즉 선입선출 또는 FIFO라고 한다. 스택과 마찬가지로 삽입하는 연산을 푸시, 꺼내는 연산을 팝이라고 합니다.

 

큐에서 데이터가 이동하는 과정

1. 빈 큐를 하나 선언한다.

   

2. 원소를 삽입한다. 빈 큐이므로 제일 앞에 삽입한다. 이어서 5를 삽입한다. 5는 2 다음으로 삽입했으니 2보다 뒤에 있다.

   

3. 팝을 하면 5가 아닌 2가 먼저 나온다. 이어서 팝을 한 번 더 진행하면 5가 빠져나온다.

   

 

 

 

 

큐의 특성을 활용하는 두가지 방법 

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에서 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다. 이러할 때 큐를 활용가능.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스의 움직임을 처리할 때 큐를 활용 가능.

 

큐 구현하기

큐를 구현하는 방식에는 리스트를 활용하는 방식과 덱을 활용하는 방식 두가지가 있다.

1. 리스트를 큐처럼 활용하기
   푸시 연산은 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)