[1158] 요세푸스 문제

이번문제도 C++로 작성했던 문제를 swift로 다시 풀어보았다.

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

1158번: 요세푸스 문제

 

풀이

문제에 적힌 방법대로 풀면 된다. 대신 기존의 배열에서 제거하는 방법이 아닌 요소를 0으로 변환하면서 배열을 순회했다. 애초에 요소는 1부터 시작하기 때문이다. 배열의 요소가 0이 아니라면 카운트를 증가하지 않고 인덱스만 증가. 카운트가 k값이 되면 그때의 요소를 요세푸스 배열에 담는 방식으로 문제를 풀어보았다.

 

풀고나서 다른 사람들의 풀이를 보니 간결하고 빠른코드가 많았다.

http://boj.kr/ef42c280ec1c4098b04deca633c2b1dc

//
//  main.swift
//  1158_swift
//
//  Created by Hyun on 2022/01/20.
//

import Foundation

let NK = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NK[0]
let K = NK[1]

var arr = Array(1...N)
var josephus = [Int]()

var cnt = 0
var idx = -1

while josephus.count < arr.count{
    cnt += 1
    idx += 1
    if idx >= arr.count{
        idx = 0
    }
    if arr[idx] == 0{
        while arr[idx] == 0{
            idx += 1
            if idx >= arr.count{
                idx = 0
            }
        }
    }
    if cnt == K{
        josephus.append(arr[idx])
        arr[idx]=0
        cnt = 0
        continue
    }
}

var text = "<"
for j in josephus{
    if j == josephus.last{
        text+=String(j)
    }else{
        text+=String(j)+", "
    }
}
text += ">"
print(text)