큰 수 만들기 / 프로그래머스 연습문제 / programmers / level2 / Javascript / 탐욕

programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

일단 작성하기에 앞서 탐욕법은 나랑 너무 안맞는 알고리즘 인 것 같다...

물론 내가 아직 실력이 한참 부족하지만... 다른 문제들에 비해서 너무 이해를 못하는 느낌???ㅠㅠ

 

그리하여 다른 블로거분들이 정리한 그리디(탐욕법) 알고리즘을 읽어보는데만 1시간 넘게 소비한 것 같다.

 

본 대로 간단하게 정리해보면

그리디 알고리즘은 그 순간에만 최선의 선택을 할 수 있는 결과를 구하는 알고리즘이다. 하여 마지막의 결과가 최선의 선택은 아닐 수 있다. 

라고 한다.

 

예를 들면 

 

내가 어떤 회사에 들어갔는데 갑자기 시한부 판정을 받아서 3개월 밖에 살지 못한다면?

지금 샤이닝보너스 100만원 받기 vs 1년 만기 근속시 연봉추가 10% 상승하기 같은 거라고나 할까?

그럼 일반적으로는 100만원 안받고 연봉 상승을 하겠지? 하지만 당장이 중요하다면 100만원을 받을 것이다.

 

비유가 맞는지는 모르겠으나... 하여튼 이거를 이해하고 풀었는데도 거의 6시간은 걸린 것 같다 ㅠ

[알고리즘 Flow]

1. 문자열길이 - 삭제할 숫자만큼 반복문 진행

2. 현재 최대값을 저장할 변수를 하나 선언하여, 삭제할 숫자만큼 반복목문을 하나 더 코딩하여 비교

3. 반복문이 종료되면 현재 최대값 문자형을 answer에 추가

4. 그리고 2번째부터 최대값이 있었던 번지의 다음 번지부터 삭제할 숫자 + 현재 카운트 만큼 반복하여 동일작업 수행

 

이렇게 작성하니 정답이었지만 10번 테스트에서 계속 시간초과가 났고 고민의 고민을 거듭하다가 도저히 안되겠어서 힌트를 조금 보았다.

 

그리하여 추가된 사항

5. 해당 문자열의 값이 9라면 비교할게 이미 최대값이니 해당 반복문을 종료하고 바로 answer에 추가

 

이러니 경과시간이 확연히 줄어든 것을 확인 할 수 있었다. ㅠㅠ 휴...

 

[나의 코드]

function test() {

	var number = "4177252841"
	var k = 4;

    solution(number, k);
}

function solution(number, k) {
    var answer = '';
    var max = '';
    // 매 순간의 최대값을 저장 해 줄 변수
    var index = 0;
    // 최대값이 저장되었을 때의 그 다음 부터 시작할 위치를 저장할 변수

    for (let i = 0; i < number.length-k; i++) { 
    // 문자열 길이 - 삭제할 숫자 만큼 반복문을 진행한다.
        max = '0';
        // 최대값 변수를 0으로 초기화 (그때그때 최대값을 구해야하기 때문)
            for (let j = index; j <= k+i; j++) {
            // 최대값이 저장된 번지의 +1 지점부터 비교를 시작할 것이다.
            // 언제까지?? 삭제할 숫자의 개수 + 삭제한 숫자 만큼
            // (처음에 그냥 k라고만 했는데 그렇게 하니 최대값 이후의 숫자들을 비교해주지 못하더라)
                if (number[j] == '9') {
                // 해당 문자열 번지의 숫자가 최대값이라면 더 이상 이 반복문에서는 비교할 필요가 없으니 바로 변수에 넣어주고 브레이크
                // 효율성 테스트에서 떨어져서 힌트를 구한 부분
                    max = number[j];
                    index = j+1;
                    break;
                } else if (max < number[j]) {
                // 현재의 최대값이 해당 문자열 번지의 숫자보다 작을때마다 최대값을 계속 초기화해준다.
                    max = number[j];
                    index = j+1;
                    console.log("max : " + max + " index : " + index);
                }

            }
            answer += max;
            // 안쪽 반복문이 완료될때마다 max에는 현재의 최대값이 들어있으니 이 값을 answer에 계속 추가해준다.
    }

    console.log(answer)
    return answer;
}

 

레벨이 올라갈 수록 문제를 풀 수록 단순히 구현만 하는게 아닌 어떻게 하면 효과적으로 구현할 수 있을지도 고민하게 만드는 것 같다. 꾸준히 열심히 더 풀어보자.

 

---

[깃허브]

https://github.com/RUCKUSJERRY/practiceOfJava/blob/main/Prs_Pratice/src/com/level02/createBigNum.js

RUCKUSJERRY/practiceOfJava