백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1158 요세푸스 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/1158

반응형

솔루션 살펴보기!!

from collections import deque

def josephus_problem(N, K):
    queue = deque(range(1, N + 1))
    result = []

    while queue:
        queue.rotate(-K)
        result.append(queue.pop())

    return result

def main():
    N, K = map(int, input().split())
    result = josephus_problem(N, K)
    print('<' + ', '.join(map(str, result)) + '>')

if __name__ == "__main__":
    main()

상세 코드 설명!!

입력 처리

N, K = map(int, input().split())

• N과 K 값을 입력받습니다. N은 사람의 수, K는 제거할 순서를 의미합니다.
• input().split()은 공백을 기준으로 입력을 분리한 후, map(int, ...)을 통해 각각의 값을 정수로 변환합니다.

큐 초기화

queue = deque(range(1, N + 1))

• range(1, N + 1)은 1부터 N까지의 숫자 리스트를 만듭니다. 이 리스트를 deque에 담습니다.
• deque는 이중 연결 리스트 형태로 구현된 큐 자료구조입니다. 리스트에 비해 삽입과 삭제가 빠릅니다.

결과 저장을 위한 리스트 초기화

result = []

 

요세푸스 순열 생성

while queue:
    queue.rotate(-K)
    result.append(queue.pop())

• while queue:는 큐가 비어있지 않은 동안 반복합니다.
• queue.rotate(-K)는 큐를 왼쪽으로 K만큼 회전시킵니다. 이는 큐의 K번째 요소가 맨 뒤로 가도록 합니다.
• queue.pop()은 큐의 맨 마지막 요소를 제거하고, 그 요소를 result에 추가합니다.

결과 출력

print('<' + ', '.join(map(str, result)) + '>')

• result 리스트의 요소들을 문자열로 변환한 후, ,로 구분하여 하나의 문자열로 합칩니다.
• 이 문자열을 <와 >로 감싸서 최종 출력을 생성합니다.

728x90

주요 개념

1. deque (Double-ended Queue):
   • deque는 Python의 collections 모듈에서 제공하는 자료구조입니다.
   • 큐의 양쪽 끝에서 빠르게 삽입과 삭제가 가능합니다. 특히, rotate() 메서드는 큐를 회전시키는 데 유용합니다.
   • 이 코드에서는 사람들을 원형으로 배열하기 위해 deque를 사용합니다. 이는 효율적인 인덱스 이동을 가능하게 합니다.
2. 회전 (Rotation):
   • rotate(-K)는 큐를 왼쪽으로 K만큼 회전시킵니다. 이는 리스트의 인덱스 계산 없이, 효율적으로 다음 제거 대상을 찾는 방법입니다.
   • 회전 후 pop()을 통해 제거할 요소를 쉽게 선택할 수 있습니다.
3. 리스트 (List):
   • Python의 기본 리스트 자료구조를 사용하여 제거된 요소를 순서대로 저장합니다.
4. 반복문:
   • while queue:는 큐가 비어 있을 때까지 반복합니다. 이는 모든 사람이 제거될 때까지 순서를 반복하는 핵심 로직입니다.
5. 문자열 조작:
   • map(str, result)는 result 리스트의 모든 요소를 문자열로 변환합니다.
   • join() 메서드는 리스트의 요소들을 특정 구분자로 연결하여 하나의 문자열로 만듭니다.

이 코드는 요세푸스 문제를 해결하기 위해 deque 자료구조와 회전을 사용하여 효율적으로 사람들을 제거하는 순서를 구합니다. 이 과정에서 큐 회전, 리스트 조작, 반복문 등의 중요한 개념이 사용되었습니다. 이를 통해 가독성과 성능이 모두 향상된 코드가 작성되었습니다. 이 코드의 구조는 명확하고, 각 부분이 어떻게 작동하는지 이해하기 쉽습니다.