Almost Sorted

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

문제

배열이 주어졌을 때 해당 배열의 상태에 따라 아래와 같이 출력한다.

1. 이미 정렬된 경우

yes

2. 두 요소의 순서만 뒤바뀐 경우

yes
// 두 요소의 순서를 출력한다.
swap 1 5

3. 정렬되지 않은 요소들의 범위를 뒤집으면 올바르게 정렬될 경우

yes
// 뒤집을 범위의 첫 번째 순서와 마지막 순서를 출력한다.
reverse 2 4

4. 모두 해당 하지 않을 경우

no

여기서의 순서는 인덱스 + 1 값이다.

1. 나의 풀이

애매하게 시간이 지체되는 것 같아서 중간에 다른 사람의 풀이를 참조하였다.

2. 다른사람의 풀이

function almostSorted(arr) {
    // 주어진 배열의 정렬 값을 계산한다.
    const sorted = [...arr].sort((v1, v2) => v1 - v2);
    let faults = [], faultsIdx = [];
    
    arr.forEach((e, i) => {
      	// 배열을 순회하여 정렬되지 않은 요소가 있는지 확인한다.
        if (e !== sorted[i]) {
          	// 정렬되지 않은 요소가 나올 경우 그 값과 순서를 담아둔다.
            faults.push(e);
            faultsIdx.push(i + 1);
        }
    });
    
   	// 우선적으로 이미 정렬된 경우였는지 확인한다.
    if (!faults.length) {
        console.log('yes');
        return;
    }
    
  	// reverse 여부를 확인하기 위해 잘못된 요소들의 정렬값을 내림차순으로 정렬한다.
    const corrects = [...faults].sort((v1, v2) => v2 - v1);

    if (faults.length === 2) {
      	// faults의 길이가 2일 경우 swap이다.
        console.log(`yes\nswap ${faultsIdx[0]} ${faultsIdx[faultsIdx.length - 1]}`);

    } else if (corrects.every((c, i) => c === faults[i])) {
      	// 내림차순 정렬된 배열과 faults의 요소들이 일치하면 reverse이다.
        console.log(`yes\nreverse ${faultsIdx[0]} ${faultsIdx[faultsIdx.length - 1]}`);

    } else {
     	// 아닐 경우 no를 반환한다.
        console.log('no');
    }
}

회고

문제 자체는 어렵지 않았지만, 조건의 우선순위를 빨리 결정하는 것이 좋을 것 같다는 생각이 들었다. 시간을 충분히 들이지 않아도 문제의 키 포인트를 빨리 찾으면 풀이 시간을 단축할 수 있기 때문이다. 여러 문제들을 더 풀어보면서 숙련도를 올려야겠다.