[Swift] 백준 1713 - 후보 추천하기

문제 : https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

내 풀이

import Foundation

let n = Int(readLine()!)!
let m = Int(readLine()!)! //추천 횟수
let nums = readLine()!.split(separator:" ").map { Int(String($0))! }
var stack:[Int] = [] //사진틀 (스택)
var count:[Int] = Array(repeating:0, count:101) //추천횟수를 담을 배열

- 사진틀에서 "가장 오래된 사진을 삭제한다"를 보고 스택 자료구조를 이용하면 되겠구나 하고 사진틀에 올라가있는 번호들이 담긴 리스트를 'stack'이라는 이름으로 초기화했다.

- 특정 학생의 추천횟수를 증가시키거나 0으로 바꾸는데, 번호는 1부터 100까지의 자연수이다 라는 조건에서 추천횟수를 담을 배열인 count를 크기 101로 하여 초기화했다.

 

for i in nums {
  if stack.count == n {
    if !stack.contains(i){ //액자에 없는경우 추가해야함
      let min = count.filter { $0 != 0 }.min()!
    
      for j in stack {
        if count[j] == min {
          count[j] = 0
          if let index = stack.firstIndex(of: j){
            stack.remove(at: index)
          }
          break
        }
      }
      stack.append(i)
    }
  }
  count[i] += 1
}

3. 비어있는 사진틀이 없는 경우(=stack의 사이즈가 n인 경우), 현재라지 추천받은 횟수가 가장 적은 학생의 사진을 삭제하는데 이때 현재까지 추천받은 횟수가 가장 적은 학생이 2명이면 가장 오래된 번호를 삭제한다.

- 여기서 또 조건이 나뉘는데, 이미 게시된 학생이면 추천수만 늘리므로, 먼저 if !stack.contains(i)로 사진틀에 걸려있는 후보인지에 대한 조건을 걸어주었다.

- 그리고 추천받은 횟수가 가장 적은 학생을 stack에서 찾아 그 학생의 추천횟수를 초기화해주고, stack에서 지워주었다. (끝까지 돌지 않고 break를 하는 이유는 stack 처음부터 돌면서 맨 처음(가장 오래된 사진)만 삭제하면 되기때문에, 가장 오래된 사진을 삭제하고나서 for문을 탈출하도록 했다.

- 그리고 이후 추천이 들어온 후보를 stack에 추가 및 추천 횟수를 +1을 해주었다.

 

else {
    if !stack.contains(i) { //사진 걸기
      stack.append(i)
    }
  }
  count[i] += 1

- 스택이 꽉차지 않은 상황이고 이미 걸려있는 후보가 아니라면 stack에 추가해주었고 마찬가지로 추천횟수를 늘렸다.

 

print(stack.sorted().map { String($0) }.joined(separator:" "))

- 이부분은 증가하는 순서대로 출력해야하기때문에 먼저 sorting 후 출력!

 

다른사람 코드

let n = Int(readLine()!)!
_ = readLine()
let array = readLine()!.split(separator: " ").map { Int($0)! }
var photos: [(Int, Int)] = []

for arr in array {
    if photos.contains(where: { $0.0 == arr }) {
        let findIndex = photos.firstIndex { $0.0 == arr }!
        photos[findIndex].1 += 1
    } else {
        if photos.count == n {
            let removed = photos.filter { $0.1 == photos.map { $0.1 }.min()! }.first!
            photos.remove(at: photos.firstIndex { $0 == removed }!)
        }
        photos.append((arr, 1))
    }
}

photos.map { $0.0 }.sorted(by: <).forEach { print($0, terminator: " ")}

- (후보, 추천 횟수) 튜플 리스트로 관리했고, firstIndex를 클로저로 조건을 걸어서 첫번째 인덱스를 찾을 수 있닫는 것을 새롭게 알게되었다.