[Baekjoon] 백준 2164번 카드2

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

 

 

입출력 예시

 

 

생각과정

문제를 생각해보면 가장 먼저 고려해야하는 부분은 카드가 위에서부터 순서대로 놓이고, 맨 위에서부터 카드를 뽑는 큐의 구조라는 점이다.

그럼 입력을 받아서 for문으로 하나씩 돌릴 때, 역순으로 리스트를 만들어줘야 한다. 

 

그리고나서 문제의 내용을 하나하나 구현하면 될 거라고 생각했는데... 접근 방식이 틀려서 결국 구현을 하지 못했다.

내가 짠 코드부터 보자.

 

풀이

내 풀이

N = int(input())
queue = []

for i in range(N, 0, -1):
    queue.append(i)

for i in range(len(queue)):
    if len(queue) == 1:
        break

    queue.pop()

    while len(queue) > 1:
        temp = queue.pop()

        # 잘못짠 코드 - 이미 pop해버린 temp를 다시 queue의 맨 앞에 넣어보려고 했으나 실패했다. 그냥 reverse했다가 append하고 다시 reverse하는 방식도 생각해봐야겠다.
        if i + 1 < len(queue):
            last = queue[i+1]
            queue[i+1] = queue[i]
            queue[i] = last
            i += 1

    queue[0] = temp

 

내 생각은 while문을 탔을 때, 맨 위의 요소를 하나씩 꺼낸 후, 꺼낸 요소를 맨 앞으로 보내주고자 했다. 생각대로 코드를 짜려고 했지만 실수를 한 부분이 일단 pop을 하면 리스트의 크기가 줄어들어서 다시 append를 하는게 아니라면 맨 앞에 넣어 줄 수 없는 코드를 짜버린 거였다. 처음에 몇가지 입력값을 넣으면 제대로 답이 나오길래 드디어 문제를 하나 해결했나 하는 마음이 있었는데 음....

 

어쨌든, 다른 풀이를 보고 해결해보자!

 

 

다른 풀이

def test_problem_queue(num):
    # 리스트 컴프리헨션 - 한 줄로 리스트를 만드는 방식.
    # 풀어쓰면 다음과 같다
    # list = []
    # for i in range(1, num + 1):
    #   list.append(i)
    deq = deque([i for i in range(1, num + 1)]) # ex) [1, 2, 3, 4]
    while len(deq) > 1:
        deq.popleft() # 맨 첫번째 (왼쪽) 요소 꺼내기 - 위에서 부터 1234의 순서로 놓여있다고 했으므로 제일 왼쪽 요소가 제일 위쪽에 있다고 본다.
        deq.append(deq.popleft())
    return deq.popleft()

큐의 데크(deque)를 이용한 방식이다.

데크는 양쪽 끝에서 요소를 빠르게 추가 / 삭제할 수 있는 리스트류 컨테이너로, 큐와 단짝이라고 해도 좋을만큼 문제를 풀 때 사용하면 유용한 객체이다.

 

기존 큐와 다른 점은 popleft() 함수의 존재인데, 보통 pop() 함수는 마지막 인덱스의 요소를 꺼내오는 반면 popleft() 함수는 처음 인덱스의 요소를 꺼내올 수 있다.

+

a.pop(0) 형태로 사용하면 pop() 함수를 가지고도 첫 인덱스의 요소를 꺼내올 수 있다고 한다!

 

popleft()가 무엇인 지 알았다면 코드는 어렵지 않게 볼 수 있는데, 추가적인 개념을 짚고가자.

바로 리스트 컴프리헨션인데, 

deq = deque([i for i in range(1, num + 1)])

이런 식으로 리스트를 생성할 때 사용하는 파이썬을 대표하는 특징 중 하나이다.

물론 지나치게 남발하면 오히려 가독성을 떨어뜨리지만 잘 사용하면 복잡도를 줄일 수 있는 좋은 방법이다. 

 

그럼 리스트 컴프리헨션을 보기 좋게 풀어서 써보자!

list = []
for i in range(1, num + 1):
	list.append(i)

리스트 컴프리헨션으로 줄인 것과 비교해보자. 훨씬 보기 쉽다.

가운데에 for문을 넣고, list.append(i)부분에서 i만 꺼내서 for 옆에 써준다. 마지막으로 list=[] 대신 꺽쇠를 양 끝에 붙여주면 완성이다.

 

사실 리스트 컴프리헨션을 써서 헷갈리는 것보단 지금은 일일히 써가면서 흐름을 익히는게 중요하다고 생각하기 때문에, 이 부분은 알고는 있되, 나중에 능력치가 향상되면 적용하기로 한다! 

---

마치며

비록 실패하긴 했지만 직접 코드를 구현하려고 시도했다는 점이 너무 뿌듯했다. 초반에는 시도조차 못했었는데 오늘은 시도까지 해봤다는게 굉장히 유의미한 날이었다! 이렇게 실력이 조금씩 늘어가는게 눈에 보이니까 공부할 맛이 난다!!!!!