프로그래머스 LV2 #9 큰 수 만들기

Jake Seo·2020년 8월 9일
0

프로그래머스 LV2

목록 보기
9/10

프로그래머스 LV2 #9 큰 수 만들기

문제

풀이

이 문제의 경우에는 숫자로 된 문자열에서 k개의 문자열을 지웠을 때 만들어질 수 있는 수 중에 가장 큰 수를 반환하는 함수를 작성하는 문제입니다.

제가 생각한 문제풀이의 핵심은 자릿수별로 가장 큰 수를 찾아내는 것입니다. 그런데 조건은 그 숫자를 기준으로 최종적인 문자 길이를 구성할 수 있어야 합니다.

이를테면 입출력 예제 중에 number="1924" k=2의 경우를 보면 최종 결과로 2자리의 숫자로된 문자열이 나온다는 것을 알 수 있습니다.

최종 문자열의 길이를 일반화해서 공식을 만들면 number.length - k입니다.

위의 기준을 이용하면 "1924"에선 "192"까지 첫번째 숫자의 후보로 들어갈 수 있습니다. 왜냐하면 "4"가 들어가면 어떤 행위를 해도 뒤의 숫자를 이용하여 2자리 숫자를 만들 수 없습니다.

요약하자면 가능한 값 중 가장 큰 값을 선택하는 것입니다. 가능한 값 중 가장 큰 값을 선택하면 그 다음 과정은 선택된 값 인덱스 이후의 인덱스부터 또 가능한 값 중 가장 큰 값을 선택하고 이 과정을 반복하면 됩니다.

소스코드로 짜면 아래와 같습니다.

let solution = (number, k) => {
    let answer = "", startIndex = 0, maximumCandidateIndex = 0; // 사용할 변수 값들 초기화

    for(let i=number.length-k; i>0; i--) { // 필요한 글자수만큼 총 반복
        let maximumCandidate = '0'; // 가장 작은 숫자를 최대 값에 넣어놓음
        
        for(let j=startIndex; j<=number.length-i; j++) { // 시작 인덱스로부터 출발 / 가능한 범위는 number.length-i 까지 가능 / 그래야 결과만큼의 문자열 생성 가능
            if(number[j]>maximumCandidate){ // 시작 인덱스부터 최대 값을 구함
                maximumCandidate = number[j];
                maximumCandidateIndex = j;
                if(maximumCandidate === '9') break; // 9면 자리수중에 가장 큰 값이기 때문에 그만 순회하여도 됨
            }
        }
        
        answer = answer + maximumCandidate; // 답안에 숫자 추가하고
        startIndex = maximumCandidateIndex + 1; // 최대값 다음 인덱스부터 또 반복
    }
    
    return answer;
}
profile
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.

0개의 댓글