[Python] 백준 2164번 문제 풀이 - 카드2

문제

https://www.acmicpc.net/problem/2164

아이디어

이 문제는 숫자 N이 주어지면 밑에서부터 N, N-1, N-2 처럼 피라미드 형식으로 숫자가 쌓입니다.

이 문제는 두 단계로 이루어지는데

 

첫번째 단계, 카드 더미 맨 위에서 한장을 버리는 것.

두번째 단계, 카드 더미 맨 위에서 한장을 뽑아 가장 아래에 넣는 것.

입니다.

 

양쪽에서 데이터를 추가하고 삭제해야 하기 때문에 일반 Queue가 아닌 Double Ended Queue를 써야겠다고 생각했습니다. 

 

그래서 큰 숫자부터 순서대로 넣은 다음에 첫번째 단계와 두번째 단계를 수행하고 덱에 요소가 하나만 있다면 출력하는 코드를 작성하였습니다.

첫번째 소스코드

from collections import deque

q = deque()

n = int(input())
for i in range(n):
    q.append(n-i)

while q:
    q.pop()

    if len(q) == 1:
        print(q.pop())
        break
    ele = q.pop()
    q.appendleft(ele)

이렇게 소스코드를 작성했더니 런타임 에러(IndexError)가 나왔습니다.

이유를 생각해보니 n이 1일 경우에는 while문 안의 첫번째 줄인 q.pop()에서 q의 요소가 다 빠져버리고 다음 ele = q.pop()을 만났을 때 q에 아무것도 없기 때문에 뺄 수 있는 요소가 없어 에러가 나는 것이였습니다. 그래서 소스코드를 수정하였습니다.

두번째 소스코드

from collections import deque

def solution(n):
    if n == 1:
        return 1
    q = deque()

    for i in range(n):
        q.append(n-i)

    while q:
        q.pop()

        if len(q) == 1:
            return q.pop()
        x = q.pop()
        q.appendleft(x)

n = int(input())
print(solution(n))

 

 

solution 함수 속에 넣어 n이 1이라면 바로 1을 리턴하게 만들어서 제출 하였습니다.

 

근데 이 글을 쓰면서 생각해보니 굳이 deque가 아닌 queue로도 가능 하다는 생각이 들었습니다.

deque를 써야 한다고 생각한 이유를 찾아보니 카드가 쌓여있는 모습을 처음에 스택으로 생각했기 때문에 밑에 카드를 넣으려면 양방향에서 넣어야 한다고 생각했습니다.

 

그래서 queue로 다시 구현해보았습니다.

세번째 소스코드

from queue import Queue

def solution(n):
    if n == 1:
        return 1
    q = Queue()

    for i in range(1, n+1):
        q.put(i)

    while q:
        q.get()

        if q.qsize() == 1:
            return q.get()
        x = q.get()
        q.put(x)

n = int(input())
print(solution(n))

두번째와 로직은 동일하고 자료구조만 변경되었습니다.

 

느낀 점

deque나 Queue가 라이브러로 제공이 되어 편하게 사용했지만

코딩테스트에서 라이브러리 사용을 금지하게 되면 당황해서 문제를 제대로 풀지 못할 것 같아

라이브러리가 어떻게 구현되어 있는지 파악하고 간략하게 구현을 해보는 과정을 거쳐야겠다고 생각했습니다.