아직도 바킹독 연결 리스트 강의 제자리 걸음... 문제 푸는 게 훈련이 덜 되어서 그런지 하나 푸는 데 시간이 오래 걸려서 진도를 못 나가고 있다.
요세푸스 문제는 사람들이 원을 이루어 앉아 있고 양의 정수 k가 주어질 때, 모든 사람이 제거될 때까지 순서대로 k번째 사람을 제거해서 수열을 만드는 것이라고 한다.
보자마자 원형 연결 리스트가 생각이 났다.(자료구조 스터디 한 보람이 있군 😁) 헤드 노드 없이 첫 번째 노드의 이전 노드를 마지막 노드로, 마지막 노드의 다음 노드를 첫 번째 노드로 해서 풀었다.
다 풀고 다른 사람들 풀이를 보니까 나머지 연산을 잘 이용해서 리스트 pop을 하는 방식이던데 훨씬 간단해 보이긴 했다. 리스트 pop 연산이 느리댔는데 이 문제는 최대 자료수가 5000개밖에 안 돼서 시간 초과가 안 나는 걸까..
🦾 배운점
join()은 배열의 모든 원소가 문자열일 때만 사용할 수 있는 거였다. 이번 문제에서처럼 배열의 원소가 문자열이 아닌 경우 str()을 사용해서 형변환을 할 수 있다. 각 원소에 대해 실행해야 하므로 map() 활용!
n, k = map(int, input().split())
circle = [] # 원 데이터 배열
next = [] # 다음 노드 배열
prev = [] # 이전 노드 배열
# 배열 초기화
for i in range(n) :
circle.append(i + 1) # 인덱스가 0부터 시작하므로 i + 1로 채운다.
if i != n - 1 : # 마지막 노드가 아니면
next.append(i + 1) # next는 다음 주소인 i + 1
else :
next.append(0) # 마지막 노드면 next는 첫 번째 노드의 주소인 0
if i == 0 : # 첫 번쨰 노드면
prev.append(n - 1) # prev는 마지막 노드의 주소인 n - 1
else :
prev.append(i - 1) # 첫 번째 노드가 아니면 prev는 이전 주소인 i - 1
count = 0 # 순서를 세는 변수
addr = 0 # 현재 보고 있는 노드의 주소
result = [] # 결과 배열
while addr != next[addr] : # next가 자기 자신을 가리키지 않는 동안 반복 (하나 남을 때까지)
count += 1
if count % k == 0 : # count가 k번째의 배수이면
result.append(circle[addr]) # 결과 배열에 데이터 추가
next[prev[addr]] = next[addr] # 이전 노드의 다음 노드에 현재 노드의 다음 노드 연결
prev[next[addr]] = prev[addr] # 다음 노드의 이전 노드에 현재 노드의 이전 노드 연결
addr = next[addr] # 다음 노드부터 다시 순회
result.append(circle[addr]) # 마지막 하나도 결과 배열에 추가
print('<' + ', '.join(map(str, result)) + '>')
