백준 온라인 저지

마법의 돌 장난감

링크 : 문제 바로가기

import java.util.*;


public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int[] toys = new int[n + 1];
		toys[0] = 0; // 인덱스와 해당값을 같게 해주는 편의를 위해 0삽입
		int count=0;
		ArrayList<String> result=new ArrayList<String>();

		for (int i = 1; n >= i; i++) {
			int toy = input.nextInt();
			toys[i] = toy;
		} // 입력된 장난감 순서 배열 완성

		for (int i = 1; i <= n; i++) { // 총 n번 돌리기( i : 1,2,...,n )
			if (toys[i] != i) {
				int startIndex = i;
				int endIndex = 0;

				for (int j = i + 1; j <= n; j++) {
					if (toys[j] == i) {
						endIndex = j;
					}
				}
//				System.out.println(Arrays.toString(toys));
//				System.out.println("바꿔야할인덱스 : "+startIndex+" "+endIndex);
				count+=1;
				if (count>100) {
					break;
				}
				result.add(Integer.toString(startIndex));
				result.add(Integer.toString(endIndex));
				
				int[] sliceBefore = Arrays.copyOfRange(toys, startIndex, endIndex + 1); // 정렬해야할 부분배열 설정
				int sliceLength = sliceBefore.length;
				int[] sliceAfter = new int[sliceLength];

				for (int j = 0; j < sliceLength; j++) {
					sliceAfter[sliceLength - 1 - j] = sliceBefore[j];
				} // 부분배열 정렬
//				System.out.println(Arrays.toString(sliceBefore));
//				System.out.println(Arrays.toString(sliceAfter));
				
				System.arraycopy(sliceAfter, 0, toys, startIndex, sliceLength);
//				System.out.println(Arrays.toString(toys));

			}
			
		}
//		System.out.println(Arrays.toString(toys));
		
		if(count>100) {
			System.out.println(-1);
		}else {
			System.out.println(count);
			for(int j=0;j<count;j++) {
				System.out.println(result.get(2*j)+" "+result.get(2*j+1));
		}
		
		
			
		}
		
		
		
	}
}

내용을 보면 퀵정렬과 비슷한 느낌이 있다. 전체적인 로직은 다음과 같다.
1. for문을 통해 배열에서 왼쪽부터 시작해서 오른쪽으로 간다고 생각하면서 해당 값이 제대로 들어가 있나 확인한다.
ex) 배열의 첫번째에는 1, 두번째에는 2가 들어있나 확인
2. 만약 들어가 있지 않다면 그 자리에 있어야 할 값을 그 자리부터 오른쪽으로 가면서 찾음(왼쪽에서 오른쪽으로 가며 정렬중이므로 왼쪽은 이미 정렬된 것으로 가정)
3. 1에서 찾은 자리와 2에서 찾은 자리를 시작과 끝으로 하는 배열이라고 생각하고 이 부분을 뒤집어서 본 배열에 적용한다.
4. for문을 통한 왼쪽부터 오른쪽 검사 계속 진행...

이 안에서 따로 정렬할 때마다 카운트를 해주고 100회가 넘어갈 시 for문 종료하는 부분 등을 더해주면 완성이다.

알고리즘 : 정렬,구성적