목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q3. 컨셉카 전시
알고리즘 및 자료구조
- 세그먼트 트리
- 스택
- 유니온파인드
힌트
출력 조건상 i번째 차량이 몇 번째에 그룹화되는지 i번째 공백에 출력해야 합니다.
문제
현대모비스는 이번 전시를 위해서 N 종류의 컨셉카를 개발했다. 컨셉카의 종류가 많아 N대의 컨셉카에 1부터 N까지 번호를 매겨 주었다. 때문에 모든 컨셉카의 번호는 서로 다르다.
컨셉카를 사람들에게 보여주기 위해 현대모비스 전시장에 1번부터 N번까지 컨셉카의 번호가 오름차순으로 정렬된 순서로 전시할 생각이다. 하지만, 컨셉카를 옮기는 과정에서 순서가 엉망이 되고 말았다.
전시 담당자인 당신은 다시 1부터 N까지 순서대로 전시하기 위해 컨셉카의 순서를 바꾸려고 한다. 컨셉카를 하나씩 옮겨도 되지만, 아래의 규칙을 만족하면서 컨셉카의 순서를 바꾸려고 한다.
- 인접한 컨셉카의 번호 차이가 2 이하인 연속된 구간을 뒤집어야 한다.
- 맨 처음에 주어진 각 컨셉카를 N개의 그룹으로 구분한다. 그룹은 항상 컨셉카의 번호가 순서대로 정리되어 있어야 한다.
- 서로 인접한 두 개의 그룹을 1번 조건을 만족하면서 컨셉카의 순서를 변경할 수 있다면 하나의 그룹으로 합칠 수 있다.
- 그룹을 합치는 순서는 합칠 수 있는 두 그룹에서 각 그룹의 가장 작은 수, 가장 작은 수가 포함되어 있지 않은 다른 그룹에서 가장 작은 수와 같이 하나의 쌍으로 표현할 때 값이 작은 것부터 그룹으로 합치기 시작한다. 이때, 값이 가장 작다는 것은 쌍 (a, b) 중 가장 작은 a가 있는 쌍을 의미하고 만약 가장 작은 a가 두 개 이상이라면 해당 쌍 중 b 값이 가장 작은 것을 의미한다.
- 이미 합쳐진 그룹은 두 개의 그룹으로 나눌 수 없다.
예를 들어, 1 6 3 4 5 2 7처럼 컨셉카가 전시되어 있다고 가정한다. 이때, 3 4 5는 인접한 수의 차이가 모두 2 이하이므로 5 4 3으로 뒤집을 수 있다.
하지만, 6 3 4 5는 6과 3의 차이가 2보다 크기 때문에 5 4 3 6으로 뒤집을 수 없다. 아래 그림은 뒤집을 수 있는 구간들을 표시한 것이다.
컨셉카를 오름차순으로 정렬하는 과정에서 크기가 1인 그룹에 속한 i번 컨셉카가 몇 번째에 다른 그룹으로 합쳐지는지 알아내고자 한다.
예를 들어, 위와 같이 1 6 3 4 5 2 7처럼 컨셉카가 전시되어 있다고 가정한다면, 그룹을 소괄호 ( )를 이용하여 구분하면 아래와 같다.
(1) (6) (3) (4) (5) (2) (7)
맨 처음에 합쳐지는 두 그룹은 (3) (4)로 그룹을 합치면 (1) (6) (3 4) (5) (2) (7)와 같다. 3번 컨셉카와 4번 컨셉카는 첫 번째에 다른 그룹과 합쳐지는 것을 알 수 있다.
그다음으로 합쳐지는 그룹은 (3 4) (5)이므로 그룹을 합치고 나면 (1) (6) (3 4 5)(2)(7)과 같다. 5번 컨셉카가 두 번째에 다른 그룹과 합쳐지는 것을 알 수 있다.
위에서 설명된 규칙을 만족하면서, 컨셉카의 순서를 바꿀 때 1부터 N까지 컨셉카를 순서대로 전시할 수 있을지 구하시오. 만약 컨셉카를 순서대로 전시할 수 있을 때, 크기가 1인 그룹에 속한 i번째의 컨셉카는 몇 번째에 다른 그룹과 합쳐지는지 구하시오.
