문제

문제 해결 전략

숫자를 들어온 순서를 그대로 유지한 채로 k개의 숫자를 제거해서 가장 큰 숫자를 만들면 된다. 만약에 원래 4자리 숫자에서 k = 2일때는 결국 2자리 십진수를 찾아야하므로 00으로 초기화된 문자열에서 비교하면서 만약에 number의 인덱스의 숫자가 더 크면 그 다음 자리로 넘어가는 식으로 만들면 될 것 같다.

ex1) 1924 k = 2

1 9, 2, 4
19, 12, 14
9 2, 4
92, 94
2, 4
24

ex2) 1231234 k = 3

1 2, 3, 1, 2, 3, 4
1231, 1232, 1223, 1234, 1312, 1323, 1324, 1334, 1123, 1134,
1234

2, 3, 1, 2, 3, 4
2312, 2323, 2334, 2123, 2134, 2234

3, 1, 2, 3, 4
3123, 3234

1, 2, 3, 4
1234

코드

string solution(string number, int k){
	string answer = "";
	int start = 0;

	for(int i = 0;i < number.size()-k;i++){
		char max = number[start];
		int mxIdx = start;	
		for(int j = start;j <= k+i;j++){
			if(max < number[j]){
			       	max = number[j];
				mxIdx = j;
			}
		}
		start = mxIdx + 1;
		answer += max;
	}
	
	return answer;
}

코드 설명

하나의 예시를 가지고 코드를 설명해봐야겠다.
첫 번째 for문의 range는 0부터 number.size()-k이다. 즉 k, 삭제되는 문자열의 길이의 전까지 탐색한다는 의미이다.
두 번째 for문은 start 결정된 문자열의 다음 인덱스를 가리키는 범위에서 부터 삭제되는 문자열의 길이와 i를 더한 범위까지 탐색을 하게 된다. 쉽게 설명해서 위에서는 큰 범위로 문자가 더 짧거나 긴 문자열을 반환하지 않도록 제어하는 것이고 안에 for문은 실제 허용된 범위 내에서 최대의 문자를 찾아주는 작업을 하게 된다.

하나의 예시를 들어서 설명하면 이해가 더 쉬울 것 같다.

ex)number = "123123411" k = 4
number.length() = 9인 문자열에서 4개의 문자를 제거하면 answer의 크기는 5가 될 것이다.

first loop<<
i = start = 0 에서 i < 5일때
max = 1 mxIdx = 0
j = 0 부터 j <= 4
1 2 3 1 2 중에서 max값을 탐색하게 된다.
max = 3 mxIdx = 2
start = mxIdx + 1 = 2 + 1 = 3
answer = "3"

second loop<<
i = 1
max = 1 mxIdx = 3
j = 3부터 j <= 5
1 2 3 중에서 max값을 탐색하게 된다.
max = 3 mxIdx = 5
start = mxIdx + 1 = 5 + 1 = 6
answer = "33"

third loop<<
i = 2
max = 4 mxIdx = 6
j = 6부터 j <=8
4 1 1 중에서 max값을 탐색한다.
max = 4 mxIdx = 6
start = mxIdx + 1 = 6 + 1 = 7
answer = "334"

fourth loop>>
i = 3
max = 1 mxIdx = 7
j = 7부터 j<= 8
1 1 중에서 max값을 탐색한다.
max = 1 mxIdx = 7
start = mxIdx + 1 = 7 + 1 = 8
.
.
.
이런식으로 진행하다보면 마지막에 3341이라는 값을 가지게 된다.