백준 2872번: 우리집엔 도서관이 있어 (S1) - Python 풀이

문제 설명

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

상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다.

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다. 가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 책의 개수 N이 주어진다. (N ≤ 300,000)

다음 N개 줄에는 가장 위에 있는 책부터 아래에 있는 책까지 순서대로 주어진다.

출력

첫째 줄에 몇 번만에 책을 정렬할 수 있는지 출력한다.

예제 입력 1

3
3
2
1

예제 출력 1

2

예제 입력 2

4
1
3
4
2

예제 출력

2

문제 요약) 책 하나를 빼서 가장 위에 놓는 것이 책 순서를 변경하는 유일한 방법일 때, 책을 몇 번 이동시켜야 오름차순 정렬이 되는지 출력해라.

풀이 과정

일단 단순히 '이동의 횟수'만 알면 되니까 아래에서 윗쪽으로의 이동이 필요한 숫자가 몇 개가 되는지만 찾으면 됩니다.

• 최댓값 기준 리스트에서 최댓값의 오른쪽에 있는 값들은 무조건 옮겨야 됩니다 왼쪽으로 → 최댓값의 오른쪽에 위치한 숫자의 개수를 answer의 초기값으로 설정합니다.
• 최댓값 기준 리스트에서 최댓값의 왼쪽에 있는 값들은 다 1씩 차이나는 게 아니라면 어차피 순서의 이동이 필요합니다. → 옆의 값과 차이가 1이 아니라면 answer에 + 1

이 문제도 파이썬의 sys로 빠른 입력을 사용하지 않으면 시간 초과가 나는 문제입니다.

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
books = [int(input()) for _ in range(N)]

# 최댓값과 최댓값의 인덱스를 구한다
max_value = max(books)
max_index = books.index(max_value)
# 최댓값의 오른쪽에 있는 숫자 개수로 초기화
answer = N - 1 - max_index

# 최댓값의 왼쪽에 있는 값들 하나씩 확인
for i in range(max_index - 1, -1, -1):
    # 1씩 차이나지 않으면 answer 카운트 추가
    if books[i] + 1 != max_value:
        answer += 1
    # 1씩 차이나면 현재 책의 값으로 max를 업데이트 해서 그 다음 책도 확인
    else:
        max_value = books[i]
        
print(answer)

이상입니다.