배열 만들기 4

문제설명

주어진 정수 배열 arr을 기반으로 새로운 배열 stk를 생성하려 한다.
이 문제의 해결에는 스택 구조의 특성이 활용되는데, 스택은 LIFO(Last In First Out)의 특성을 가지는 자료구조로, 이를 이용하여 특정 조건에 따라 원소를 stk에 추가하거나 제거한다.

문제 규칙

1. stk가 빈 배열일 때: 현재 arr[i] 값을 stk에 추가한다.
2. stk에 원소가 있고, 마지막 원소가 arr[i]보다 작을 때: arr[i]를 stk에 추가한다.
3. stk에 원소가 있지만 마지막 원소가 arr[i]보다 크거나 같을 때: stk의 마지막 원소를 제거한다.

풀이

function solution(arr) {
    let stk = [];
    for(let i = 0; i < arr.length; i++){
        while(stk.length > 0 && stk[stk.length - 1] >= arr[i]){
            stk.pop();
        }
        stk.push(arr[i]);
    }
    return stk;
}

코드 분석

스택 초기화

let stk = [];

stk라는 빈 배열을 초기화하여 원소를 추가하거나 제거할 준비를 한다.

순회 시작

for(let i = 0; i < arr.length; i++){

주어진 배열 arr의 원소들을 순차적으로 순회하기 위한 반복문

조건 확인: 현재 stk의 마지막 원소와 arr[i] 비교

while(stk.length > 0 && stk[stk.length - 1] >= arr[i]){

이 부분은 현재 stk의 마지막 원소와 arr[i]를 비교하는 조건문이다.
만약 stk가 비어있지 않고 그 마지막 원소가 현재 arr[i]보다 크거나 같다면 아래의 내용을 실행한다.

stk의 마지막 원소 제거

stk.pop();

stk의 마지막 원소를 제거한다.
위의 조건에서 현재 stk의 마지막 원소가 arr[i]보다 크거나 같은 경우에 해당 원소를 제거해야 한다고 명시되어 있기 때문이다.

현재 arr[i]를 stk에 추가

stk.push(arr[i]);

반복문 내에서, 현재 순회 중인 arr[i] 원소는 무조건 stk에 추가된다.
이는 stk의 마지막 원소가 arr[i]보다 크거나 같으면 그 원소를 제거한 후, 혹은 그렇지 않으면 바로 현재 원소를 stk에 추가하기 때문이다.