[TIL #15]

코드분석

Q. 양의 정수가 주어질 때,
숫자에서 k개의 자릿수를 제거하여 얻을 수 있는 가장 큰 수를 구하세요.

• number는 최대 1,000,000자리까지 입력될 수 있습니다.
• k는 1 이상 len(number) - 1 이하입니다.
• EX) 입력 number = 1924, k = 2, 출력 94

알고리즘 문제인데 내용이 재밌고 스택을 사용해 보아서 정리해 보려고 한다.

let number = 195324, k = 4;

function del(number, k) {
    let num = String(number);
    let ResultArray = [];
    let Remove = k;
    
    for(let i=0;i<num.length;i++){
        const digit = num[i];
        while(Remove > 0 && ResultArray.length > 0 && 
            ResultArray[ResultArray.length-1] < digit
        )
        {
            ResultArray.pop();
            Remove--;
        }
        ResultArray.push(digit);
    }
    while (Remove > 0) {
        ResultArray.pop();
        Remove--;
    }
    return ResultArray.join('');
}

console.log(del(number, k));

1. 숫자를 문자열로 변환

let num = String(number); 

• 입력된 숫자 'number'를 문자열로 변환한다. 각 자리를 개별적으로 나누어 컨트롤 해야 하기 때문이다.
  
  

2. 결과를 저장할 배열 초기화

let ResultArray = [];

• 새롭게 배열을 만들어 스택으로써 가장 큰 수를 하나씩 추가해 준다.
  
  

3. 제거할 숫자의 개수 설정

let Remove = k;

• k의 값을 Remove에 저장하여, 제거해야 할 자릿수를 파악한다.
  
  

4. 각 자리에 수 저장

for(let i = 0; i < num.length; i++) {
    const digit = num[i];

• 문자열로 변환된 숫자의 각 자리에 있는 수를 digit에 저장한다.
  
  

5. 현재 자릿수와 스택의 마지막 숫자를 비교하여 제거 & 스택에 추가

while(Remove > 0 && ResultArray.length > 0 && 
            ResultArray[ResultArray.length-1] < digit
        )
        {
            ResultArray.pop();
            Remove--;
        }
        ResultArray.push(digit);

• 여기서 고민을 오래 했다.
• while 루프 안에서 다음 조건을 만족 시키며 실행한다.
  1. 스택에서 더 제거해야하는가 (Remove > 0)
  2. 스택이 비어있지 않은가 (ResultArray.length >0)
  3. 스택의 마지막 수가 비교하는 값보다 작은가(ResultAraay[ResultArray.length -1] < digit)
• 이렇게 위 3가지 조건을 만족하면 지금 값을 스택에 push해준다.

6. 추가가 끝나고 더 제거해야할 경우 뒤에서부터 순차적으로 제거

while (Remove > 0) {
    ResultArray.pop();
    Remove--;
}

• 루프가 종료 됬음에도 Remove가 0이 아닐경우 스택의 뒤에서부터 제거

이러한 방식으로 알고리즘을 작성했다.
흥미로웠던 것은

• 숫자로 입력받은 것을 String()을 통해 문자열로 바꿔주는 것
  • 기존에는 배열을 split("")을 통해 만들어 주려고 했는데 실패 하였음.
• 배열을 통해 스택기능을 사용하여 본 것.

즐겁다.