프로그래머스 - Level 2. 뒤에 있는 큰 수 찾기 / JavaScript (js)

문제설명

문제분석

입력 배열을 순차적으로 순회합니다. 이때 순회하는 요소를 기준으로 이 요소보다 값이 크고, 가장 가까운 요소의 값으로 현재 요소의 값을 업데이트합니다.

1. 입력 배열을 순차적으로 탐색한다.
2. 현재 인덱스의 요소를 기준으로, 이후에 나오는 배열의 요소 중 현재 요소보다 큰 값을 찾는다.
3. 현재 요소보다 큰 값을 발견하면 해당 값으로 현재 요소를 업데이트한다.
4. 현재 요소가 가장 큰 값인 경우 -1로 업데이트 한다.

 

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다.

이해하기 쉽게 코드작성하기

function solution(numbers) {
	// 모든 요소를 순회하며 업데이트
    return numbers.map((x, i) => {
    	const remains = numbers.slice(i + 1);
        // 현재 요소보다 큰 값을 찾으면 업데이트 후 리턴
        for(const el of remains) {
        	if(x < el) {
            	return el;
            }
        }
        return -1;
    });
}

코드 설명

먼저 위 코드는 분석한 문제를 토대로 현재 요소와 나머지 요소를 비교하는 코드입니다. 안타깝게도 이 코드는 논리적으로 합당하나, 위 코드는 Big-O notation으로 최악의 경우 O(n^2)입니다. 배열의 길이가 조금만 길어져도 굉장히 느려지며, 제출 후 채점하는 경우 시간 초과로 실패합니다. 그렇다면 가능한 반복문을 줄여서 해결해야 합니다.

 

이 문제의 경우 처음부터 마지막 인덱스까지 모든 인덱스를 탐색하여야 합니다. 그러나 이때 i번째 요소보다 i+1 번째 요소의 값이 더 작다면 업데이트할 내용이 없습니다. 오히려 i+1 번째 요소마저 그 다음 요소를 기다려야하는 판국입니다. 따라서 스택을 사용해 다음과 같이 한 번 바꿔보겠습니다.

function solution(numbers) {
    const idxStack = [];
    const answer = new Array(numbers.length).fill(0);
    
    for(let i = 0; i < numbers.length; i++) {
    	// 스택이 비어있거나 현재 요소가 이전 요소보다 작은 경우
        if(idxStack.length === 0 || numbers[i] < numbers[i-1]) {
        	idxStack.push(i);
        } else {
        	// 스택이 비어있고,
            // numbers[스택의 peek]가 현재 요소보다 작은 경우
            // answer[스택의 peek]를 현재 요소로 업데이트
	        while(
    	        idxStack.length > 0 &&
        	    numbers[idxStack[idxStack.length - 1]] < numbers[i]
	        ) {
	            answer[idxStack.pop()] = numbers[i];
	        }
    	    idxStack.push(i);
        }
    }
    while(idxStack.length > 0) {
        answer[idxStack.pop()] = -1;
    }
    
    return answer;
}

 

이렇게 변경하면 훨씬 빠른 퍼포먼스로 문제를 해결할 수 있습니다. 그러나 for문 안에서 if문과 관계없이 idxStack.push(i)를 실행하므로 if문을 없애도 동일하게 동작합니다. 이왕 수정하는 김에 모듈화를 통해 조금 더 깔끔하게 작성하겠습니다.

function solution(numbers) {
    const idxStack = [];
    const answer = new Array(numbers.length).fill(0);
    
    for(let i = 0; i < numbers.length; i++) {
        while(
            isNotEmpty(idxStack) &&
            numbers[getLastElement(idxStack)] < numbers[i]
        ) {
            answer[idxStack.pop()] = numbers[i];
        }
        idxStack.push(i);
    }
    while(isNotEmpty(idxStack)) {
        answer[idxStack.pop()] = -1;
    }
    
    return answer;
}

function isNotEmpty(arr) {
    return arr.length > 0;
}

function getLastElement(arr) {
    return arr[arr.length - 1];
}

level 2로 넘어오니 확실히 level 1보다 간단한 자료구조라도 사용하는 경향이 커졌습니다. level 1이 문자열을 가지고 노는 문제들이었다면, level 2는 기본적인 알고리즘에 관한 내용인 것 같습니다. 앞으로 문제를 풀 때에도 조금더 알고리즘 기초 체력을 높이는 데에 주안점을 두고 문제를 해결하겠습니다.