[프로그래머스] Lv.2 큰 수 만들기 (Greedy 알고리즘 , 탐욕, ,StringBuilder, Java)

 

문제설명

나의 풀이

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(); 
        int start = 0 ;
        int idx = 0;
        
        for(int i = 0 ; i < number.length() - k ; i++){
            char max = '0';
            
            //현재 구간에서 가장 큰 값 찾기
            for(int j = start ; j <= i+k ; j++){
                if(max < number.charAt(j)){
                    max = number.charAt(j);
                    idx = j+1; //다음 검색을 위한 인덱스 업데이트
                }                
            }
            sb.append(max);
            start = idx; //다음 구간의 시작 인덱스 설정
        }
        
        return sb.toString();
    }
}

 

이번 문제는 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제입니다.

 

예를 들자면 "1924"일 때 [19,12,14,92,94,24]가 되는데 여기서 가장 큰 수인 94가 정답입니다. 

 

숫자를 하나씩 제거하면서 비교하는 것이 아니라 이 문제에서는 매번 가능한 범위 내에서 가장 큰 숫자를 선택하는 것이 최선의 선택입니다.

 

문자열에 붙이면 시간이 오래걸리기 때문에 StringBuilder 클래스를 사용합니다. 그리고 number.length() - k는 최종적으로 구성할 숫자의 길이입니다.

 

 

그리고 각 구간에서 가장 큰 값을 찾습니다. 여기서 중요한 점이 바로 두 번째 for문의 j의 시작위치입니다. 

 

만약 각 구간에서 최대값을 찾고 해당 최댓값의 인덱스 다음 값부터 구간을 설정해야 합니다.

 

이는 그리디 알고리즘의 핵심 원리인 "현재 단계에서 가장 최선의 선택을 하고, 그 선택 이후의 부분을 다시 새로 고려한다"에 기반합니다.

 

각 구간에서 구한 max값을 StringBuilder에 append() 메서드로 추가해 주고, 각 구간의 인덱스를 최댓값 다음 값으로 업데이트해줍니다.

 

그리고 마지막으로 StringBuilder 클래스의 toString() 메서드를 사용하여 문자열로 변환을 하여 마무리합니다.

 

---

 

 

• 첫 번째 구간 (인덱스 0부터 시작, 길이 3):
  • 현재 선택할 수 있는 구간은 "192"입니다.
  • 최댓값은 '9'입니다. 따라서 "9"를 선택합니다.
  • 다음 구간의 시작 인덱스는 1이 됩니다.
• 두 번째 구간 (인덱스 1부터 시작, 길이 2):
  • 이전에 선택된 최대값 '9' 이후의 구간은 "24"입니다.
  • 이 구간에서 최대값은 '4'입니다. 따라서 "4"를 선택합니다.

---

예시: "1231234", k = 3

• 첫 번째 구간 (인덱스 0부터 시작, 길이 4): 
  • 현재 선택할 수 있는 구간은 "1231"입니다.
  • 가장 큰 숫자는 '3'입니다. 따라서 "3"을 선택합니다.

• 두 번째 구간 (인덱스 1부터 시작, 길이 4):
  • 이전에 선택된 최대값 '3' 이후의 구간은 "2312"입니다.
  • 가장 큰 숫자는 '3' 이후의 '2'입니다. 따라서 "2"를 선택합니다.

• 세 번째 구간 (인덱스 2부터 시작, 길이 4):
  • 이전에 선택된 최대값 '3' 이후의 구간은 "3123"입니다.
  • 가장 큰 숫자는 '3' 이후의 '1'입니다. 따라서 "1"을 선택합니다.

• 네 번째 구간 (인덱스 3부터 시작, 길이 4):
  • 이전에 선택된 최대값 '3' 이후의 구간은 "1234"입니다.
  • 가장 큰 숫자는 '3' 이후의 '4'입니다. 따라서 "4"를 선택합니다.

---

 

for(int i = 0 ; i < number.length() - k ; i++){
            for(int j = i ; j <= i+k ; j++){
                System.out.print(number.charAt(j) + " ");
            }
        }

 

이해를 돕기 위해 최종적으로 구할 숫자의 길이인 첫 번째 for문과 각 구간의 최댓값을 구하는 두 번째 for문을 안에 내용 없이 가져왔습니다.

 

위와 같이 코드를 작성한다면 결과는 다음과 같습니다.

1 2 3 1 
2 3 1 2 
3 1 2 3 
1 2 3 4

 

이는 예제 2번을 각 구간을 나타낸 것입니다.

 

그리디 알고리즘의 원칙에 따라 각 구간에서 최댓값을 찾고 최대 값 다음 값부터 새로 비교해야 하기 때문에 각 구간의 시작점인 start를 업데이트해야 하는 것입니다.

 

그러면 위 코드의 두 번째 for문에서 int j = i 가 아닌 start로 설정해야 하는 것입니다.

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

[JAVA] char에서 String으로 변환하기 (value of() , charAt())