본문 바로가기
코딩테스트

[Python] 백준 1158번 - 요세푸스 문제

by 박매트 2024. 6. 11.

https://www.acmicpc.net/problem/1158

 

나의 답

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

li = []
index = -1
print("<",end="")

for i in range(1,N+1,1):
    li.append(i)

while True:
    
    for _ in range(K): # 3번 건너뛰기.이 때 마지막 index일 경우, 0으로 바꾸기
        index+=1
        if index == N:
            index = 0

    if len(li)==1: # 마지막  
        print(li[index], end="")
        break

    print(li[index],end=", ")

    li.remove(li[index])
    index-=1
    N-=1

print(">",end="")

 

1번부터 N번까지 N명의 사람이 원을 이룰 수 있도록 배열을 만들었다.

 

수건돌리기 하는 느낌으로, 3칸씩 건너뛴 값을 출력하고, 그 값을 삭제했다.

삭제할 때 index와 N(개수)를 삭제했다. index를 삭제해야 삭제한 지점으로 부터 3칸 떨어진 곳을 확인할 수 있다.

 

그리고 출력은 <요소,요소,요소> 이런식으로 출력되어야 해서... 구리디 구린 방식으로 처음과 끝에 < >  코드를 짜줬다..^^

 

다른 사람 코드 - https://velog.io/@thguss/%EB%B0%B1%EC%A4%80-1158.-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-with.-Python-%ED%81%90-%EB%AC%B8%EC%A0%9C%EC%97%90%EC%84%9C-deque%EB%8A%94-%ED%95%84%EC%88%98-%EB%B3%84%EA%BC%AC%EB%A6%AC-%EB%95%85%EB%95%85 참고

from collections import deque

n, k = map(int, input().split())

# 1~n번 사람
people = deque()
for i in range(1, n+1): people.append(i)
result = []

while people:
  for _ in range(k-1):
    people.append(people.popleft())

  result.append(people.popleft())

print(str(result).replace('[', '<').replace(']', '>'))

 

와... 역시나 큐 문제 였구나...

앞에 있는 걸 뒤에 붙이면서 생각하면 되는 구나... !! 

2번 건너뛰면 앞에 있느 2개가 순서대로 뒤로 붙여질 거고, 3번째 사람이 result에 append 된다니.. 천재적이다...

 

Kotlin 버전 코드

import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val k = scanner.nextInt()

    val people: Queue<Int> = LinkedList()
    for (i in 1..n) {
        people.add(i)
    }

    val result = mutableListOf<Int>()

    while (people.isNotEmpty()) {
        for (i in 1 until k) {
            people.add(people.poll())
        }
        result.add(people.poll())
    }

    println(result.joinToString(prefix = "<", postfix = ">", separator = ", "))
}

 

느낀 점

큐를 잘 사용해보자...