[프로그래머스] 큰 수 만들기(그리디) - ☆

#문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42883?language=cpp

<전략>

1. 순열로 풀다가 100만자리인 것을 뒤늦게 확인했다. 순열의 결과는 당연히 시간초과.

2. 생각해보다가 도저히 모르겠어서 블로그를 참고했다.

3. 전략은 이렇다. 크기 10인 배열에 숫자들이 들어가있다고 생각해보자. 이중 k개만큼을 지운 숫자 중 가장 큰 숫자를 구하는 문제이다. k를 4라고 생각하자.

배열의 인덱스 : 0 1 2 3 4 5 6 7 8 9 , 이중 4개를 지워야 하고, 10 - 4 = 6, 6개를 가져가야 한다.

이 6개 중에, 인덱스 0~k까지의 범위안에서 무조건 한개이상의 숫자가 나와야 한다.

( 0 1 2 3 4 ) 5 6 7 8 9 괄호 안의 범위에서 무조건 한개이상이 나와야한다. 왜냐하면, 괄호 범위에서 한개도 선택하지 못하면, 남는 수는 5개뿐이기 때문이다. 따라서, 괄호안의 범위 중 가장 큰 값을 가져오고 그 큰 값의 인덱스를 저장해서 그 다음 반복에 그 인덱스보다 +1 인 인덱스부터 다시 반복해서 찾으면 된다.

예를 들어보면, 4 1 7 7 2 5 2 8 4 1 이라는 숫자가 들어왔을때,

( 4 1 7 7 2 ) 5 2 8 4 1, 괄호안의 숫자 중 7이 가장 큰 수이고, 2번째 인덱스의 7이 가장 먼저 나오므로, 인덱스 2를 저장하고, 인덱스 2 다음인 인덱스 3 부터 그 다음 검사를 진행한다. 여기서, 전체 반복을 6번으로 하게끔 한다. 숫자를 6개 뽑아야 하므로 그렇다. 이제, 여기서 그 다음 검사의 범위를 하나 늘려야한다. 오른쪽 괄호의 위치가 +1 되어야 한다는 소리.

4 1 <7> ( 7 2 5 ) 2 8 4 1 , 선택된 숫자는 <>처리하였다. 3번째 인덱스부터 5를 값으로 가지는 5번째 인덱스까지로 검사 범위가 바뀐다. 자, 하나를 선택했기 때문에, 남은 자리는 5자리이다. ( 7 2 5 ) 중에 아무런 값도 뽑지 못한다면 남은 숫자는 2 8 4 1 4개뿐이라 자리가 한자리 남게 된다. 따라서, ( 7 2 5 ) 중에 무조건 한자리를 먹어야 한다. 역시, 제일 큰 수를 만들어야 하므로 이 범위에서 제일 큰 숫자인 7을 선택하고 또 다음 범위로 넘어간다.

4 1 <7> <7> ( 2 5 2 ) 8 4 1, 이후에 같은 방식으로 하면,

4 1 <7> <7> 2 <5> ( 2 8 ) 4 1

4 1 <7> <7> 2 <5> 2 <8> ( 4 ) 1

4 1 <7> <7> 2 <5> 2 <8> <4> ( 1 )

4 1 <7> <7> 2 <5> 2 <8> <4> <1>

775841이 답이된다.

※주의사항

1. 안쪽 for문의 반복자 j의 시작값은 start로 이해하기 쉽다. 하지만 어디까지 설정해야 하는가는 생각을 좀 해봐야 한다.
배열 전체의 크기가 n이라 할때, 바깥쪽 반복자 i의 값이 0~n-1-k까지 반복하고(n-k개의 자리를 선정하므로),
j는 start(이전 범위의 가장 큰 녀석의 인덱스+1)~k+i 로 설정하면 된다. 인덱스는 0부터 시작해서, k 는 k+1번째 숫자이므로, 0~k 번째 인덱스에서 무조건 한개 이상의 자리를 차지하므로, k로 제한을 두고, 안쪽 반복이 끝날때마다, 자리가 하나씩 줄어들고, 탐색해야 하는 범위가 하나씩 늘어나므로, 바깥 반복자 i를 이용해서 k+i 가 되는 것이다.

Code