프로그래머스 레벨 2 - 큰수 만들기 (https://programmers.co.kr/learn/courses/30/lessons/42883)
팀원 중에 한 분이 요즘 그리디 문제를 푸는데, 잘 안풀리는 문제가 있다고 해서 나도 한 번 살펴보게 되었다.
이 문제가 백준에서 2초 제한으로 올라왔으면 진짜 금방 풀었을 거 같지만.. 생각보다 실수를 많이해서 두시간 정도 걸렸다.
레벨3까지는 아니고, 레벨2 중에서 까다로운 축에 속한다고 생각하는데 비슷한 문제를 몇 개 더 풀어본 상태였다면 생각이 달라졌을지도 모르겠다.
O(N^2) 까지는 금방 생각나고, O(N) 풀이는 적절한 전처리 이후 최대한 효율적인 소거를 해나가야 하기 때문에 조금 귀찮다.
몇 달 전에도 그리디 문제가 코딩 테스트에 나와서 굉장히 고생했던 기억이 나는데, DP 문제에만 집착하지 말고 Leetcode에서 그리디도 많이 풀어보는게 좋을 것 같다는 생각이 들었다.
풀이
이 문제에서 input 뒷부분은 딱히 살펴볼게 없다.
맨 앞부터 살펴보고, 이 숫자를 작게 만드는 주범 들을 적절히 골라내주면 된다. 뒷부분은 그 다음에 생각해도 좋다.
주범을 골라내는 기준은 어떻게 잡아야 할까? 가능한 앞 부분을 큰 숫자 위주로 구성할 수 있도록 작은 숫자들을 골라내는 것이 중요하다.
현재 보고 있는 숫자의 위치가 i번째이고, length(number) != i 라고 했을 때 i+1 번째 숫자보다 작은 i 번째 숫자는 이 숫자를 작게 만드는 주범이라고 간주할 수 있다.
내 접근법은 아래와 같다.
1) 먼저 주어진 숫자에 대해 첫번째 인덱스부터 k번째 인덱스까지 살펴본다.
그 중 가장 큰 숫자가 있는 위치를 보관할 maxPos라는 변수를 선언하고, k번째 인덱스까지 탐색하면서 그 위치를 저장해놓는다.
2) 맨앞부터 maxPos 직전까지 제거하고, 그 만큼 k를 감소해준다.
당연한 얘기지만.. 뒤에 나오는 숫자들이 아무리 크더라도 맨앞 숫자가 작으면 아무 소용 없기 때문이다.
-> k가 여기서 0이 된 경우 이후 로직은 진행할 필요 없이 [k+1...length] 부분을 잘라서 리턴하면 된다. 다만 그렇게 하지 않아도 문제 푸는데에는 지장 없으므로 따로 처리하지 않고 넘어갔다.
3) 앞부분이 제거된 number를 탐색하면서, 역방향 탐색 + 제거에 사용할 j에 현재 위치를 저장한다.
4) 도중에 i+1 번째 숫자보다 작은 i 번째 숫자를 발견하면 잠시 탐색을 중단한다. 이후 j를 1씩 감소해주면서, number[j] < number[i+1] 인 숫자를 하나씩 제거하고 number[j] >= number[i+1]이 되면 멈춘다.
예를 들어 911111174321이 있고 k가 6인 경우, 7 직전의 1에서 탐색을 중단하게 될 것이다. 그러면 j가 맨 앞에 닿을 때까지 만나는 숫자들은 항상 7보다 작으니 삭제 대상에 들어가게 될 것이고, 이렇게해서 만들어진 974321은 이 상황에서 만들 수 있는 숫자중 가장 큰 숫자가 된다.
5) 앞의 과정들을 거친 뒤에도 k가 0보다 크다면, 현재 남은 숫자에서 뒷부분을 k만큼 잘라낸 값을 리턴해주면 된다.
예시
4177252841 이 input으로 주어지고, k가 4인 경우 맨 앞부터 살펴보면 아래와 같다.
(편의상 0-based indexing을 쓰겠다)
1) 0번째부터 3번째까지 살펴본 결과 제일 큰 숫자는 7이다. 7이 제일 먼저 등장하는 index인 2가 maxPos에 들어가게 된다.
2) maxPos에 2가 들어있으니 [0...1]번째를 잘라낸 77252841이 새로운 number가 되고, k를 2만큼 감소시켜준다. (k = 2)
3) 맨앞부터 숫자를 하나씩 비교해준다. 우선 0번째 숫자와 1번째 숫자는 같으니 스킵 (i = 0, j = 0)
4) 1번째 숫자가 2번째 숫자보다 크니 스킵 (i = 1, j = 1)
5) 2번째 숫자는 3번째 숫자보다 작으니 지워준다. 1번째 숫자는 3번째 숫자보다 크니 지우지 않고 중단한다. (남은 숫자 7752841, k = 1)
6) 3번째 숫자는 4번째 숫자보다 크니 스킵
7) 4번째 숫자는 5번째 숫자보다 작으니 지워준다. 3번째 숫자도 5번째 숫자보다 작지만, k가 이미 0이 되었으므로 더이상 제거하지 않고 끝낸다. (남은 숫자 775841, k = 0)
8) 최종적으로 남은 숫자를 모아서 리턴해주면 끝~
짧은 팁
맨앞부터 maxPos까지 잘라내거나 뒷부분을 k만큼 자르는 것은 subString을 이용하면 간단하지만, 중간 부분을 일부 잘라내는 것은 신중하게 접근할 필요가 있다.
문자열 길이가 짧으면 subString을 남발해서 합쳐도 문제가 안되겠지만, 엄청 자주 발생한다면….
자바에는 toCharArray라는 유용한 메서드가 있으니, 맨앞부터 maxPos까지 잘라낸 number 문자열을 char[]로 변환하고 제거할 위치에 0을 채워버리자. 이후 0이 아닌 문자열들만 StringBuilder에 하나씩 넣어주면 된다.