[백준]마법의 돌 장난감
백준 온라인 저지
마법의 돌 장난감
링크 : 문제 바로가기
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));
}
}
}
}
내용을 보면 퀵정렬과 비슷한 느낌이 있다. 전체적인 로직은 다음과 같다.
- for문을 통해 배열에서 왼쪽부터 시작해서 오른쪽으로 간다고 생각하면서 해당 값이 제대로 들어가 있나 확인한다.
ex) 배열의 첫번째에는 1, 두번째에는 2가 들어있나 확인 - 만약 들어가 있지 않다면 그 자리에 있어야 할 값을 그 자리부터 오른쪽으로 가면서 찾음(왼쪽에서 오른쪽으로 가며 정렬중이므로 왼쪽은 이미 정렬된 것으로 가정)
- 1에서 찾은 자리와 2에서 찾은 자리를 시작과 끝으로 하는 배열이라고 생각하고 이 부분을 뒤집어서 본 배열에 적용한다.
- for문을 통한 왼쪽부터 오른쪽 검사 계속 진행…
이 안에서 따로 정렬할 때마다 카운트를 해주고 100회가 넘어갈 시 for문 종료하는 부분 등을 더해주면 완성이다.
알고리즘 : 정렬,구성적