[SWEA] 3499. 퍼펙트 셔플 (Python/D3)

---

[문제 링크] 👇

SW Expert Academy

---

풀이

💡카드를 절반으로 나눠서 각자 저장한 후 결과 덱을 생성한다. 홀수일 경우 마지막 남은 카드를 추가한다.

 

해결 방법에는 다음과 같은 방법들이 있다.

 

1️⃣ pop() 사용

while len(second_half) > 0:
    result.append(first_half.pop(0))  # 첫 번째 원소를 빼서 결과에 넣기
    result.append(second_half.pop(0))

• pop() 을 사용하면 성능이 다소 저하될 수 있다. 
• 리스트의 맨 앞 요소를 제거할 때마다 나머지 요소를 앞으로 당겨야 하므로, 성능 상 비효율적이다.

 

2️⃣ 덱 사용

while second_half:
    result.append(first_half.popleft())
    result.append(second_half.popleft())

• deque 을 활용해 popleft() 로 리스트의 앞에서 요소를 제거하는 비용을 O(1)로 줄였다.
• pop() 을 사용하는 것 보다 훨씬 효율적이다.

 

3️⃣ 리스트를 교차로 합치기

for i in range(len(second_half)):
    result.append(first_half[i])
    result.append(second_half[i])

• 단순히 두 리스트를 for 문으로 처리하는 방법도 있다.
• 위의 두 방법보다 코드가 훨씬 간결하고 실행 속도도 빠르다.

 

Solution

import math
T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())  # 카드 수
    card = list(map(str, input().split()))
    first_half = [card[i] for i in range(math.ceil(N / 2))]  # 카드의 절반에서 앞 카드들만 저장
    second_half = [card[i] for i in range(math.ceil(N / 2), N)]  # 카드의 절반에서 뒤 카드들만 저장
    result = []
    while len(second_half) > 0:
        result.append(first_half.pop(0))  # 첫 번째 원소를 빼서 결과에 넣기
        result.append(second_half.pop(0))
    # 홀수 일때 first 리스트는 하나의 카드가 남기 때문에 따로 추가
    if N % 2 != 0:
        result.append(first_half.pop())
    print(f"#{test_case}", end=' ')
    print(*result)

 

수정한 코드

from collections import deque
import math

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())  # 카드 수
    card = input().split()

    # 절반으로 나눈 덱을 deque로 만들어 popleft()로 효율적인 제거 수행
    first_half = deque(card[:math.ceil(N / 2)])
    second_half = deque(card[math.ceil(N / 2):])

    result = []
    # 두 반쪽을 교차로 섞어 새로운 덱을 생성
    while second_half:
        result.append(first_half.popleft())
        result.append(second_half.popleft())

    # 홀수일 때 첫 번째 반쪽에 한 장 더 남아있는 경우 추가
    if first_half:
        result.append(first_half.popleft())

    # 결과 출력
    print(f"#{test_case} {' '.join(result)}")

 

 

효율적인 코드

T = int(input())  # 테스트 케이스 수
for test_case in range(1, T + 1):
    N = int(input())  # 카드 수
    card = input().split()
    
    # 카드 덱을 절반으로 나누기
    mid = (N + 1) // 2  # 홀수일 때 앞쪽 덱에 하나 더 배정
    first_half = card[:mid]
    second_half = card[mid:]
    
    # 결과 덱 생성
    result = []
    for i in range(len(second_half)):
        result.append(first_half[i])
        result.append(second_half[i])
    
    # 홀수일 경우 마지막 남은 카드 추가
    if N % 2 != 0:
        result.append(first_half[-1])

    print(f"#{test_case} {' '.join(result)}")

 

 

👩‍💻 회고

카드를 절반으로 나눌 때부터 뇌가 굳은 것 같다. 홀수일 경우 원하는대로 나눠지지 않았기 때문이다. 

풀이가 다양한데 내 코드는 효율적이지 못하다. 성능 생각도 하면서 코드를 짜는 노력이 필요하다.

---