BOJ 3231 - 카드놀이

문제

BOJ 3231 - 카드놀이

1부터 N까지의 카드를 섞은 순서가 주어질 때, 인접한 두 카드의 숫자가 내림차순인 경우의 수를 세는 문제이다. 카드들이 놓인 순서를 역추적하여 값 기준 인접 쌍에서 "나중에 놓인 쪽이 먼저 놓인 것보다 앞에 있는" 경우를 카운트한다.

입력

첫 줄에 카드 수 N이 주어진다. 이후 N줄에 걸쳐 카드가 놓인 순서대로 카드 번호가 주어진다.

출력

인접한 카드 번호 쌍(i, i+1)에 대해 카드 i가 카드 i+1보다 나중에 놓인 경우의 수를 출력한다.

예제

풀이

각 카드 번호가 몇 번째 순서에 놓였는지를 역인덱스 배열로 저장하고, 인접 번호 쌍의 순서를 비교한다.

1. 크기 100001의 배열 arr을 0으로 초기화한다.
2. N개의 카드를 입력받으며 arr[카드번호] = 놓인순서(1-indexed)로 기록한다.
3. 1부터 N-1까지 순회하며 arr[i] > arr[i+1]인 경우(카드 i가 카드 i+1보다 나중에 놓임) ans를 증가시킨다.
4. 최종 ans를 출력한다.

핵심 아이디어: 값→순서 역인덱스를 만들면 인접 값 쌍의 순서 비교를 O(1)에 처리할 수 있다.

코드

import sys
 
input = sys.stdin.readline
 
n = int(input())
 
arr = [0] * 100001
for i in range(n):
    num = int(input())
    arr[num] = i + 1
 
ans = 0
for i in range(1, n):
    if arr[i] > arr[i + 1]:
        ans += 1
 
print(ans)

복잡도

• 시간: O(N) — 입력 처리 O(N) + 비교 순회 O(N)
• 공간: O(N) — 역인덱스 배열 크기 10만