들어가며
해당 빈출 문제집 문제를 하나씩 푸는 중이다.
살짝 주춤하거나 막힌 것 위주로 포스팅을 한다.
문제
- 문제: 크게만들기, 큰 수 만들기
- 레벨: [백준] 골드3, [프로그래머스] level 2
- 숫자가 문자열로 주어지고, 앞에서부터 작은 수를 K개 지워나가 만들 수 있는 수 중에서 가장 큰 수를 출력한다.
접근 방식: 그리디 + 스택
숫자 문자열을 하나씩 비교해 나가며 최댓값을 구한다❓ 스택 떠올리자
핵심 로직: 스택 구현
- 손으로 하나씩 답을 구해봤을 때, 뒤에 있는 수보다 작다면 일단 지운다.
- 높은 자리수의 수가 커질수록 큰 수가 된다.
- 문자열의 왼쪽부터 확인하고, 판별이 끝난 아이들을 모아두며 이들을 확인해나간다.
- 현재 값을 기준으로 이전 값은 현재 값보다 작은 경우, 크거나 같은 경우로 나뉜다.
- 이전 값이 더 작은 경우 그 아이를 뺀다. 이때 pop한 것을 카운팅(cnt) 해줌. 그리고 다음 이전값을 또 반복하여 확인한다.
- 이전 값이 크거나 같은 경우 현재 값을 넣어준다.
cnt == K가 되면 중단한다.
ex. 1924 k=2
(empty) 1[924]
-> 1 [924] push 1, cnt:0
1 9[24]
-> 9 [24] pop 1, push 9, cnt:1
9 2[4]
-> 92 [4] push 2, cnt:1
[9]2 4(empty)
-> [9]4 (empty) pop 2, push 4, cnt:2 -> break
ans: 94
만약 여기서 k=3 이었다고 해도 더 이상 input 값이 없으므로 판별이 완료된 값에서 처리해주어야 함.
따라서 94라는 답에서 우리는 N - K 인 1자리만 필요하므로
그때 답은 9.
ex. 1231234 k=3
(empty) 1[231234]
-> 1 [231234] push 1, cnt:0
1 2[341234]
-> 2 [341234] pop 1, push 2, cnt:1
2 3[41234]
-> 3 [41234] pop 2, push 3, cnt:2
3 4[1234]
-> 4 [1234] pop 3, push 4, cnt:3 -> break
ans: 41234결과값 처리
- 스택에 들어있는 값을
pop하지 않고 그대로 순회하며 빼내고, 아직 판별하지 않은input도 역시 차례대로ans에 담아준다.
- 이때 주의 점은, cnt가 K에 못미치고 순회가 끝났을 경우, 아직 덜 제외한 것이 되므로 결과 값의 뒷자리에서
K-cnt만큼 제외해줘야 한다. 뒷자리를 제외하는 것이 가장 큰 값이 되므로.
- 다시말하면 정답 문자열의 인덱스
0~(N-K)까지가 답이 된다.- 이런 부분은 답을 구해놓고, 문자열로 처리해주는 것이 편함.
통과 코드
package solution;
import java.io.*;
import java.util.*;
public class BOJ2812_크게만들기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st= new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Queue<Integer> input = new LinkedList<>();
String str = br.readLine();
for (int i = 0; i < N; i++) {
input.add(str.charAt(i) - '0');
}
Stack<Integer> stack = new Stack<>();
int cnt = 0;
while(!input.isEmpty() && cnt < K) {
Integer now = input.poll();
while(true) {
if(stack.empty()) {
stack.push(now);
break;
}
Integer prev = stack.peek();
if(prev < now) {
stack.pop();
cnt++;
if(cnt == K) {
stack.push(now);
break;
}
} else {
stack.push(now);
break;
}
}
}
StringBuilder ans = new StringBuilder();
for(Integer num : stack) ans.append(num);
while(!input.isEmpty()) ans.append(input.poll());
System.out.println(ans.substring(0, N - K));
}
}
추가) 프로그래머스 큰 수 만들기 java
import java.util.*;
import java.io.*;
class Solution {
public String solution(String number, int k) {
Stack<Integer> stack = new Stack<>();
int cnt = 0;
int idx = 0;
for(int i = 0; i < number.length(); i++) {
Integer now = number.charAt(i) - '0';
while(true) {
if(cnt == k || stack.empty()) {
stack.push(now);
break;
}
Integer left = stack.peek();
if(left < now) {
stack.pop();
cnt++;
} else {
stack.push(now);
break;
}
}
idx = i;
if(cnt == k) break;
}
StringBuilder tmp = new StringBuilder();
for(Integer n : stack) {
tmp.append(n);
}
String answer = String.valueOf(tmp);
if(idx < number.length() - 1) answer += number.substring(idx + 1, number.length());
return answer.substring(0, number.length() - k);
}
}결과
- 소요 시간: 40m
- 스택 자료구조와 접근 방향은 바로 캐치함.
while(true)에서 break 거는 코드가 잦아서 디버깅하는데 시간 소요가 많이 들었다.- 조건이 구간마다 있을 때는 조금 지저분 해도 한 번에 처리하려고 하지 말자. 오류가 많음.. 정확하게 푸는 것이 제일 중요하니까 함부로 if문 옮기지 않기.
마치며
최근 스택, 그리디를 자주 푸니 방향을 금방 잡을 수 있어서 기분이 조타 *^^*
개발의, 개발에 의한, 개발을 위한 기록장