📝 큰 수 만들기 (Level 2)
🔹Python
탐욕법(Greedy)
큰 수 만들기
- 내가 쓴 풀이
from itertools import combinations
def solution(number, k):
answer = ''
nums = []
temp = []
for i in range(len(number)): # number의 각 자리수를
nums.append(number[i]) # nums 리스트에 추가해서
combi = list(combinations(nums, len(number)-k)) # number의 길이에서 제거할 수의 개수인 k를 뺀만큼 조합을 구한다.
for com in combi: # combi에 있는 조합된 수들을
letter = ''
for i in range(len(com)):
letter += com[i] # 문자 하나로 만들어준다.
temp.append(letter) # temp 배열에 문자를 추가해놓고
return max(temp) # 가장 큰 수 찾기
테스트 케이스는 통과했는데 시간 초과 걸림 -> 절망ㅜ
combinations 함수가 너무 오래 걸리는건가 ..?
문제점
-
조합(combinations) 사용:
itertools.combinations를 사용하여 모든 가능한 조합을 생성하고, 각 조합을 문자열로 변환한 후 그 중 가장 큰 숫자를 선택하는 방식입니다.
조합의 수는 C(n, n-k)로 계산되며, n이 클수록 조합의 수가 급격히 증가합니다. 이는 시간 복잡도를 매우 크게 만듭니다. 예를 들어, number의 길이가 10이고 k가 5이면, 조합의 수는 C(10, 5) = 252가 됩니다. 길이가 100이라면 조합의 수는 훨씬 더 커져서 시간 초과가 발생합니다. -
모든 조합을 탐색:
모든 가능한 조합을 생성하고 그 중 가장 큰 값을 찾는 방식은 비효율적입니다. 최악의 경우, 조합의 수가 매우 많아져 메모리와 시간 모두 비효율적입니다.
해결 방안:
이 문제는 스택을 사용하여 효율적으로 해결할 수 있습니다. 목표는 숫자를 왼쪽에서 오른쪽으로 탐색하면서 가능한 한 큰 수를 유지하는 것입니다.
- gpt 코드
def solution(number, k):
stack = []
for num in number:
while stack and k > 0 and stack[-1] < num:
stack.pop() # 스택의 top에 있는 숫자가 현재 num보다 작으면 제거
k -= 1
stack.append(num)
# 만약 k가 0보다 크다면, 끝에서 k개를 자른다.
if k > 0:
stack = stack[:-k]
return ''.join(stack)만약 k가 0보다 크다면, 끝에서 k개를 자른다. 여기 부분이 이해가 안가서 gpt한테 물어봤다.
-
일곱 번째 숫자 1 처리:
stack = [7, 6, 5, 4, 3, 2]인데, stack의 top(2)이 현재 숫자 1보다 크므로 아무것도 제거하지 않고 1을 스택에 추가합니다.
stack = [7, 6, 5, 4, 3, 2, 1]
k = 3 -
남은 k 처리:
지금까지 숫자를 모두 순회했지만 k = 3이 남아 있습니다. 즉, 아직 3개의 숫자를 더 제거해야 합니다. 이 경우, 스택의 끝에서 k개의 숫자를 제거합니다. 이는 우리가 가능한 한 큰 숫자를 만들기 위해 뒤에서부터 작은 숫자를 제거하는 것입니다.
스택의 끝에서 3개의 숫자를 제거하면, 스택은 [7, 6, 5, 4]가 됩니다.
''.join(stack): 리스트에 있는 문자열 요소들을 하나의 문자열로 합치는 방법
🔸Java
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
Stack<Character> stack = new Stack<>();
// 모든 문자에 대해 반복
for (int i = 0; i < number.length(); i++) {
char num = number.charAt(i);
// 스택의 top에 있는 숫자가 현재 num보다 작으면 제거
while (!stack.isEmpty() && k > 0 && stack.peek() < num) {
stack.pop();
k--;
}
stack.push(num);
}
// 만약 k가 0보다 크다면, 스택의 끝에서 k개를 제거
while (k > 0) {
stack.pop();
k--;
}
// 스택에 있는 문자들을 하나의 문자열로 합침
StringBuilder answer = new StringBuilder();
for (char num : stack) {
answer.append(num);
}
return answer.toString();
}
}설명
-
Stack 사용:
Stack를 사용하여 각 문자를 스택에 저장합니다. -
반복문:
number의 각 문자를 반복하며 charAt(i)로 현재 문자를 가져옵니다. while 문에서 !stack.isEmpty()를 사용해 스택이 비어 있지 않은지 확인하고, stack.peek()으로 스택의 top에 있는 문자를 확인한 후 num과 비교하여 조건이 만족하면 pop()으로 제거합니다. -
남은 k 처리:
스택을 모두 처리한 후에도 k가 남아있을 수 있으므로, 남아있는 k만큼 스택의 끝에서 문자를 제거합니다.
-
문자열 생성:
StringBuilder를 사용하여 스택에 있는 문자들을 하나의 문자열로 합칩니다. 이는 StringBuilder가 문자열을 효율적으로 조작할 수 있기 때문에 사용됩니다. -
결과 반환:
최종적으로 answer.toString()을 호출하여 결과를 문자열로 반환합니다.
주의 사항
- Java의 Stack 클래스는 Character 자료형을 사용하므로, 스택에 Character를 저장하고 처리합니다.
- peek() 메소드는 스택의 top 요소를 반환하며, pop() 메소드는 top 요소를 제거합니다.
- StringBuilder는 문자열 조작 시 성능이 뛰어나므로, 문자열을 누적하는 데 적합합니다.
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}