[백준(BOJ)] 2164번 : 카드2 - PYTHON[파이썬]

www.acmicpc.net/problem/2164

2164번: 카드2

 

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 큐

 

---

 

⊙ 문제 접근 과정

 

제일 먼저 내가 문제에 접근한 방법은 QUEUE다.

 

큐로 문제를 접근하여 풀었더니 손쉽게 풀었다.아래엔 내가 직접 구현한 큐 코드이다.

 

N = int(input())
L = list(range(1,N+1))


while (len(L)>1):
    L.pop(0)
    temp = L.pop(0)
    L.append(temp)


print(L.pop(0))

 

하지만 시간 초과가 뜬 코드다.

 

시간을 더 줄일 수 있는 방법을 찾아야만 한다. 시간 복잡도를 더 줄일 수 있는 방법은 뭘까?

 

여러 가지가 있지만 그중 파이썬의 라이브러리를 적극 활용하는 방안이 있다.

파이썬 라이브러리 중 collection의 deque이 있다.

 

두번째 문제 접근 방법은 덱을 이용해 코드를 구현해봤다.

 

라이브러리를 사용하여 문제를 푸니 타임 리미트를 해결할 수 있었다.

코드는 위에 직접 구현한 코드와 다르지 않다.

 

아래 문제 풀이에 코드를 통해 확인해보자.

 

그리고 문제를 풀다 일정한 규칙을 이루는 것 같아서 시간 복잡도를 줄일 겸 세 번째 풀이를 생각해봤다.

 

세 번째 문제 접근 방법은 저 출력 속에 일정한 규칙을 발견하여 공식을 찾는 방법이다.

시간 복잡도 부분에선 이게 가장 최강이지만 난이도가 상당하다.

 

INPUT -> 2 OUTPUT -> 2

INPUT -> 3 OUTPUT -> 2

INPUT -> 4 OUTPUT -> 4

INPUT -> 5 OUTPUT -> 2

INPUT -> 6 OUTPUT -> 4

INPUT -> 7 OUTPUT -> 6

INPUT -> 8 OUTPUT -> 8

 

보이는가? 규칙이 존재한다. 분명히.

OUTPUT을 유심히 보자. 성공한다면 시간 복잡도를 엄청나게 줄일 수 있다.

 

3일 때 : (3 - 2) * 2 = 2

4일 때 : (4 - 2) * 2 = 2

5일 때 : (5 - 4) * 2 = 2

6일 때 : (6 - 4) * 2 = 4

7일 때 : (7 - 4) * 2 = 6

8일 때 : (8 - 4) * 2 = 8

 

[ INPUT - 2**(INPUT>2의 제곱) ] * 2이다.

 

세 번째 문제 풀이도 아래에서 확인해보자

 

---

 

⊙ 문제 풀이

 

from collections import deque

N = int(input())
deque = deque([i for i in range(1, N+1)])

while(len(deque) >1):
    deque.popleft()
    move_num = deque.popleft()
    deque.append(move_num)
    
print(deque[0])

 

AND

 

input = int(input())
square = 2

while True:
    if (input == 1 or input == 2):
        print(input)
        break
    square *= 2
    if (square >= input):
        print((input - (square // 2)) * 2)
        break

 

---

⊙ 결과

 

 

---

 

 

⊙ 마무리

 

 

일정한 규칙을 찾고 공식을 만드는 데 성공하면 시간 복잡도와 공간 복잡도를 엄청나게 줄일 수 있다.

 

하지만 난이도가 상당하다.