[선택] 2002 추월

정답 코드

let count = Int(readLine()!)!

var entranceOrder: [Int: String] = [:]
var overtakingDiscrimination: [String: Bool] = [:]

for i in 0..<count {
    let input = readLine()!
    overtakingDiscrimination[input] = false
    entranceOrder[i] =  input
}

var currentOrder = 0
var overtakingNumber = 0

for i in 0..<count {
    let input = readLine()!
    overtakingDiscrimination[input] = true
    if entranceOrder[currentOrder] != input {
        overtakingNumber += 1
    } else {
        if i == count - 1 {
            break
        }
        while overtakingDiscrimination[entranceOrder[currentOrder]!]! {
            currentOrder += 1
        }
    }
}

print(overtakingNumber)

 

코드 설명

• 차량의 수를 count변수에 할당한다.
• entranceOrder 는 입구에서 기록한 차량의 순서를 저장한다.
• overtakingDiscrimination 는 차량이 지나갔는지 여부를 저장한다.
• 출구에서의 통과차량의 입력을 for문으로 입력받는다.
  
  • ✔︎ 새로 차량이 나갈 때마다 비교를 하므로 최대 값을 차량의 수만큼으로 제한된다.
  • ✔︎ 추월한 차량은 반복되어서 세지 않는다.
  • 통과한 차량의 Bool값을 true로 변경
  • [if] entranceOrder의 currentOrder에 해당되는 차량이 출구에서 들어온 차량(input)과 다르다면
  • currentOrder의 차량을 추월 했으므로 overtakingNumber의 수를 1 증가 시킨다.
  • [else]  entranceOrder의 currentOrder에 해당되는 차량이 출구에서 들어온 차량(input)과 같다면
    • [while] 이미 지나간 차량에 대해서는 추가적으로 for문을 반복하면서 확인할 필요가 없으므로
      • 이미 지난간 차량이 entranceOrder에 있다면 그 값을 지나간다. 
      • currentOrder의 수를 증가시킨다.
    • [if] while문이 차량 수 보다 많이 증가하는 것을 막기 위해 입력받은 차량의 수의 지날 경우
    • break으로 else문을 탈출한다.

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

2002번: 추월