[백준_17298] 오큰수 ( 스택 - 자바스크립트 )

문제

https://www.acmicpc.net/problem/17298

17298번: 오큰수

How to Solve ?

 

[1] 탐색

 

단순히 탐색을 한다고 생각 했을 때는 2중 for loop 을 돌면서 1번째 루프에서 설정한 idx보다 뒤에 있는 문자열을 슬라이스 해서 접근 하는 방식을 취했는데, 시간 초과로 인해 다른 방안을 모색 하게 되었다.

 

[2] 스택

 

스택을 쓴다고 했을 때, 이전의 풀이에서 1 -> N 로 가는 방식을 이용 했기에 뒤의 값들을 스택으로 저장해서 쓴다는 개념이 너무 어색하게 다가 왔었다.

 

그러나 이 문제를 스택답게 풀고자 한다면, 첫번째 루프에서 설정한 "인덱스" 뒤의 값을 보는게 아니라 앞의 값들을 별도의 저장 공간인 스택 배열에 저장해두고 뒤의 값들과 비교하는 방식을 채택하면 더욱 빠른 처리가 가능해진다.

 

아래의 그림에서는 스택에 쌓이는 내용이 이전의 값을 포함 했는데, 실제로는 idx 번호를 스택에 쌓고, 인덱스를 통해 값을 뽑아내어 비교를 진행하였다.

 

그 이유는 값을 통해 인덱스에 접근 하는 경우, 중복이 발생 할 수 있기 때문이다 :)

 

 

 

전체 코드

 

for loop

function solve() {
  for (let i = 0; i < n; i++) {
    const current = nums[i];

    for (let j = stack.length - 1; j >= 0; j--) {
      const tmp = nums[stack[j]];

      if (tmp < current) {
        result[stack.pop()] = current;
      } else {
        break;
      }
    }
    stack.push(i);
  }
  console.log(result);
}

 

 

while 

function solve() {
  for (let i = 0; i < n; i++) {
    const current = nums[i];
	
    // 스택이 존재하고, 이전에 저장 해놓았던 값이 현재보다 작을 때
    // ( 비교 할 내용이 있고, 큰 값 중 첫 번째로 큰 값을 만났을 때 )
    while (stack && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = current;
    }

    stack.push(i);
  }
  console.log(result);
}