배열 A가 주어졌을 때, 중복 없는 숫자들의 집합을 무작위로 섞어야(shuffle) 한다고 가정해 봅시다. 예를 들어 입력이 [1,2,3]이라면 셔플 결과는 [1,3,2]가 될 수 있고, 리셋한 뒤 다시 셔플하면 [2,3,1]과 같은 새로운 순서가 나올 수 있습니다.
문제 해결 접근 방법
이 문제를 해결하기 위해 init(), reset(), shuffle() 세 가지 메서드를 구현합니다. 각 메서드는 다음과 같이 동작합니다.
1. init() — 초기화
- original: 주어진 배열의 복사본을 저장합니다.
- temp: 원본 배열(nums)을 그대로 참조합니다.
- indices: 0부터 배열 길이 - 1까지의 인덱스 목록을 생성합니다.
2. reset() — 초기 상태 복원
- reset() 메서드를 호출하면 저장해 둔 original 배열을 그대로 반환하여 초기 상태로 되돌립니다.
3. shuffle() — 무작위 섞기
- temp 배열의 길이가 0이면 빈 배열을 반환합니다.
- indices 배열에서 인덱스 i와 j를 각각 무작위로 선택합니다.
- i번째와 j번째 요소를 서로 교환(swap)합니다.
- 섞인 temp 배열을 반환합니다.
4. getAllPermutation() — 모든 순열 생성 (백트래킹)
추가적으로, 재귀와 백트래킹 기법을 사용해 가능한 모든 순열을 생성하는 getAllPermutation() 메서드도 구현할 수 있습니다. 초기 호출 시 i = 0으로 시작하며 다음과 같이 동작합니다.
- curr := i 로 설정합니다.
- i가 배열의 길이와 같아지면 현재 nums 배열의 복사본을 결과 리스트(all)에 추가하고 종료합니다.
- j를 curr부터 배열 길이까지 반복하면서:
- j번째와 curr번째 요소를 교환합니다.
- getAllPermutation(nums, curr + 1)을 재귀 호출합니다.
- 다시 j번째와 curr번째 요소를 교환하여 원상 복구합니다(백트래킹).
구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
import random
class Solution(object):
def __init__(self, nums):
self.original = [x for x in nums]
self.temp = nums
self.indices = [x for x in range(len(nums))]
def reset(self):
return self.original
def shuffle(self):
if not len(self.temp):
return []
i = random.choice(self.indices)
j = random.choice(self.indices)
self.temp[i], self.temp[j] = self.temp[j], self.temp[i]
return self.temp
ob = Solution([1,2,3])
print(ob.shuffle())
print(ob.reset())
print(ob.shuffle())
입력
[1,2,3]으로 초기화한 후, shuffle(), reset(), shuffle()을 순서대로 호출
출력
[2, 1, 3]
[1, 2, 3]
[2, 3, 1]
출력 결과를 보면 shuffle() 호출 시마다 배열이 무작위로 섞이고, reset()을 호출하면 항상 초기 배열 [1, 2, 3]으로 복원되는 것을 확인할 수 있습니다. 이러한 설계는 Fisher-Yates 셔플 알고리즘의 개념과 유사하며, 카드 게임이나 데이터 샘플링 등 다양한 분야에 활용될 수 있습니다.