Larry's Array

사이트: HackerRank
난이도: 미디움
분류: Sorting

문제

순차적으로 정렬될 수 있는 배열 A가 주어졌을 때, 정해진 수의 원소들을 rotate하여 정렬가능한지 판단한 후 YES or NO를 반환하라. 이 때 rotate 가능한 원소의 개수는 3개이다.

A				rotate 
[1,6,5,2,4,3]	[6,5,2]
[1,5,2,6,4,3]	[5,2,6]
[1,2,6,5,4,3]	[5,4,3]
[1,2,6,3,5,4]	[6,3,5]
[1,2,3,5,6,4]	[5,6,4]
[1,2,3,4,5,6]

YES

1. 나의 풀이

문제에서 주어진 변수의 범위가 아래와 같이 작아서 n^2 정도의 시간복잡도를 가져도 괜찮다고 생각하였다. 아래 n은 배열의 길이이다.

3 <= n <= 1000
1 <= A[i] <= n

function larrysArray(A) {
    // Write your code here
    // 이전(i > x) 원소들은 이미 정렬되어 찾을 필요 없기 때문에 start부터 탐색하도록 하였다.
    const findIndex = (arr, start, condition) => {
        for (let i = start; i < arr.length; i++) {
            if (condition(arr[i], i)) {
                return i;
            }
        }
    }
    
    for (let i = 1; i <= A.length; i++) {
        let index = -1;

      	// 현재 위치의 값이 현재 순서이지 않을 경우 루프 실행
        while(A[i - 1] !== i) {
            if (index === -1) {
                // 현재 순서의 인덱스를 찾는다.
                index = findIndex(A, i, a => a === i);
                // 만약 끝 인덱스인데 마지막 순서가 아닐 경우 NO를 반환한다.
                if (i === A.length && index !== A.length - 1) {
                    return 'NO';
                }
            }
            
            // 구조분해할당을 통해 rotate 한다.
            if (index === A.length - 1) {
                // last item
                [A[index - 2], A[index - 1], A[index]] = [
                    A[index - 1], A[index], A[index - 2]
                ];

            } else {
                [A[index - 1], A[index], A[index + 1]] = [
                    A[index], A[index + 1], A[index - 1]
                ];
            }
            
            // 다음 index 설정
            index = index - 1;
        }
    }
    
    return 'YES';
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.