백준 20309 - 트리플 소트

Java

20309 번 - 트리플 소트

문제

알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 “트리플 소트”는 다음과 같이 동작한다.

• 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.
• 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 이면 뒤집은 뒤에는 가 된다.
• 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.
  하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. 부터 까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오
  문제 출처

접근 방법

주목 해야할 것은 1부터 N까지 정수가 차례대로 입력된다는 것이다.
또한 연속된 정수 [a, b, c]가 있으면 정렬은 a와 c만 변경되며 이는 인덱스가 1,3,5,7…인 홀수 번째에 있는 수는 홀수 번째에만 변경이 가능하고 역으로 짝수번째에 있는 수는 짝수 번째에 있는 수 끼리만 변경이된다.
위 2개의 조건으로 홀수 번째에 홀수만 오고, 짝수 번째에 짝수만 오면 트리플 소트가 가능하다.

구현

각 인덱스와 해당 인덱스의 값이 함께 짝수 혹은 홀수가 아니면 중단하여 트리플 sort 불가능하다고 출력한다.

코드

/*
20309번 - 트리플 소트
https://www.acmicpc.net/problem/20309
*/

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int n = Integer.parseInt(br.readLine());
    	int[] arr = new int[n+1];
    	boolean isSort = true;
    	StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
    	//System.out.println(Arrays.toString(arr));
		// 각 인덱스와 값이 동시에 짝수이거나 홀수인지 판별
    	for(int i = 1; i <= n; i++) {
    		if(arr[i] % 2 != 1 && i % 2 == 1) {			//홀수 인덱스에 짝수가 오면 종료한다.
    			isSort = false;
				break;
    		}
    		else if(arr[i] % 2 != 0 && i % 2 == 0) {	//짝수 인덱스에 홀수가 오면 종료한다. 
    			isSort = false;
				break;
    		}
    	}
    	
    	if(isSort) {
    		System.out.println("YES");
    	}else {
    		System.out.println("NO");
    	}
    	
    	br.close();
    }
}

총평

난이도

⭐★★★★

후기

해결방법이 눈에 바로 보인문제

개선할 점

없