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

문제

뒤에 있는 큰 수 찾기

프로그래머스

 

map함수를 사용한 코드

function solution(numbers) {
    var answer = [];
    answer = numbers.map((e,i,arr)=> {
        for(let j =i+1; j <arr.length;j++){
            if(arr[j]>e){return arr[j];}
        }
        return -1;
    })
    return answer;
}

결과 : testcase 20~23을 시간 초과로 통과하지 못했다. 

 

📖스택을 사용한 코드

function solution(numbers) {
    var answer = new Array(numbers.length).fill(-1);
    var stack = [];
    for(var i =0;i<numbers.length;i++){
        while(stack&&numbers[stack.at(-1)]<numbers[i]){
            answer[stack.pop()] = numbers[i];
        }
        stack.push(i);
    }
    return answer;
}

결과 : 모든 testcase통과!

 

오랜 시도 끝에 시간 초과 문제를 해결하기 위해 찾아낸 코드는 위와 같았다. 

스택을 이용한 코드인데 갑자기 이해 난이도가 극상이 된다.😭

 

이해를 위해 numbers가 [2,3,3,5]일 때 for문 안에 과정을 표로 만들어 보았다. 

numbers = [2,3,3,5]

i	stack	answer
초기	[]	[-1,-1,-1,-1,]
0	[0]	[-1,-1,-1,-1]
1	[1]	[3,-1,-1,-1]
2	[1,2]	[3,-1,-1,-1]
3	[1]	[3,-1,5,-1]
	[]	[3,5,5,-1]
결과값	[3]	[3,5,5,-1]

 

 

✅checkpoint!

var arr = new Array(N).fill(-1);	크기가 N이고-1로 채워진 배열 만들기
arr.at(-1)	배열의 맨 뒤에 값 반환

 

💡아이디어 요약

map사용	map함수를 이용했다. map에 인자로 들어가는 함수 내에 for문을 돌려 가장 가까운 큰값을 반환하게 하고 없을 경우 -1을 반환해서 answer이라는 새로운 배열을 만들었다.
스택 사용	길이가 numbers와 동일하고 -1로 초기화된 answer배열을 만든다.  인덱스 값을 담을 stack배열을 만든다.  stack배열에 인덱스를 넣고 후입선출 방식으로 stack안에 인덱스를 꺼내서 while문 안에 비교과정을 거쳐 해당 인덱스에 값을 넣는다.