[JS][백준]2493_탑

문제 번호

2493번: 탑

 

 

알고리즘 분류

• 자료 구조
• 스택

 

문제 풀이

 문제를 읽어보면 i번째 타워에서 왼쪽으로 검색해서 가장 먼저 만나는 i번째 타워의 높이보다 크거나 같은 타워를 찾으면 된다.

 근데 i번째 타워마다 매번 검색을 하기엔 500,000개의 타워를 검색해야 하기 때문에 시간 초과에 걸릴 것이라 생각했다. 그렇다면 어떻게 빠르게 검색을 할것인가에 대해서 고민했다. 처음에는 높이 순으로 이분 탐색을 진행하려 하였으나 타워들의 높이가 정렬된 순서가 아니니 불가능했다. 

 우리는 가장 먼저 만나는 타워의 위치만 알면된다. 여기까지 생각하니까 가장 위에 있는 자료를 먼저 사용하는 stack을 활용해보아야겠다는 생각이 들었다. 단 방향 탐색이고 조건에 따라서 pop / push를 진행하면 되겠거니 싶었다.

 

 스택은 가장 높은 타워가 가장아래, 가장 낮은 높이가 top에 있는 모양새가 될 것이다.

일단 i번째 타워를 살펴볼때 2가지 경우의 수가 있다고 생각한다. 스택의 top에 있는 타워의 높이보다 1. 높을 때, 2. 낮을 때.

 

1. 스택의 top보다 i번쨰 높이가 더 높으면 스택의  top이 i번째 높이보다 같거나 커질 때까지 스택을 pop 해준다. 해당 과정을 통해서 나보다 왼쪽에 있으면서 최초로 만나는 나보다 크거나 같은 타워를 알 수 있다. i-n번째에 있는 i번째보다 작은 타워들은 i+n번째 타워들이 만날 수 없다.(i-n >=1 && i+n <= N. n은 자연수) 그러니 pop 해주는 것이다.(문제풀이에 필요가 없기 때문에) 

      while (s.length > 0 && s[s.length - 1].h < tower[i]) {
        s.pop();
      }

 

2. 스택의 top보다 i번째 타워의 높이가 낮으면 스택에 push 해주면 된다. 

      s.push({
        no: i + 1,
        h: tower[i],
      })

 손으로 몇 번 써보다보면 이해하기 쉽다.

 

 

 전체 코드

/**
 * 왼쪽에 있는애들중에 최초로 만나는 나보다 크거나 같은애.
 *  3. 
 * 1. 스택의 top보다 i번째 높이가 더 높으면 스택을 pop하고(스택의 top이 i번째 높이보다 같거나 커질때 까지) 스택에 push 하고 answer에 0을 추가한다.
 * 2. 스택의 top보다 i번쨰 높이가 낮으면 answer에 스택의 top이 있는 위치를 추가하고 스택에 push 한다.
 */
function main() {
  let answer = '';
  const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
  const N = +input[0];
  let tower = input[1].split(' ').map(Number);
  let s = [];

  for (let i = 0; i < tower.length; i++) {
    if (s.length == 0) { // 처음.
      s.push({
        no: i + 1,
        h: tower[i],
      });
      answer += 0 + ' ';
    }
    else if (s.length > 0 && tower[i] > s[s.length - 1].h) {
      while (s.length > 0 && s[s.length - 1].h < tower[i]) {
        s.pop();
      }
      if (s.length == 0)
        answer += 0 + ' ';
      else
        answer += s[s.length - 1].no + ' ';

      s.push({
        no: i + 1,
        h: tower[i],
      });
    } else { // i번째가 더 낮을경우.
      answer += s[s.length - 1].no + ' ';
      s.push({
        no: i + 1,
        h: tower[i],
      })
    }
  }

  return console.log(answer.trim())
}
main();

 

 

 

특이사항

 스택을 활용해야 하는 것만 잘 떠올리면 어렵지 않았다. 스택을 활용하는 문제는 while문을 활용해서 특정 조건을 만족할 때까지 pop / push를 하는 방법으로 많이 나오는것 같다.