2026.09.20
문제 풀이
1차 실행 오류
0.0/100.0
실패
실패 원인 분석
number = 654321 일 때, 아무런 숫자도 없애지 않는 반례가 발생한다.
class Solution {
public String solution(String number, int k) {
int max = 0;
int idx = 0;
for (int i = 0; i < k; i++) {
int n = number.charAt(i) - '0';
if (max < n) {
max = n;
idx = i;
}
}
k -= idx;
if (k == 0) return number.substring(idx);
StringBuilder sb = new StringBuilder();
for (int i = idx; i < number.length() - 1; i++) {
int a = number.charAt(i) - '0';
int b = number.charAt(i + 1) - '0';
if (k > 0 && a < b) { // 현재 자리보다 뒤에 있는 수가 더 클 경우 없애기
k--;
} else sb.append(number.charAt(i));
}
sb.append(number.charAt(number.length() - 1)); // 마지막 수 더하기
return sb.toString();
}
}2차 실행 오류
8.3/100.0
실패
실패 원인 분석
number = 25948763752, k = 5 일 때,
number = 9876752, k = 1 이 된다.
하지만 이 때, number = 987752가 되어야 하지만
현재 코드에서는 가장 마지막 자리를 없애 number = 987675가 된다.
class Solution {
public String solution(String number, int k) {
int max = 0;
int idx = 0;
for (int i = 0; i < k; i++) {
int n = number.charAt(i) - '0';
if (max < n) {
max = n;
idx = i;
}
}
k -= idx;
if (k == 0) return number.substring(idx);
StringBuilder sb = new StringBuilder();
for (int i = idx; i < number.length() - 1; i++) {
int a = number.charAt(i) - '0';
int b = number.charAt(i + 1) - '0';
if (k > 0 && a < b) { // 현재 자리보다 뒤에 있는 수가 더 클 경우 없애기
k--;
} else sb.append(number.charAt(i));
}
sb.append(number.charAt(number.length() - 1));
if (k == 0) return sb.toString();
return sb.substring(0, sb.length() - k).toString();
}
}3차 실행 오류
16.7/100.0
실패
실패 원인 분석
반례 number = 932912, k = 2 일 때,
9912가 나와야 하지만 9392 가 출력된다.
앞자리가 우선적으로 큰 수가 배정이 되어야 한다.
즉, 2 < 9 비교 후 3 < 9 의 비교가 이루어져야 하지만
1 < 2 의 낮은 자리 비교가 계속되기 때문이다.
class Solution {
public String solution(String number, int k) {
int max = 0;
int idx = 0;
for (int i = 0; i <= k; i++) {
int n = number.charAt(i) - '0';
if (max < n) {
max = n;
idx = i;
}
}
k -= idx;
if (k == 0) return number.substring(idx);
StringBuilder sb = new StringBuilder(number.substring(idx));
while(true) {
int before = k;
for (int i = 0; i < sb.length() - 1; i++) {
int a = sb.charAt(i) - '0';
int b = sb.charAt(i + 1) - '0';
if (k > 0 && a < b) { // 현재 자리보다 뒤에 있는 수가 더 클 경우 없애기
k--;
sb.deleteCharAt(i);
i--;
}
}
if (k == 0) return sb.toString();
int after = k;
if (before == after) break; // 계속 반복 해도 변화가 없을 때
}
return sb.substring(0, sb.length() - k).toString();
}
}나의 코드
소요 시간: 1시간 37분
시간 복잡도:
class Solution {
public String solution(String number, int k) {
int max = 0;
int idx = 0;
for (int i = 0; i <= k; i++) {
int n = number.charAt(i) - '0';
if (max < n) {
max = n;
idx = i;
}
}
k -= idx;
if (k == 0) return number.substring(idx);
StringBuilder sb = new StringBuilder(number.substring(idx));
for (int i = 0; i < sb.length() - 1; i++) {
int a = sb.charAt(i) - '0';
int b = sb.charAt(i + 1) - '0';
if (k > 0 && a < b) { // 현재 자리보다 뒤에 있는 수가 더 클 경우 없애기
k--;
sb.deleteCharAt(i);
i = 0;
}
}
if (k == 0) return sb.toString();
return sb.substring(0, sb.length() - k).toString();
}
}AI 코드
시간 복잡도:
코드 분석
해당 코드는 "가장 큰 수가 최대한 앞자리로 갈 수 있게" 수를 옮기는 데에 있다.
수를 스택에 계속 삽입하다가, 현재 스택의 top에 있는 숫자보다 큰 수가 들어오면
원래 스택에 들어있던 수를 반복적으로 제거하며,
큰 수가 최대한 앞으로 오게 설계한다.
class Solution {
public String solution(String number, int k) {
StringBuilder stack = new StringBuilder();
for (char c : number.toCharArray()) {
// 가장 큰 수가 최대한 앞자리로 갈 수 있도록 높은 자리의 작은 수 제거
while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) < c) {
stack.setLength(stack.length() - 1);
k--;
}
stack.append(c);
}
stack.setLength(stack.legnth() - k);
return stack.toString();
}
}문제 풀이 후기
문제를 풀었음에도 불구하고 너무나도 답답하다.
스택을 활용한 문제라는 것은 깃허브의 풀이 기록에서 보았다.
그러나 이걸 스택을 써서 어떻게 푸는거야? 하고 다른 방식으로 풀었다.
어떻게 푸는지 알려줘도 풀 방법이 생각이 안나는 그 사실에 너무 화가 난다.
천천히 꾸준히 나아간다고 하지만 나아가고 있는지 잘 모르겠다.
뭔가 Level 2 정답률 50% 대의 문제를 푸는 과정에서 벽에 막힌 기분이 든다.
