[프로그래머스] 큰 수 만들기 -Java

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

코딩테스트 연습 - 큰 수 만들기

---

문제

문제 설명

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

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

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

---

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

풀이

풀이 과정

탐색할 문자열의 인덱스를 저장할 변수와 정답을 만들기 위한 StringBuilder

int idx = 0;
StringBuilder sb = new StringBuilder();

 

전체 길이 - k번 비교할 수 있도록 구간을 나누어 0번 인덱스부터 하나씩 증가시키며 각 구간별로 가장 큰 값을 선택하여 정답 문자열에 추가한다.

이 때 각 구간 안에서 이전에 선택되었던 최대값은 이미 선택이 되었고 그 이전 값들은 제거가 될 값들이기 때문에 제외하고 최대값을 구한다.

예시) "4177252841"

for(int i = 0; i < number.length() - k; i++) {
	// 전체길이 - k 번 반복
    char max = 0; // 최대값 변수
    
    for(int j = idx; j <= i + k; j++) {
		if(max < number.charAt(j)) {
			max = number.charAt(j);
			idx = j + 1;
		}
		sb.append(max);
	}
}

 

4

1

7

7

2

5

2

8

4

1

idx = 0, i = 0
최대값 = 7

4

1

7

7

2

5

2

8

4

1

idx = 3, i = 1, 이전 최대값 2번 인덱스 이하 제외
최대값 = 7

4

1

7

7

2

5

2

8

4

1

idx = 4, i = 2, 이전 최대값 3번 인덱스 이하 제외
최대값 = 5

4

1

7

7

2

5

2

8

4

1

idx = 6, i = 3, 이전 최대값 5번 인덱스 이하 제외
최대값 = 8

4

1

7

7

2

5

2

8

4

1

idx = 8, i = 4, 이전 최대값 7번 인덱스 이하 제외
최대값 = 4

4

1

7

7

2

5

2

8

4

1

idx = 9, i = 5, 이전 최대값 8번 인덱스 이하 제외
최대값 = 1

answer = "775841"

 

만약 최대값을 찾는 중 9가 나오게 되면 이는 무조건 가장 큰 수가 되기 때문에 효율성을 위해 바로 최대값을 추가하고 다음 반복으로 넘어간다

for(int i = 0; i < number.length() - k; i++) {
		char max = 0;
		for(int j = idx; j <= i + k; j++) {
			if(max < number.charAt(j)) {
				max = number.charAt(j);
				idx = j + 1;
			}
			if(max == '9') break;
		}
		sb.append(max);
	}

 

최종 코드

class Solution {
	public String solution(String number, int k) {
		String answer = "";
        
		int idx = 0;
		StringBuilder sb = new StringBuilder();
		
		// 앞에서 부터 (전체길이 - k) 수 중 가장 큰 수 선택
		// 선택한 수 다음 인덱스 부터 탐색 범위를 한칸씩 늘려가며 반복 탐색
		for(int i = 0; i < number.length() - k; i++) {
			char max = 0;
			for(int j = idx; j <= i + k; j++) {
				if(max < number.charAt(j)) {
					max = number.charAt(j);
					idx = j + 1;
				}
			}
			sb.append(max);
		}
        
        return sb.toString();
    }
}

---