[2002] 추월

생각

• 추월했을 경우 앞차 a와 뒷차 b의 위치는 서로 바뀐다.
• a b c d e -> b e d a c 인 경우 정답은 3대
  • b a c d e
  • b a c e d
  • b a e c d
  • b e a c d
  • b e a d c
  • b e d a c
• 입력 가능 차의 대수는 총 1000대
• bedac를 다시 알파벳 배열 순으로(처음 들어왔던 순서) 정렬할 때, 뒤로 보내야 할 차량의 개수가 확정적으로 추월한 차량의 수이다.
  • 차량의 순서가 차례대로가 될 수 있을때까지 차례가 맞지 않는 차를 제외하고, 순서가 맞는 순간 제외된 차량의 수가 추월한 차량의 수이다.
  • bedac 에서 e다음 d는 옳지 않으므로 제거
  • bdac 에서 d다음 a는 옳지 않으므로 제거
  • bac에서 b다음 a는 옳지 않으므로 제거
  • ac는 차례가 맞으므로 제거된 b,d,e 3대가 정답

처음 코드

import Foundation

func passCarCheck(inCar: Dictionary<String, Int>, outCar: inout [String]) -> Int{
    var count = 0
    while true{
        for a in 0..<outCar.count - 2{
            let b = a + 1
            if inCar[outCar[a]]! > inCar[outCar[b]]!{
                outCar.remove(at: a)
                count += 1
            }
        }
        if isSorted(inCar: inCar, outCar: outCar) {
            break
        }
    }
    return count
}

func isSorted(inCar: Dictionary<String, Int>, outCar: [String]) -> Bool{
    for a in 0..<outCar.count - 2{
        let b = a + 1
        if inCar[outCar[a]]! > inCar[outCar[b]]!{
            return false
        }
    }
    return true
}

let carCount = Int(readLine()!)!

var inCar = Dictionary<String, Int>()
var outCar = [String]()

for i in 0..<carCount{
    inCar[readLine()!] = i
}
for _ in 0..<carCount{
    outCar.append(readLine()!)
}

print(passCarCheck(inCar: inCar, outCar: &outCar))

런타임에러남..
예상

• 입력이 한대만 주어져서

수정

import Foundation

func passCarCheck() -> Int{
    var count = 0
    if inCar.count <= 1 {
        return 0
    }
    while true{
        for i in 0..<outCar.count - 2{
            if inCar[outCar[i]]! > inCar[outCar[i+1]]!{
                outCar.remove(at: i)
                count += 1
            }
        }
        if isSorted() {
            break
        }
    }
    return count
}

func isSorted() -> Bool{
    if outCar.count <= 1{
        return true
    }
    for i in 0..<outCar.count - 2{
        if inCar[outCar[i]]! > inCar[outCar[i+1]]!{
            return false
        }
    }
    return true
}

let carCount = Int(readLine()!)!

var inCar = Dictionary<String, Int>()
var outCar = [String]()

for i in 0..<carCount{
    inCar[readLine()!] = i
}
for _ in 0..<carCount{
    outCar.append(readLine()!)
}

print(passCarCheck())

그래도 런타임 에러남
백준의 런타임 에러의 종류는 다음과 같다고 한다

• segmentation fault
• 재귀 함수 호출이 너무 깊어진 경우
• 잘못된 메모리 참조
• 배열 범위를 넘어가게 참조하거나 (배열 크기를 넉넉하게 잡고 , 예외가 있는지 확인하자)
• divide by zero

내 생각엔 배열 범위를 넘어가게 참조..아직 예외가 있는듯 하다.

디버깅을 하던 중 아예 로직이 잘못된것을 깨달았다
1. 2대일 경우 outCar.count -2 때문에 0이 출력됨.
2. outCar.count - 1이 맞는데, 이 경우 이전 진행되던 i 값과 outCar.count간의 논리적인 오류 발생
-> 내가 생각했던건 하나를 제외할때마다 처음부터 순서 확인을 해야하는 거였으므로, break를 추가해주었다.

import Foundation

func passCarCheck() -> Int{
    var count = 0
    while true{
        if outCar.count <= 1{
            return count
        }
        for i in 0..<outCar.count - 1{
            if inCar[outCar[i]]! > inCar[outCar[i+1]]!{
                outCar.remove(at: i)
                count += 1
                break
            }
        }
        if isSorted() {
            break
        }
    }
    return count
}

func isSorted() -> Bool{
    if outCar.count <= 1{
        return true
    }
    for i in 0..<outCar.count - 1{
        if inCar[outCar[i]]! > inCar[outCar[i+1]]!{
            return false
        }
    }
    return true
}

let carCount = Int(readLine()!)!

var inCar = Dictionary<String, Int>()
var outCar = [String]()

for i in 0..<carCount{
    inCar[readLine()!] = i
}
for _ in 0..<carCount{
    outCar.append(readLine()!)
}

print(passCarCheck())

맞았다~~
1시간동안 땅굴팜..^^