[Nodejs]1874번: 스택 수열

처음에 문제를 예시까지 싹 읽고 든 생각은

먼 개소리야?(넝담ㅎ)

 

힌트를 보고서야 무슨 말인지 이해할 수 있었다.

1234567...n 까지의 오름차순의 수들을 스택에 push하는 것까지는 변하지 않는 고정된 상황.

여기서 pop하는 숫자들을 순차적으로기록해서 주어진 수열을 만족할 수 있냐는 소리였다.

 

43687521의 경우, 1234 push(++++) 4 pop(-) 3 pop(-) 56 push(++) 6 pop(-) 78 push(++) 87521 pop(-----) 이므로 조건을 만족한다.

12534의 경우 1 push(+) 1 pop(-) 2 push(+) 2 pop(-) 345 push(+++) 5 pop(-) 이후 무조건 4 pop만 가능하기에 조건을 만족하지 못한다.

 

12345...n까지의 값을 stack에 push한다고 하면, stack의 특성 상 n까지 push한 뒤로는 pop만 가능하다.

여기서 파악한 규칙성은

1. Max 이후의 값 :
      내림차순이다.
2. Max 이전의 값 :
      이전값보다 작은 수의 경우, 해당 값이 되기 전에 사이에 있는 값들이 이전에 pop되었다.
or   없다. (ex. 87654321)

이었다.

 

이를 통해, 먼저 해당 수열이 push pop 연산으로 만들어질 수 있는가를 선판단 한 후,

아니라면 NO 출력 후 end

맞다면 연산을 하면 된다.

 

그렇다면 push pop을 빠르게 계산하기 위한 규칙성은 없을까?

max값 이전의 값들은 규칙성을 확인할 수 있었는데,

 

43687521의 예시를 다시 끌어와보겠다.

여기서 max값을 포함한 앞의 값은 4368이다.

1부터 순차적으로 push하는 것을 고려하면, 4는 최소 push 4번을 강제한다.

+ + + + -

이후 값은 감소한다면, pop 한번.

-

이후 값이 증가한다면, 이전값(3)에서 해당값까지 push... 뭐 이런식으로 값 비교후, 차잇값만큼 +를 써주고 - 써주고...

---

문제 파악은 끝난 것 같아 코드를 작성해보았다.

function solution(inputArray){
  let count = +inputArray[0]; //count===max
  let resultlog = [];
  inputArray.splice(0, 1);

  var maxIndex = inputArray.indexOf(count);

  for(let i = 0, previousMax = 0; i < count; i++) {
    if(i === 0) { //  *** i 처음일 때 ***
      for(let j = 0; j < inputArray[i]; j++) {
        resultlog.push('+');
      }
      previousMax = inputArray[i];
      resultlog.push('-');
      continue;
    } else if(i <= maxIndex) { //  *** max 이전 값일 때 ***
      if(inputArray[i] < inputArray[i-1]) { // ** 값이 감소했을 때 **
        for(let j = inputArray[i]+1; j < inputArray[i-1]; j++) {
          if(inputArray.indexOf(j) < i) { //  * 사잇값들이 이전에 pop되었다 : O

          }else { //  * 사잇값 중 이전에 pop되지 않은 것이 있다 : X
            resultlog.push('NO');
            break;  //for문을 한 번 더 break해야 함.
          }
        }

        if(resultlog[resultlog.length-1] === 'NO') {
          break;
        } else {
          resultlog.push('-');
        }
      }else { //  ** 값이 증가했을 때 **
        for(let j = previousMax; j < inputArray[i]; j++) {
          resultlog.push('+');
        }
        resultlog.push('-');
      }
    } else if(i > maxIndex) { //  *** max 이후 값일 때 ***
      if(inputArray[i-1] < inputArray[i]) { //  **  값이 증가했을 때 : X **
        resultlog.push('NO');
        break;
      } else {  //  **  값이 감소했을 때 : O **
        resultlog.push('-');
      }
    }
    if(previousMax < inputArray[i]) {
      previousMax = inputArray[i];
    }
  }
  if(resultlog[resultlog.length-1] === 'NO') {
    console.log('NO');
  } else {
    console.log(resultlog.join('\n'));
  }
}

그냥 조건 검색도 하면서, 로그 수정도 하도록 했다.

그치만..

어카지..

검색해보니까 나처럼 문제를 접근한 사람은 거의 없는 것 같았다...

대부분이 직접 스택에 넣고 거기서 오류가 나면 NO를 반환하는 코드를 짠 것 같았음...

나도 그렇게 짜야하나 고민했는데, 짜놓은 거 아깝기도 해서 일단 시간을 잡아먹는 요소를 찾아 해결해보려고 했다.

 

        for(let j = inputArray[i]+1; j < inputArray[i-1]; j++) {
          if(inputArray.indexOf(j) < i) { //  * 사잇값들이 이전에 pop되었다 : O

나는 여기서 indexOf가 시간을 오지게 잡아먹으리라 생각했다.

왜냐면 저 함수 자체로도 아마 수열 전체를 순회하며 돌테고,

사실상 내가 검사해야 하는 부분은 맨 앞부터 i 이전까지만임에도 불구하고 다 검사를 하고있을테니까

 

아쉽게도 정해진 index까지만 검사하는 방법은 없었지만, 반대로 정해진 index부터 검사를 시작할 수는 있었다.

그리고 뒤부터 검사하는 lastIndexOf 라는 함수를 발견했다. 역시 정해진 인덱스부터 역순으로 검사가 가능하다.

그러면 lastIndexOf에 i-1 index를 넣어주면 내가 원하는 범위만 검사를 하지 않겠는가?

        for(let j = inputArray[i]+1; j < inputArray[i-1]; j++) {
          let index = inputArray.lastIndexOf(j, i-1);
          if(index < i && index > -1) { //  * 사잇값들이 이전에 pop되었다 : O

          }else { //  * 사잇값 중 이전에 pop되지 않은 것이 있다 : X
            resultlog.push('NO');
            break;  //for문을 한 번 더 break해야 함.
          }
        }

lastIndexOf로 바꿔서 다시 코드를 돌렸다.

(저 if else 문이 흉측하고 비효율적이긴 한데... 일단 수정은 안했다... 당시엔 코드 돌아가는게 더 중요했고 변수를 만들고 싶지 않았음. if문의 조건을 뒤집고 else문 내부 코드를 if문으로 옮겨주고 else를 지우면 되겠쬬...?)

바로 해결됨... wow.....

 

그치만 다른 Nodejs 이용자 채점 현황을 보니 시간이 200-300ms에서 끝나는 코드들이 절반가량 되었다.

아마 앞서 언급한 방식으로 구현하면 시간이 많이 단축되는 게 아닐까...?

시간 될 때, 저 스택 직접 구현 방식으로 구현해봐야겠다.