HackerRank 문제풀이 - 7 (New Year Chaos)

1. 문제

• 임의의 배열이 주어진다.
  • 배열 내의 숫자들은 오름차순으로 정렬되어 있어야 하지만, 일부 숫자들이 이 정렬의 규칙을 어기고 자리가 이동되어있다.
    • 자기보다 작은 숫자로 이동할 수 있으며 이동하면 자연스레 작은숫자들은 뒤로 밀리게 된다.
      • 만일, 본래의 자리에서 2를 초과한 만큼 벗어난 숫자가 있으면 "Too chaotic" 를 출력하고,
      • 아니라면 각 숫자들이 자기 자리로 돌아가기 위해 몇번의 swap을 거쳐야 하는지 해당 수를 출력해야 한다.

 

 

2. 1차 문제풀이

2.1 풀이 과정

function processOrderSwap(q, lastSwapedNum){
    let swapedNum = lastSwapedNum;
    //console.log(`processOrderSwap >> q: ${q}`);
    
    if(q != null && typeof q != "undefined" && q.length > 0){
        let orgQ = [...q];
        for(let i = 0; i < q.length; i++){
            if(i+1 < q.length){
                if(q[i] > q[i+1]){
                    let temp = q[i];
                    q[i] = q[i+1];
                    q[i+1] = temp;
                    
                    swapedNum++;
                }
            }
        }
        
        if(JSON.stringify(q) != JSON.stringify(orgQ)){
            swapedNum = processOrderSwap(q, swapedNum);
        }
    }
    
    return swapedNum;    
}

function processBribedNum(q){    
    let bribedNum = 0;
    let swapedIndice = [];
    
    for(let i = 0; i < q.length; i++){
        const currentNum = q[i];
        const correctNum = i + 1;
        
        if(currentNum > correctNum){
            const gap = currentNum - correctNum;
            swapedIndice.push(currentNum);
            
            //console.log(`currentNum: ${currentNum}, gap: ${gap}`);
                    
            if(gap > 2) {
                return "Too chaotic"; 
            } else {
                bribedNum += gap;
            }
        }
    }
    
    let notSwapedQ = [];
    for(let i = 0; i < q.length; i++){
        if(swapedIndice.indexOf(q[i]) == -1){
            notSwapedQ.push(q[i]);
        }
    }
    // console.log(`notSwapedQ: ${notSwapedQ}`);
    
    const additinalSwaped = processOrderSwap(notSwapedQ, 0);
    // console.log(`additinalSwaped: ${additinalSwaped}`);
    
    return bribedNum + additinalSwaped;
}

function minimumBribes(q) {
    // Write your code here
    
    const res = processBribedNum(q);
    console.log(res);
}

풀이 과정은 다음과 같다.

• 배열의 길이만큼 for문을 돈다.
  • 만약 요소가 올바른 위치에 있지 않다면
    • 현재 위치의 인덱스와 원래 있어야할 위치의 인덱스를 구한다.
      • 해당 인덱스의 차를 구한다.
        • 만일 해당 값이 2가 넘는다면 "Too chaotic"를 출력하게 한다. (종료)
        • 아니라면, 해당 값을 총교체횟수(swapedIndice) 변수에 더한다.
• 교체(swap)되지 않았던 요소들을 모아서 배열에 담는다
  • 해당 배열내 요소들의 정렬을 2차로 검사하는 재귀함수(processOrderSwap)으로 넘긴다.
    • 배열 내의 요소들이 오름차순으로 되어있지 않다면, 하나씩 인접한 인덱스끼리 교체(swap)을 해준다.
      • 요소들의 변동이 없을때까지 재귀를 수행한다.
  • 1차로 검사한 총교체횟수(swapedIndice)와 2차 정렬 검사 함수에서 리턴된 값(addiitinalSwaped)을 더하여 출력한다.

 

 

2.2 풀이 결과

이런.. 10만개에 가까운 요소를 담은 배열에서 Time limit가 떴다.

 

아무래도 2차 정렬 검사 함수에서 정렬이 완료될때까지 계속 재귀를 도는 과정이 효율적으로 처리되지 않던것 원인이라 판단하여 로직을 개선하게 되었다.

 

 

 

 

3. 2차 문제풀이

3.1 풀이 과정

