[프로그래머스/42883] 큰 수 만들기

19 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이(실패)
  • 두 번째 풀이(성공)

☑️ 문제

프로그래머스 42883

☑️ 풀이

첫 번째 풀이(실패)

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String[] arr = number.split("");
        
        for (int i = 0; i < arr.length; i++) {
            if (k == 0) {
                break;
            }
            
            if (arr[i].equals("x")) {
                continue;
            }
            
            int end = 0;
            for (int j = i + 1; j < i + 1 + k; j++) {
                if (Integer.parseInt(arr[i]) < Integer.parseInt(arr[j])) {
                    end = j;
                    break;
                }
            }
            
            if (end != 0) {
                k -= (end - i);
                for (int j = i; j < end; j++) {
                    arr[j] = "x";
                }
            }
        }
        
        if (k > 0) {
            for (int i = arr.length - 1; i > arr.length - 1 - k; i--) {
                arr[i] = "x";
            }
        }
                
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            if (!arr[i].equals("x")) {
                sb.append(arr[i]);
            }
        }
        
                
        return sb.toString();
    }
}

• 우선, 주어진 number 를 배열로 변환한 뒤 앞에서부터 k개씩 탐색하면서 현재 숫자보다 큰 숫자가 나오면 현재 인덱스부터 큰 숫자의 인덱스 전까지 범위의 숫자를 x 로 변환한다. (삭제한 걸 표시)
  • 만약 k 가 남는다면 남은 k 개 만큼 뒤에서 추가로 삭제해준다.
  • x 가 아닌 숫자들만 모아 최종적으로 반환하였다.

• 두 개의 테케에서 런타임에러가 발생했다.

  

  • String 배열을 사용하여 메모리가 낭비되었기 때문에 StringBuilder 를 사용하도록 개선했다.
  • 삭제된 문자를 x 로 치환하는 방식이 비효율적이기 때문에 StringBuilder의 deleteCharAt() 메서드를 사용해 직접 삭제하는 방식을 사용하였다.

두 번째 풀이(성공)

//시간: 1774.34ms
//메모리: 79.7MB

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        int idx = 0;

        while (k > 0 && idx < sb.length() - 1) {
            if (sb.charAt(idx) < sb.charAt(idx + 1)) {
                sb.deleteCharAt(idx);
                k--;
                if (idx > 0) idx--;
            } else {
                idx++;
            }
        }

        if (k > 0) {
            sb.delete(sb.length() - k, sb.length());
        }

        return sb.toString();
    }
}

• String 배열 대신 StringBuilder 를 사용하여 메모리를 절약하였다.
• 이전의 로직과는 다르게 현재 숫자가 다음 숫자보다 작으면 삭제하도록 했고, 삭제 후에는 이전 숫자를 다시 비교하기 위해 idx값을 하나 줄였다.