(알고리즘) 백준 25287 java 자바

원종식·2022년 7월 27일

문제

백준 25287 순열정렬 : https://www.acmicpc.net/problem/25287

$1$ 부터 $N$ 까지의 정수를 임의로 배열한 순열은 총 $N! = N\times(N-1)\times(N-2)\times\cdots\times1$ 가지가 있다. 예를 들어 $1$ 부터 $3$ 까지의 수를 임의로 배열한 순열은 $\lbrace1,2,3\rbrace, \lbrace1,3,2\rbrace, \lbrace2,1,3\rbrace, \lbrace2,3,1\rbrace, \lbrace3,1,2\rbrace, \lbrace3,2,1\rbrace$ 로 총 6가지가 있다.
다음과 같은 연산을 원하는 만큼 사용해서 수들이 감소하지 않도록 만들려고 한다. 연산을 수행한 결과는 순열이 아니어도 된다.
$i$ 를 $N-i+1$ 로 바꾼다.
예를 들어, 크기가 $N = 5$ 인 순열 $\lbrace 5,2,3,4,1 \rbrace$ 이 주어졌다고 하자. 첫 번째 원소를 $1(=N-5+1)$ 로 바꾸고, 다섯 번째 원소를 $5(=N-1+1)$ 로 바꾸면 $\lbrace 1,2,3,4,5 \rbrace$ 가 되어 감소하지 않는 수열을 만들 수 있다.
연산을 아무리 많이 사용해도 감소하지 않도록 만들 수 없는 순열이 존재한다. 순열이 주어지면 감소하지 않도록 만들 수 있는지 판별하는 프로그램을 작성하자.

입력

첫째 줄에 테스트케이스의 개수 $T$ 가 주어진다. ( $1 \leq T \leq 50\,000$ )
각 테스트케이스는 두 줄로 구성되어 있다.
테스트케이스의 첫째 줄에 순열의 길이 $N$ 이 주어진다. $(1 \leq N \leq 50\,000)$
테스트케이스의 둘째 줄에 순열을 의미하는 $N$ 개의 수가 공백으로 구분되어 주어진다. 순열은 $1$ 부터 $N$ 까지의 정수가 한 번씩 등장한다.
모든 테스트케이스에서 $N$ 의 합은 $50\,000$ 을 넘지 않는다.

출력

각 테스트케이스마다 주어진 순열을 감소하지 않도록 만들 수 있으면 "YES" , 만들 수 없으면 "NO"를 출력한다.

예제 입력 1

5
1
1
2
2 1
3
2 3 1
5
5 2 3 4 1
5
2 5 3 1 4

예제 출력 1

YES
YES
YES
YES
NO

풀이

해당 문제는 그리디로 풀었다. 각 위치에서 가능한 최소값을 넣어본다.
이때 가능한 최소값을 넣었음에도 이전 값보다 감소하게 될 경우 이는 불가능한 경우로 체크한다. 코드를 통해 이해해보자

코드

import java.io.*;
import java.util.StringTokenizer;

public class Boj25287 {

    public static void main(String[] args) throws IOException {
        BufferedReader bw = new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(bw.readLine());
        StringBuilder ans=new StringBuilder();
        for(int test=0;test<T;test++){
            int n=Integer.parseInt(bw.readLine());
            String put="YES\n";
            StringTokenizer st=new StringTokenizer(bw.readLine());
            if(n==1){//길이가 1이면 무조건 가능
                ans.append(put);
                continue;
            }
            int[] nums=new int[n];
            nums[0]=Integer.parseInt(st.nextToken());
            if(nums[0]>n-nums[0]+1){//0번째 값중 가장 작은 값 넣어 줌
                nums[0]=n-nums[0]+1;
            }
            for(int i=1;i<n;i++){
                nums[i]=Integer.parseInt(st.nextToken());
                int small,big;
                if(nums[i]<n-nums[i]+1){//연산과 비연산 중 작은건 small에 큰건 big에 넣는다
                    small=nums[i];
                    big=n-nums[i]+1;
                }
                else{
                    big=nums[i];
                    small=n-nums[i]+1;
                }
                if(small<nums[i-1]){//만일 small이 이전 값보다 작다면 big으로 해주고 아니면 small로 해준다
                    nums[i]=big;
                }
                else{
                    nums[i]=small;
                }
                if(nums[i]<nums[i-1]){//small이 이전 값보다 크면 당연히 실행되지 않고 만일 작았다면 big이 들어갔다, 
                					  //이때도 작으면 이는 불가능한 경우다.
                    put="NO\n";
                    break;
                }
            }
            ans.append(put);
        }
        System.out.println(ans);
   }
}