문제 설명

• 출처

어떤 숫자에서 k개의 수를 제거하였을 때 얻을 수 있는 가장 큰 수를 구하려고 합니다.

예를들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다.

이 중 가장 큰 숫자는 94입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 작성해주세요.

제한사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

• k는 1 이상 number의 자릿수 미만의 숫자입니다.

입출력 예

Solution

일전에 풀었던 문제를 복기할 겸 다시 풀었다.

문제 해결을 위해 주의해야 할 점이 두 가지 있다.

첫 째는 1,000,000 자리의 문자열 형태가 주어지기 때문에 문자열 자체를 자르는 등의 코드는 시간 초과를 일으키기 쉽다.

두번째는 문자열 제거 문제라고 했지만 사실 문자열 선택 문제로 접근하는 것이 훨씬 더 쉽고 깔끔한 코드를 구현할 수 있다.

선택으로 문제를 해결할 경우 큰 수를 선택해야 하는 명확한 기준이 생기기 때문이다.

즉, k개의 수를 제거하는게 아니라 number.length() - k개의 수를 선택하는 방향으로 진행한다.

단, 선택 시 고려해야 할 부분이 있다. 바로 선택 범위 조정이다. 우리가 만들어야 하는 수는 특정 길이를 만족해야 한다. 다시말해 number.length() - k라는 길이를 만족해야 한다.

만일 선택 범위를 제한하지 않는다면 첫 번째 선택한 수가 문자열의 마지막 인덱스가 되어버릴 수 있다.

이를테면 12341299 중 3개를 선택해야 할 때 처음 선택한 수가 1231299 라면 다음 2개의 수를 선택할 수가 없어진다.

즉, 1231299 사이로 범위를 좁혀야 그 다음 두번의 선택을 할 수 있게된다.

이 범위 제한은 toSearch라는 변수로 표현할 수 있는데, 구하는 수식은 int toSearch = 문자열 전체 길이 - 남은 선택 개수로 구할 수 있겠다.

코드를 살펴보자.

Code

복기 문제(문자열 선택 변수에 관심)

기존에 풀었던 문제(문자열 삭제 변수에 관심)

두 코드를 비교해보면 우선 toSearch의 범위가 서로 다르다. 삭제할 변수의 남은 수에 관심을 갖는 두 번째 코드의 경우 cutoff + 1개 만큼 탐색을 하여 그 중 가장 큰 값(max) 아래의 문자열은 제거 한다. cutoff + 1개만큼의 탐색을 하는 이유는 cutoff 개 만큼의 문자열을 앞에서 삭제 할 수 있어야 하기 때문이다.

그리고 첫 번째 코드의 toSearch는 선택할 문자의 남은 수를 고려한다. number.length - toGetSize 범위를 탐색하는 이유는 toGetSize개 만큼의 문자열을 뒤에서 선택할 수 있어야 하기 때문이다.

몇줄 평

기존에 풀었던 문제를 다시 파악하느라 고생했다. 왜 저렇게 로직을 짰을까? 아마 제대로 파악하고 짰다기 보단 흐름대로 흘러가다 보니 저렇게 구현한 것 같다. 이번 기회에 복기 문제와 기존 문제를 좀 더 심층적으로 분석하는 시간을 가졌다.

문자열 선택 변수에 관심을 둔 "복기 문제"와 문자열 삭제 변수에 관심을 둔 "기존에 풀었던 문제"를 보면 알겠지만 문자열 삭제 변수에 관심을 둔 로직의 경우 다시 봐도 내가 무슨 생각으로 저런 로직을 짯는지 한번에 파악이 잘 안된다. 다시말하면 문자열 선택 변수에 관심을 둔 로직이 보다 직관적이다.

왜 문자열 선택을 위한 범위가 i <= curIdx + cutOff 인가 생각해보면 삭제해야할 문자열 개수(cutOff) + 1개만큼의 범위에서 가장 큰 수를 선택한다. 그리고 선택한 수와 curIdx 사이에 어떤 문자가 존재한다면 그 수는 자동적으로 삭제됨을 의미하므로 cutOff = toSearch - maxIdx를 취해준다. 이로써 삭제해야할 문자열의 개수가 갱신된다.

반면 toGetSize 변수에 관심을 둔 복기 문제는 좀 더 깔끔하게 처리가 가능하다.

사실 처음 복기 문제를 풀었을때는 while이 아닌 Recursion으로 구현했었다.

하지만 계속해서 9, 10번에서 실패를 해서 반례를 계속 찾아보려고 노력했지만 결국 찾지 못했다.

거의 2시간 가까이 삽질한 끝에 Recursion이 문제라는 점을 깨달았다. (처음 문제 해결시 재귀로 해결했다)

즉, call stack이 터져버리는 현상이 발생한 것이다.

재귀를 loop로 수정하니 정상 제출이 되었다.

참고 및 출처

• 프로그래머스