[BOJ] 백준 11866 요세푸스 문제 0 (Swift)

문제

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

11866번: 요세푸스 문제 0

풀이

이 문제는 Queue를 사용해서 풀 수도 있고, index를 순회하면서 풀 수도 있습니다.

Queue를 사용해서 풀이하면,
K-1번 만큼 Queue에서 삭제한 요소를 Queue에 삽입시켜주고
K번째가 될 때, Queue에서 삭제연산을 해주면 K번째 요소를 제거할 수 있습니다.
이 동작을 queue가 빌 때 까지 반복해주면 됩니다.

index로 접근은 어떻게 할까요?

초기값은 0번째 인덱스를 가리키고 있고,
index에 k - 1을 더해준 위치의 요소를 제거해주면 됩니다.

여기서 왜 k가 아닌 k - 1인가..에 대해 설명드리자면,
array에서 삭제 연산을 하게되면 array의 크기가 1이 줄어들기 때문에 k가 아닌 k - 1을 더해줬습니다.

또한 index가 array의 범위를 벗어날 수 있기 때문에 더해줄 때 마다,
array의 크기만큼의 mod 연산을 해주었습니다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], k = input[1]
	var array = [Int](1...n)
	var answer: [Int] = []
	var index = 0
	for _ in 0..<n {
	index = (index + k - 1) % array.count
	answer.append(array.remove(at: index))
	}
	print("<\(answer.map { String($0) }.joined(separator: ", "))>")

view raw 요세푸스 문제 0(index).swift hosted with ❤ by GitHub

	struct Queue {
	private var array: [Int] = []
	private var index: Int = 0
	var isEmpty: Bool {
	return array.count - index <= 0
	}
	mutating func push(_ element: Int) {
	array.append(element)
	}
	@discardableResult
	mutating func pop() -> Int? {
	guard !self.isEmpty else {
	return nil
	}
	let element = array[index]
	index += 1
	return element
	}
	}
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], k = input[1]
	var queue = Queue()
	var answer: [Int] = []
	(1...n).forEach { queue.push($0) }
	while !queue.isEmpty {
	for _ in 0..<k - 1 {
	queue.push(queue.pop()!)
	}
	answer.append(queue.pop()!)
	}
	print("<\(answer.map { String($0) }.joined(separator: ", "))>")

view raw 요세푸스 문제 0(Queue).swift hosted with ❤ by GitHub

후기

Queue를 사용하거나 index로 제거하는 방식으로 풀 수 있는 문제였습니다.
Queue를 사용했을 때, K가 크다면 삭제 연산을 하는 횟수가 많으므로 index를 사용하는 것이 조금 더 빠른 것 같습니다.