BOJ 23158 Array

Problems

BOJ 23158 Array

문제 링크:

문제 내용

0 이상 $10^9$ 이하의 정수로만 이루어진 배열 $a_1, a_2, \cdots, a_n$ 이 있습니다. 여기서 함수 $S(l, r)$ 을 다음과 같이 정의합니다.

$S(l, r) = \{a_l, a_{l+1}, \cdots, a_r\}$ , 즉 $l$ 번째부터 $r$ 번째까지의 원소를 모두 포함하는 집합입니다.

그리고 $b_1, b_2, \cdots, b_n$ 을 다음과 같이 정의합니다.

$b_i$ 는 $S(1, n) = S(i, j) \Leftrightarrow j \ge b_i$ 를 충족하는 1 이상 $n+1$ 이하의 정수입니다.

이러한 $b_i$ 는 단조증가 수열입니다. 즉, 모든 $i$ 에 대해 $b_i \le b_{i+1}$ 이 성립합니다.

수열 $b_1, b_2, \cdots, b_n$ 이 주어질 때, 이 수열을 만들 수 있는 입력 배열 $a_1, a_2, \cdots, a_n$ 이 존재한다면 그러한 배열을 아무거나 하나 출력하세요.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$ 가 주어집니다. ( $1 \le T \le 60\;000$ )

각 테스트 케이스에 대해, 첫 번째 줄에 수열의 길이 $n$ 이 주어집니다. ( $1 \le n \le 200\;000$ )

다음 줄에는 $b_1, b_2, \cdots, b_n$ 이 순서대로 주어집니다. ( $1 \le b_1 \le b_2 \le \cdots \le b_n \le n + 1$ )

하나의 테스트 파일에서 $n$ 의 총합은 $2\;600\;000$ 이하입니다.

출력

각 테스트 케이스에 대해, 주어진 수열 $b_i$ 에 대응되는 배열 $a_i$ 가 존재한다면, 그러한 $a_1, a_2, \cdots, a_n$ 을 순서대로 한 줄에 출력합니다. 존재하지 않는다면 -1을 대신 출력합니다.

문제 풀이

스포일러

하나의 $b_i$ 의 값은 아래의 두 가지 정보를 포함합니다.

$S(i, b_i) = S(1, n)$ (단, $b_i = n+1$ 일 경우 제외)
$S(i, b_i - 1) \neq S(1, n)$

예를 들어, [5, 8, 8, 8, 10, 10, 11, 11, 11, 11]은 다음과 같이 표현할 수 있습니다.

1 2 3 4 5 6 7 8 9 A
a a a a x
  a a a a a a x
    a a a a a x
      a a a a x
        a a a a a x
          a a a a x
            a a a a

이 그림의 각 줄은 a부터 x까지의 구간은 $S(1, n)$ 과 같고, a만을 포함하는 구간은 $S(1, n)$ 에서 하나(x)가 빠져있다는 의미가 됩니다. 이로부터, 한 줄의 x는 그 줄의 모든 a와 다르다는 것을 알 수 있습니다. 같은 x 위치를 공유하는 경우, 이 조건은 가장 긴 범위를 갖는 줄만 고려하면 됩니다.

$b_i \le n$ 인 줄 중에서 가장 짧은 줄의 길이를 $k$ 라고 합시다. 그러면 $a_1, a_2, \cdots, a_n$ 은 $k$ 종류를 초과하는 값을 가질 수 없습니다. 편의상 배열 $a_i$ 에 등장하는 수들을 $1, 2, \cdots, k$ 로 둡니다. 실제로 답이 존재하는 경우에는 $k$ 종류의 수가 모두 등장하는 배열을 만들 수 있지만, 이유는 아직 모릅니다.

또한, $b_i = n+1$ 인 줄에 대해서는 $n+1$ 번째 자리에 더미 x를 하나 추가하여 그 줄의 a들 역시 x와 다르다는 조건을 줄 수 있습니다. 그러면 위 그림은 아래와 같이 바뀝니다.

1 2 3 4 5 6 7 8 9 A B
a a a a x
  a a a a a a x
        a a a a a x
            a a a a x

이제 두번째 줄과 세번째 줄을 보면, 두번째 줄의 마지막 a a a a x는 1부터 $k$ 까지를 포함해야 하는데, 그 중 맨 앞을 제외한 a a a x는 아래 줄의 a a a a ...의 일부이기 때문에 세번째 줄의 x와 같을 수 없습니다. 따라서 $a_4$ 는 $a_{10}$ 과 같아야 합니다.

1 2 3 4 5 6 7 8 9 A B
b a a a x
  a a b a a a x
        a b a a a x
            a a a a x

여기서 $i$ 번째 줄의 b는 $i+1$ 번째 줄의 x와 같은 값을 가지며, 또한 각각의 b a a .. a x 구간은 1부터 $k$ 까지를 모두 포함해야 하는 최소의 구간들이 됩니다.

이제 다음과 같은 그리디적인 접근을 구상할 수 있습니다.

맨 오른쪽 ( $n+1$ 번째 값)부터 시작하여 오른쪽에서 왼쪽 순으로 칸을 채워 봅니다.
$i$ $i$ 번째 칸을 채울 때는 다음의 두 가지 정보를 고려합니다.
- $i$ 를 포함하는 구간들에 해당하는 x의 목록 $X$ : 절대 $i$ 번째 칸에 올 수 없는 값들
- 현재 $i$ 를 포함하는 b ... x 구간에서 아직 없는 값의 목록 $W$
$i$ 가 현재 고려 중인 b ... x의 오른쪽에 있거나 모든 그러한 구간이 이미 충족되었다면, $X$ 에 없는 값을 아무거나 하나 넣습니다. 이것이 불가능하다면 -1을 출력하고 종료합니다.
$i$ $i$ 가 현재 고려 중인 b ... x의 내부에 있다면, $W$ $W$ 에 있는 값을 아무거나 하나 넣습니다. $W$ $W$ 가 비었다면 당장 $i$ $i$ 번째 칸을 채우지 않고, 이전 줄의 b ... x로 넘어가서 재시도합니다.
- 여기서 $W$ 에 있는 값은 모두 $X$ 에 없음을 보일 수 있습니다.
어떤 칸에 값을 썼을 때 이 칸이 x가 있는 칸이면, 그 칸에 대응되는 b에 같은 값을 적습니다. 여기가 또 x 칸이면, 다음 b에 다시 같은 값을 적는 것을 반복합니다. 그리고 이에 맞춰서 $X$ 와 $W$ 를 잘 업데이트합니다.

$X$ 와 $W$ 를 구현할 때, 구간의 각 수의 개수를 세는데는 벡터를 쓰고, 개수가 0인 값의 목록을 유지하는데는 트리셋을 쓰는 것이 좋습니다. 해시셋에서 원소를 하나 꺼내는 것은 TLE, 트리셋에서 꺼내는 것은 AC인 경우가 있습니다.

Last updated on 2026년 3월 25일 14:11:23

BOJ 23091 Calculate! 3 BOJ 2320 끝말잇기