[Programmers] 큰 수 만들기 - Java

문제

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

프로그래머스

 

풀이

2~100만 자리의 숫자가 나올 때, k개의 숫자를 지워서 최대 숫자를 만드는 문제이다.

 

k개를 숫자를 어떻게 지우는게 최대 숫자가 나온다고 할 수 있을까?

1. 첫번째 자리가 높을수록 좋다.

2. 순회하면서 이전에 들어왔던 숫자가 더 작으면 지우는 것이 좋다.

 

2번에서 뭔가 이전에 들어왔던 숫자를 저장해서 다 지운다? => 스택이구나 라는 생각이 들었다.

스택을 사용해서 다 넣고 다 지운다고 해도 200만 연산이니 사용해도 된다고 생각했다.

 

1. 스택이 비어있으면, 그냥 문자를 넣는다.

 

2. 스택이 비어있지 않다 + k가 0보다 크다(지울 수 있다) + 현재 문자가 스택에 제일 최근에 들어온 문자보다 작다 이 3가지 조건을 만족하면 지운다.

=> 순회하면서 이전에 들어왔던 숫자가 더 작으면 지우는 것에 대한 조건이다.

 

3. k번이 다 사용되지 않을 수 있다.

number = "987654321", k = 3이면 지울 수가 없다. 이런 경우 내림차순으로 정렬이 되어 있다는 의미이므로, k번 최근에 들어온 문자들을 모두 삭제한다.

 

4. 스택에 있는 문자들을 꺼내 문자열을 만들어서 반환한다.(두가지 방법이 존재)

 

4-1. 스택에 있는 문자들을 removeLast 메소드를 호출해서 문자열을 만든다.

 

4-2. for-each문을 사용해서 문자들을 읽어서 문자열을 만든다.

 

소스코드

import java.util.ArrayDeque;

class Solution {
    public String solution(String number, int k) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        for (char ch : number.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peekFirst() < ch) {
                stack.removeFirst();
                k--;
            }
            
            stack.addFirst(ch);
        }
        
        while (k > 0) {
            stack.removeFirst();
            k--;
        }
        
        StringBuilder sb = new StringBuilder();
        
        while (!stack.isEmpty()) {
            sb.append(stack.removeLast());
        }
        
        return sb.toString();
    }
}

 

import java.util.ArrayDeque;

class Solution {
    public String solution(String number, int k) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        for (char ch : number.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peekLast() < ch) {
                stack.removeLast();
                k--;
            }
            
            stack.addLast(ch);
        }
        
        while (k > 0) {
            stack.removeLast();
            k--;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (char ch : stack) {
            sb.append(ch);
        }
        
        return sb.toString();
    }
}

 

실행결과

remove 메서드로 문자열 만들었을때 실행결과

for-each로 문자열을 만들었을때

성능 비교

테스트	remove 방식	for-each 방식	개선 효과
평균 실행 시간(ms)	14.92	11.65	21.9% 빠름
평균 메모리 사용량(MB)	86.80	86.67	0.15 감소

 

빨라진 이유

remove 메서드를 사용하는 방식은 스택이 비어 있는지 체크하는 연산 + 포인터와 사이즈를 바꾸고, reference count가 0인 객체를 GC가 메모리 할당을 해제하는 연산이 있다. 하지만 stack에 있는 데이터를 읽는 연산인 이와 같은 연산을 하지 않아 실행 시간이 더 빠르다.