function swapTwoElements(arr, i, j){
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function processBribedNumNew(q){    
    let bribedNum = 0;
    
    for(let i = q.length -1; i >= 0; i--){
        let currentNum = q[i];
        const correctNum = i + 1;
        
        
        while(currentNum < correctNum){
            const correctNumIdx = q.indexOf(correctNum);
            const gap = i - correctNumIdx;
            
            //console.log(`i=${i}, currentNum=${currentNum}, correctNum=${correctNum}, gap=${gap}`);
            //console.log(q);
            if(gap > 2) {
                return "Too chaotic";
            } else {
                bribedNum += gap;
                
                for(let j = 0; j < gap; j++){
                    swapTwoElements(q, correctNumIdx+j, correctNumIdx+j+1);
                }
            }
            
            currentNum = q[i];
        }
    }
    
    return bribedNum;
}

function minimumBribes(q) {
    // Write your code here
    
    const res = processBribedNumNew(q);
    console.log(res);
}

1차 풀이때보다 소스가 제법 줄어들었는데, 풀이과정은 다음과 같다.

• 배열의 요소들을 index가 가장 큰 요소부터 index가 0인 요소까지 for문을 돈다.
  • 만약 현재 위치에 알맞지 않은 수가 있을 경우, 알맞은 숫자가 몇번째 인덱스에 있는지 구한다. (indexOf 내장함수 사용)
    • 현재 인덱스와 해당 수의 인덱스(correctNumIdx)의 차를 구한다.
      • 만일 그 차가 2를 초과할 경우, "Too chaotic"을 출력한다.(종료)
      • 아니라면, 총교체횟수(bribedNum)에 해당 값을 더한다.
        • 해당 요소에 알맞은 숫자가 해당 요소까지 오도록 반복해서 swap을 실행한다.
• 반복문이 종료되면, 총교체횟수(bribedNum) 값을 출력한다.

 

3.2 풀이 결과

 

로직이 그래도 일부 개선되어서 그런지 위에서 실패하였던 Test case6은 통과하게 되었다.

 

그런데 10만개의 요소가 넘는 배열을 약 10초간의 시간 내에 연산이 되게끔 하려면 어떤 방식으로 더 개선해야할지..

오늘은 시간이 늦었으니 다음에 다시 풀어보기로 해야겠다.

 

 

 

 

4. 3차 문제풀이

4.1 풀이 과정

사실 4차 풀이과정이다. 3차풀이과정은 setTimeout 함수를 사용해서

비동기로 주어진 배열의 탐색 위치를 각각 나누어주어 연산을 수행하게 하였는데..

 

결국에는 각각 역할배분을 하였어도, 연산 시기에 따라 잘못된 요소의 값이 들어있는 채로 연산을하니

당연하게도 오답을 내놓게 되었다.

 

그래서 처음부터 접근이 잘못되었다 생각하여, 최종으로 로직을 다시 짜게 되었다.

function minimumBribes(q) {
    // Write your code here
    let bribedNum = 0
    for(let i=q.length-1; i>=0; i--) {
        const correctNum = i + 1;
        
        if(q[i]-correctNum>2) {
            console.log("Too chaotic");
            return;
        } else {
            for(let j=q[i]-2;j<i;j++){
                if(q[j]>q[i]) bribedNum++
            }
            
        }
    }
    
    console.log(bribedNum);
}

풀이 방법은 다음과 같다.

• 주어진 배열의 길이만큼 for문을 돈다. (배열의 끝부분부터 시작)
  • 만일 탐색하는 인덱스에 알맞는 수보다 2를 초과하면 "Too chaotic"을 출력한다.(종료)
  • 아니라면, 탐색하는 위치의 앞과 그 앞 수를 확인하여 현재 값보다 큰지 검사한다.
    • 크다면, 해당 값은 이동을 해야 하므로 이동횟수(bribedNum)를 1 더한다.
• 반복문이 끝나면, 모두 더한 이동횟수(bribedNum)값을 출력한다.(종료)

 

 

 

4.2 풀이 결과

휴.. 어느때보다 보기 힘들었던 녹색 간판이었다.

 

확실히 한 챕터를 풀어가다보니 점점 난이도가 어려운 문제들을 접하게 되어

더 높은 수준의 로직이 요구되어 많은 시간을 할애하게 된 것 같다.

 

특히나 쉽게 생각할 수 있는 문제를 방향을 잘못잡으면 굉장히 되돌아가는걸 느끼며

이렇게 여러가지 문제를 마주하고 풀어봐야 또 좋은 경험과 공부 삼을수 있으니

틈틈히 코딩테스트문제를 푸는 습관을 들여야겠다.