[프로그래머스] Level2 - 뒤에 있는 큰 수 찾기(Javascript)

프로그래머스

▶ 문제 요약

1. 정수로 이루어진 배열이 있는데 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰 수이다.

2. 뒷 큰 수를 차례로 담은 배열을 return하고 존재하지 않는 원소는 -1 담는다. 

 

▶ 코드

function solution(numbers) {
    let stack = [];
    // -1을 주어진 입력값의 길이만큼 생성
    let answer = new Array(numbers.length).fill(-1);
    
    for (let i = 0; i < numbers.length; i++) {
        // 배열의 원소를 변수에 담고
        let element = numbers[i];
        
        // stack이 있거나 현재 원소가 stack의 최상단 요소보다 크다면
        while (stack.length > 0 &&
              numbers[stack[stack.length -1]] < element) {
              // 최상단 요소 꺼내고
              let index = stack.pop();
              // 최상단 요소에 현재 원소 값을 넣는다.
              answer[index] = element;
        }
        // 현재 원소를 스택에 넣는다.
        stack.push(i);
    }
    return answer;


}

▶ 풀이 과정

1. -1을 주어진 입력값의 길이만큼 생성하게 되면 만약 뒷 큰 수가 없는 원소는 -1을 추가적인 처리를 하지 않아도 된다.

 

2. 그림으로 설명하겠다. (입력 예제 1번을 활용했다)

위에 그림처럼 현재 요소가 다음 요소보다 크거나 같다면 stack에 잠시 머문다. 그러다가 큰 요소를 발견하면 stack에서 빠져 나와서 

자유의 몸이 된다. 그리고 나보다 큰 요소가 있다는 것을 배열에 남겨준다. stack을 도는데 현재 요소보다 작은게 없다면 다음 과정을 진행한다.

 

▶ 배운점

1. 솔직하게 문제가 이해가 되지 않는 부분이 있었다. 문제에서는 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 했는데 위에 코드처럼 풀게 된다면 예를 들어 배열 = [5, 7, 6]이라면 5보다 가까운 수는 6인데 위에 코드에 의하면 7이 가장 가까운 수로 인식을 한다. 근데 통과하는 것을 보니 그러한 예외 부분까지 고려하지 않은 것으로 보인다. 

2. 배열 안에 숫자를 비교할 때 이중 for문 보다 stack을 먼저 고려해보자.