[해커랭크] New Year Chaos

Hacker Rank - Interview Preparation Kit

category - [Arrays]

language - [javascript]

 

1. New Year Chaos

www.hackerrank.com/challenges/new-year-chaos/problem

New Year Chaos | HackerRank

 

---

 

[문제 선정의 이유]

쉽게 생각하고 접근했다가 서브미션에서 단 두 개의 테스트 케이스 말고는 다 나가리 먹고 나서 정신 차리고 다시 봤다.

찬찬히 로직을 세우고 나면 구현 자체는 어렵지 않은 문제인데 나처럼 아무 생각없이 포문부터 작성하고 덤벼들다가 금쪽같은 시간을 낭비하지 말자.

 

---

 

[문제 내용]

중요한 포인트만 정리하면

1. 사람들이 줄을 서는데 번호표는 1번부터 하나씩 증가한다. 즉 4명이 줄을 섰다면 1, 2, 3, 4 가 배부된다. 
2. 바로 앞 번호에게 뇌물을 주고 새치기를 할 수 있는데 기회는 한 사람당 2번씩 주어진다.
3. 앞 번호가 미쳐가지고 뒤로 가고 싶다고 뇌물을 주는 경우는 없다.

인풋은 새치기로 엉망이 된 줄이 배열 형태로 주어진다.

아웃풋은 주어진 인풋을 가지고 자리 이동이 몇 번이 일어났는지 출력하면 된다.
이 때 주어진 인풋이 포인트 2번을 어긴 경우(한 놈이 세 번 이상 뇌물을 먹인 경우)는 자리 이동 카운팅을 중단하고 "Too chaotic"(존나엉망!)을 뱉으면 된다.

 

---

 

[문제 해설]

(인풋 배열 q, 인덱스 i)

 

이 문제에서 짚고 넘어갈 것은 두 가지이다.

1. 원래 위치보다 세 칸 이상 앞으로 온 놈이 있다면 "Too chaotic"으로 끝내버리자.
2. q[i]에게 뇌물을 먹인 놈을 찾아서 다 더해버리자. 

1번은 최대 뇌물 회수를 초과한 경우다. 코드로 구현하는 것도 어렵지 않다.

배열의 인덱스는 0부터 시작하지만 번호는 1부터 시작한다. 따라서 현재 위치에 있어야 할 원래 번호는 다음과 같이 나타낼 수 있다.

 

q[i] = i+1;

뇌물을 받아 뒷 번호가 앞으로 오게되는 경우는 다음과 같이 증가하는데

 

q[i] = i+2;  한 칸 뒤에 있던 놈이 온 경우 (뇌물 한 번)
q[i] = i+3;  두 칸 뒤에 있던 놈이 온 경우 (뇌물 두 번)
q[i] = i+4;  세 칸 뒤에 있던 놈이 온 경우 (뇌물 세 번) 허용범위 초과!

.

.

.

따라서 배열 q를 순회하면서 i번째 인덱스의 값이 i+3보다 큰 경우 "Too chaotic"을 출력하고 순회를 중단하면 된다.

if(q[i]>i+3){
    console.log("Too chaotic");
    return;
}

 

 

2번은 다음과 같이 생각하면 도출할 수 있다.

현재 엉망인 배열의 i번째 인덱스의 값 q[i]를 편의상 x라 칭하겠다.

x에게 뇌물을 주지 않고서 x보다 큰 번호가 x의 앞에 갈 수 있는 방법은 없으므로 i보다 작은 인덱스에서 x보다 큰 값을 검출하면 자리를 바꾼 경우로 카운팅이 가능하다.

for(let j=0; j<i; j++){
    if(q[j]>q[i]) cnt++;
}

 

이 때 한 단계 더 나아가 반복문의 범위를 줄여보자.

원래 번호는 인덱스+1의 값이 주어지므로 번호 x에 대하여 x의 원래 인덱스는 x-1이라고 도출 할 수 있다.

그러므로 x에게 뇌물을 주고 앞으로 이동한 번호는 원래 x의 위치인 x-1에 가거나 한 번 더 뇌물을 주고 한 칸 더 이동해 x-2의 위치까지밖에 갈 수 없다. (물론 뇌물을 받는 수에는 제한이 없으므로 x는 원래 위치보다 훨씬 뒤로 가 있을 수 있다.)

 

즉, 지금 x가 어느 위치에 있든 x에게 뇌물을 주고 앞으로 간 번호를 찾을 때 x-2번째 인덱스보다 작은 값은 볼 필요가 없는 것이다.

따라서 반복문의 범위를 x-2와 0 중 더 큰 인덱스부터 시작하도록 조정하면 다음과 같이 고쳐볼 수 있다.

for(let j=Math.max(q[i]-2,0);j<i; j++){
    if(q[j]>q[i]) cnt++;
}

 

이제 인풋 배열 q의 모든 인덱스 i를 순회하며 1번과 2번을 차례로 확인하도록 합쳐주면 최종 식이 나온다.

function minimumBribes(q) {
    let cnt   = 0;
    const len = q.length;
    for(let i=0; i<len; i++){
        if(q[i]>i+3){
            console.log("Too chaotic");
            return;
        }
        for(let j=Math.max(q[i]-2,0); j<i; j++){
            if(q[j]>q[i]) cnt++;
        }
    }
    console.log(cnt);
}

 

이렇게 추석이 다가오는 시기에 새해와 관련 문제를 풀어보았다.

생각을 하고 문제 풀기를 시작하는 습관을 들이자.

 

---