[프로그래머스] 뒤에 있는 큰 수 찾기 JS

 

첫 번째 풀이는 뒷큰수가 있는 경우만 판별하여
이중 포문으로 처리했습니다
2개 정도 시간초과가 발생했습니다

시간 초과가 발생해서 어떻게 해야 반복을 줄일 수 있을까 고민했습니다
생각을 하다보니 스택을 통해 뒷큰수만 유지하면 되겠다는 판단이 들었습니다.
뒤에서부터 순회를 하면서
바로 뒤에 있는 수와 그 수의 뒷큰수들만 스택으로 관리하는 방식으로 풀었습니다

 

function solution(numbers) {
  //뒤에서부터 순회하면서
  //스택에는 바로 뒤에 있는 수와 그 수의 뒷큰수들만 관리

  const stack = [];
  const result = [];

  //뒤에서부터 순회
  for (let i = numbers.length - 1; i >= 0; i--) {
    //스택이 빌 때까지 반복
    while (stack.length) {
      //바로 뒤에 있는 수와 그 수의 뒷큰수
      const current = stack.pop();

      //가장 가까이 있는 뒷큰수를 발견하면
      //뒷큰수 다시 stack에 넣고
      //반복문 탈출
      if (current > numbers[i]) {
        result.push(current);
        stack.push(current);
        break;
      }
    }

    //stack이 비었으면 뒷큰수가 존재하지 않는 것이므로 결과에 -1 추가
    if (stack.length === 0) result.push(-1);

    //현재 수를 stack에 추가
    stack.push(numbers[i]);
  }

  return result.reverse();
}

 

 

밑에는 

시간 초과 걸렸었던 풀이

function solution(numbers) {
    //뒤에서부터 순회하면서
    //최대값을 저장해나감
    //뒷큰수가 있으면 숫자 바로 뒤에서부터 순회
    
    let max = -Infinity;
    const result=[];
    
    for(let i=numbers.length-1;i>=0;i--){
        if(max<=numbers[i]){
            result.push(-1);
            max=numbers[i];
            continue;
        }
        
        for(let j=i+1;j<numbers.length;j++){
            if(numbers[j]>numbers[i]){
                result.push(numbers[j]);
                break;
            }
        }
    }
    
    return result.reverse();
}