2872번: 우리집엔 도서관이 있어

문제 풀이 아이디어

처음에는 맨 위에만 책을 올릴 수 있다고 했기 때문에 stack이라고 생각했습니다. 하지만 맨 위에서만 pop할 수 있는 stack과는 달리 이 문제에서는 책을 어느 위치에서 관계 없이 어느 위치에서나 뺄 수 있습니다.

물론 시뮬레이션을 통해서 구현할 수도 있을 것입니다. 직접 책들을 Array에 담고 순서를 바꾸어 가면서 정렬의 갯수를 세는 것이죠. 하지만 이 방법은 시간 초과가 나올 가능성이 99.999%입니다.

따라서 결론은 주어진 자료를 변형하지 않고 규칙을 찾아야 합니다. 아래에 예시를 들어 설명해보겠습니다.

예시

3
1
4
5
2

일단 어떤 형태로 책이 위치하던지 관계 없이 가장 아래에 있어야 하는 책인 5는 뺄 필요가 없습니다. 다른 책들을 정렬하는 과정에서 자동으로 맨 아래에 위치할 것이기 때문입니다.

또한 4 아래에 있는 책들은 무조건 빼야 합니다. 왜냐하면 5가 맨 아래로 가야하기 때문입니다.

그렇다면 5 위에 있는 책들 중에서 우리가 정렬하지 않아도 되는 책의 갯수를 구해보겠습니다. 5 위에 있는 책들 중에 (5 4 3 2 1 )의 순서대로 이미 정렬된 책은 뺄 필요가 없습니다. 즉 4와 3은 이미 정렬된 상태나 마찬가지 입니다. 직접 정렬하면서 보겠습니다.

2를 빼서 맨 위에 올리면 아래와 같이 됩니다.

2
3
1
4
5

마지막으로 1을 빼서 맨 위에 올리면 정렬이 마무리됩니다.

1
2
3
4
5

이를 일반화하면 N 위에 있는 N - 1은 정렬할 필요가 없습니다. 마찬가지로 N - 1 위에 있는 N - 2는 정렬할 필요가 없습니다.

따라서 위 원리를 활용해서 N - 1에서 정렬할 필요가 없는 책의 갯수를 빼주면 답을 구할 수 있습니다.

코드

// 입력 받기
let N = Int(readLine()!)!
var books = [Int]()
for _ in 0..<N {
    books.append(Int(readLine()!)!)
}

// 위의 책들을 탐색하기 편하게 뒤집기
books.reverse()

// 가장 아래에 있어야 하는 책인 N보다 위에 N - 1이 있으면 정렬할 필요가 없음
var noSortBook = N - 1

// 가장 아래에 있어야 하는 책인 N의 위치
let bookPosition = books.firstIndex(of: N)!

// 정렬해야만 하는 책의 권수 (일단 N 빼고 전부 정렬해야 한다고 치고)
var booksToSort = N - 1

// 가장 아래에 있어야 하는 책 N보다 위해 정렬할 필요가 없는 책 찾기
for i in (bookPosition + 1)..<N {
    if books[i] == noSortBook { //👉 정렬할 필요가 없는 책이라면 (N - 1)
        noSortBook = books[i] - 1 //👉 다음 정렬할 필요가 없는 책 (N - 1위에 N - 2)
        booksToSort -= 1 //👉 정렬해야만 하는 책의 권수
    }
}

print(booksToSort)