[BOJ] 1158번 - 요세푸스 문제

문제

 

풀이 코드

var result = [Int]()
let inputs = readLine()!.split(separator: " ")
var num: [Int] = Array(1...Int(inputs[0])!)
var idx = Int(inputs[1])! - 1

while true {
    result.append(num.remove(at: idx))
    if num.isEmpty { break }
    idx = (idx + Int(inputs[1])! - 1) % num.count
}
print("<\(result.map({ String($0)}).joined(separator: ", "))>")

 

풀이 과정

문제를 이해하는데 그림을 그려야 했다.. 그래서 발로 그린듯한 그림을..

이렇게 원형으로 앉아있을때 K번 순으로 제거하는 문제였다

K번째를 셀때, 제거된 자리는 건너뛰고 세어야 한다!! 

 

코드에서 inputs[0] 에는 N 이,  inputs[1] 에는 K 가 들어간다.

 

그리고 나서 규칙을 찾기위해 열심히.. 그림을 그렸다

처음 idx 는 K - 1 ( 인덱스는 0부터 시작하기 때문!! ) 가 되고,

이후로 제거할때 마다 idx 를 바꿔줘야 하는데, 어떻게 바꿀지를 그리면서 고민한 결과 규칙을 찾았다!

 

1. 우선 idx 인덱스 요소를 제거한다

2. 현재 idx 의 값에 K-1 을 더한후, 제거후 남은 배열의 갯수로 나눈 나머지로 재설정한다 ( idx = (idx + (k-1)) % Array.count )

3. 무한 루프로 돌되, 제거후 배열이 비어 있는 상태가 되면 루프를 종료시킨다!

 

알고나면 간단한 문제였다..

이래서 그리면서 생각하는게 중요한가봄..