[Swift]BOJ-1158

BOJ-1158번, 요세푸스

문제 📑

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

1158번: 요세푸스 문제

문제 정리 ▾ 

BOJ-1158

• 1~N까지 차례로 들어있는 배열에서 K번째 원소를 삭제
• 배열의 끝에 도달 시, 다시 처음으로 이어지며 카운팅(카운팅은 유지된다) 하여 삭제
• 삭제되는 순서대로 출력하면 끝 !

 

접근 🚶🏻

나의 생각 ▾

• 문제를 보았을 때 처음 생각난 건 매 K번째의 원소를 새로운 배열에 넣어줌과 동시에 삭제해주고, 다 삭제가 되었을 때(기존 배열이 비었을 때) 새로운 배열을 출력하면 된다고 생각했다.
• 처음 문제를 이해하는데만 10분... 이후 생각한 대로 나름 잘 풀어나갔다... 😅

import Foundation

let data = readLine()!.split(separator: " ").map{ Int(String($0))!}, (n, k) =  (data[0], data[1])
var tc : [Int] = Array(1...n)
var cnt = k - 1
var result = [Int]()

while true {
    result.append(tc.remove(at: cnt))
    if tc.isEmpty { break }
    cnt = (cnt + k - 1) % tc.count
}
print("<" + result.map({String($0)}).joined(separator: ", ") + ">")

 

코드 리뷰 ▾

let data = readLine()!.split(separator: " ").map{ Int(String($0))!}, (n, k) =  (data[0], data[1])

• data라는 배열을 만들어 공백(띄어쓰기) 기준으로 Int형 입력을 받은 후에 n, k라는 변수에 각각 넣어주었다.

var tc : [Int] = Array(1...n)

• n은 배열의 원소 개수이므로 1부터 n개까지 원소를 갖는 배열을 만들어줬다.

var cnt = k - 1
var result = [Int]()

• cnt는 삭제되는 인덱스를 알려주는 변수로 배열의 인덱스는 0부터 시작하므로 1을 빼주었다.
• result는 위에서 내 생각대로 새로운 배열(출력할 배열)을 선언해주었다.

while true {
    result.append(tc.remove(at: cnt))
    if tc.isEmpty { break }
    cnt = (cnt + k - 1) % tc.count
}

• 이후 무한 반복시켜 tc라는 배열이 비어질 때까지 코드를 진행시킨다.
• result라는 배열에 삭제될 원소(cnt 번째 원소)를 넣어줌과 동시에 tc배열에서 삭제했다.
• 삭제하고 나서 기존 배열(tc Array)이 비었는지 체크를 해주고, 비어있으면 그대로 끝을 내며, 안 비어있으면 다음 원소 삭제를 위해 cnt의 값을 변경해주었다.
• cnt의 값은 cnt자신과 k-1(기존 인덱스)를 더해주고, tc.count를 통해 tc에 남아있는 원소를 삭제를 할 수 있게 기준을 잡았다.

 

다른 풀이 📎

let input = readLine()!.split(separator: " ").map {Int(String($0))!}

let n = input[0]
let k = input[1]

var queue = Array(1...n)
var result = "<"
var index = k-1

while queue.count != 1 {
    if index >= queue.count {
        index %= queue.count
    }
    
    let value = queue.remove(at: index)
    result += String(value) + ", "
    index += (k-1)
}
result += String(queue.last!) + ">"

print(result)

• 위 풀이와 내 풀이에 차이는 result가 배열이 아닌 String형으로 잡아 바로 출력할 수 있게 구현하였다.
• 이 코드에선 무한반복 없이 queue배열의 남은 원소가 1이 되면 종료되고, 마지막은 자연스럽게 추가해주며 결과를 출력했다.
  • 나도 나름 생각했던 부분인데 새로운 배열에 넣어주는 게 더 깔끔할 줄 알았다...(물론 코드만 신경 썼다..)
• index를 while문 첫 문장에서 배열의 크기 이상이면 그 크기만큼 나눈 값이 나머지를 유지시켰다. → 정말 많이 쓰이는 % 연산자 👍

 

Additional 📂

• 시간과 깔끔한 숏 코딩만 지향하던 나에게 메모리를 신경 쓰게 해주는 계기가 되는 문제였다.
• 많은 메모리가 사용된 건 아니지만, 위에 코드(62384KB)와 내 코드(79692KB) 확연한 차이가 있다.
• 메모리까지 고려를 하여 푸는 연습을 해야겠다.
• 정말 부족하다... 더 노력하자 🥲