[구현]프로그래멋 큰 수 만들기( 실패분석 - 아이디어 )

접근

https://school.programmers.co.kr/learn/courses/30/lessons/42883

요즘 문제를 풀면서 느낀 것은 구현 문제의 경우
간단한 풀이법을 발견하는게 어렵다는 것입니다.

이 문제의 경우
주어진 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
따라서 2중 for문을 도는 경우 연산 횟수가 1,000,000,000,000 번으로
100초가 넘게 걸릴 수도 있습니다.

따라서 2중 for문으로 찾는 것이 아니라 O(n)으로 끝낼 수 있도록 방법을 구현해야 합니다.

결국 저는 아이디어를 떠올리지 못했는데
다른 분의 풀이를 보고 힌트를 얻어 다시 풀어보았습니다.

방법은 이러합니다.
1. 일단 k개를 제외하고 가장 큰 수를 구해야 하기 때문에
주어진 number의 길에서 k를 뺀 자리수가 보장되어야 합니다.

2. 그걸 보장해주면서 안을 돌아야 하는데 현재 위치에서 현재위치+k까지의 수에서 가장 큰 수를 누적합니다. 가장 큰 수를 누적하고 나서는 그 뒤부터 비교가 가능하므로 가장 큰 수의 위치를 기억해야 합니다.

예시

number = "4177252841"
k = 4

즉 구해야하는 자리수는 6자리입니다.
그리고 6자리를 구하면서 비교해야할 안의 개수의 k+1로 5개 입니다.

• 1회 : ([4 1 7 7 2]) 5 2 8 4 1

  가장 큰 수 7
  다음 비교 위치 3
  answer = "7"

• 2회 : 4 (1 7 [7 2 5]) 2 8 4 1

  가장 큰 수 7
  다음 비교 위치 4
  answer = "77"

• 3회 : 4 1 ( 7 7 [2 5 2]) 8 4 1

  가장 큰 수 5
  다음 비교 위치 6
  answer = "775"

• 4회 : 4 1 7 (7 2 5 [2 8]) 4 1

  가장 큰 수 8
  다음 비교 위치 8
  answer = "7758"

• 5회 : 4 1 7 7 (2 5 2 8 [4]) 1
  가장 큰 수 4
  다음 비교 위치 9
  answer = "77584"

• 6회 : 4 1 7 7 2 (5 2 8 4 [1])
  가장 큰 수 1
  다음 비교 위치 10(끝)
  answer = "775841"

따라서 이를 풀이로 나타내면 아래와 같습니다.

풀이(여기서 왜 실패가 나오는지 - 스터디원과 알아내기)

import java.util.*;

class Solution {
    
    
    
    public String solution(String number, int k) {
        //k개의 수를 제거했을 때얻을 수 있는 가장 큰숫자
        // 문자열 형식의 숫자 nuber 제거할 수의 개수 k
     
       
        
        StringBuilder sb = new StringBuilder();
        
        int index=0;
        for(int i=0;i<number.length()-k;i++){        
            int max =0;
            String sub = "";
            for(int j=index ; j<=i+k;j++){
                if(max < number.charAt(j)-'0'){
                    sub = number.charAt(j)+"";
                    max = number.charAt(j)-'0' ;
                    index=j;
                }
                
            }
            
            sb.append(sub);
            index++;
        }
       
        return sb.toString();
    }
}

아무리 그 원인을 모르겠습니다.

feedback

성공 풀이

class Solution {
    
    public String solution(String number, int k) {
        //k개의 수를 제거했을 때얻을 수 있는 가장 큰숫자
        // 문자열 형식의 숫자 nuber 제거할 수의 개수 k
     
        StringBuilder sb = new StringBuilder();
        
        int index=0;
        for(int i=0;i<number.length()-k;i++){        
            int max =0;
            String sub = "";
            for(int j=index ; j<=i+k;j++){
                if(max < number.charAt(j)-'0'){
                    max = number.charAt(j)-'0' ;  
                    index=j;
                }
                
            }
            
            System.out.println(max);
            
            sb.append(max);
            index++;
        }
       
        return sb.toString();
    }
}