안녕하세요,
재재입니다.
BOJ 2413 비슷한 순열 문제에 대한 풀이입니다.
BOJ 2413 비슷한 순열
(1) 문제 설명
분류 : 구현, bruteforce
출처 : https://www.acmicpc.net/problem/2413
(50,000 이하) N개의 순열이 주어집니다.
순열이 비슷하다는 것은, 순열의 각 위치의 수의 차이가 1 이하인 경우를 말하는데,
주어진 순열을 이용해 만든 비슷한 순열 중 가장 작은 값을 출력해주면 됩니다.
(단, 순열의 크기 비교는 가장 앞의 수부터 시작한다.)
(2) 풀이 도출
앞에서 가능한 기존의 수보다 하나 작은 수를 써야 이득이다.
따라서, 해당 위치의 숫자를 하나 낮출 수 있는지 없는 지를 봐야 한다.
단, 모든 경우를 해 보는 것은 $$ O(3^n) $$ or $$ O(n!) $$ 이기 때문에 신중해야합니다.
여기서 필요한 것은, 해당 숫자가 있는 원래의 위치 배열인데요.
그리고, 현재의 수보다 하나 작은 수의 위치를 염두 하며,
해당 위치의 숫자를 고정 시켜야 하는 지에 대한 정보가 필요합니다
이를 구현하면 전체 시간 복잡도 $$ O(n) $$ 에 해결 가능합니다.
(단, 숫자 1을 주의해야 하는데 0은 없기 때문에 별도의 처리가 필요합니다.)
(3) 정답 코드
BOJ 2413 비슷한 순열