[PS/JS] 프로그래머스 - 가장 큰 수

Pakxe·2023년 5월 3일

JavaScript ps 프로그래머스

PS

목록 보기

13/16

문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746

풀이

이전에 풀었던 문제인 큰 수 만들기와 굉장히 유사한 형태의 문제다.
큰 수 만들기 풀이를 보고 이 풀이를 보지 않은채 풀어보는 걸 추천한다.
힌트라면 이 문제는 수를 제거하는 것이 아닌 순서를 바꿔서 큰 수를 만들어야 한다.

이 문제의 제일 중요한 부분은 수의 크고 작음을 어떻게 비교하느냐 이다.
일단 모든 수를 다 읽어봐야 한다. 결국 순차적으로 읽게될 것이다.
그렇다면 이건 버블 정렬과 비슷한 방식으로 큰 수를 만들 수 있겠다고 예상할 수 있다.

이때 숫자들은 스택에 저장하며, 스택의 top + 들어오려는 수 와 반대인 들어오려는 수 + 스택의 top 둘의 크기를 비교해서 후자가 더 크다면 pop하면 된다.

이때 중요한건 pop이 연쇄적으로 일어날 수 있도록 들어오려는 수를 바로 push하지말고, 계속해서 스택의 top + 들어오려는 수과 들어오려는 수 + 스택의 top의 비교를 반복적으로 수행해야한다.

그리고 마침내 전자인 스택의 top + 들어오려는 수가 더 크다면 더이상 순서를 바꾸지 않아도 되므로 반복을 종료한다. 아래 이미지를 보면 이해가 될 것이다.

pop한 수들은 제거되면 안되므로 별도의 변수에 저장해둔다.

그렇게 반복이 종료된 후에 들어오려는 수를 스택에 push한다. 그리고 별도의 변수에 저장해 놓았던 pop된 수들을 스택에 붙인다.

계속해서 들어오려는 수에 대해 위와 동일한 과정을 수행하면 된다.

수도 코드

- for 문으로 모든 수에 대해서 반복한다.
	- pop된 숫자들을 저장할 변수를 선언한다.
    - while 로 더이상 교환하지 않아도 될 때까지 반복
    	- 임시로 저장할 변수에 pop한 수 저장
        - 만약 스택 길이가 0이면 pop할 수 없으므로 break
	- 스택에 현재 수를 push
    - 임시로 저장한 변수에 있던 수들을 스택의 끝에 다시 붙이기

정답 코드

function solution(numbers) {
    const stack = [];
    const strNums = numbers.sort().reverse().map(n => n.toString());
    
    stack.push(strNums[0]); // 초기값
    
    for(let i = 1; i < numbers.length; i++) {
        const temp = []; // 임시로 저장할 변수
        
        // 교환한 수가 더 크다면 교환
        while(parseInt(stack[stack.length - 1] + strNums[i]) < parseInt(strNums[i] + stack[stack.length - 1])){
            temp.push(stack.pop()); // 임시로 저장할 변수에 교환된 수를 넣는다.
            if(stack.length === 0) break; // 스택 길이가 0이면 더이상 pop할 수 없으므로 break
        }
        
        stack.push(strNums[i]); // 스택에 현재 수를 push
        if(temp.length !== 0) { 
            while(temp.length !== 0) { // 임시로 저장한 변수의 내부가 빌 때까지 반복
                stack.push(temp.pop()); // 스택의 끝에 pop했던 수들을 넣는다.
            }
        }
        
    }
    
    let result = stack.join(''); 
    return parseInt(result) === 0 ? '0' : result; // '0000' = '0' 이므로 예외처리
}