[알고리즘 문제풀이] 프로그래머스 - 큰 수 만들기

yourjin·2022년 2월 27일
level2알고리즘탐욕법(Greedy)
0

알고리즘 문제풀이

목록 보기
3/28
post-thumbnail

TIL (2022.02.04)

➕ 오늘 푼 문제

프로그래머스 - 큰 수 만들기

➕ 아이디어

단순 구현 - O(n2n^2)

이 방법을 사용하면 Python에서 통과하지 못한다. 그리고 n2n^2은 효율성 측면에서도 좋지 못하다.

  • k개를 빼는 문제이지만 len(number)-k개를 뽑는 문제로 바꿔서 생각한다.
  • 특정 범위에서 가장 큰 수를 len(number)-k개 뽑으면 가장 큰 수를 만들 수 있다.
    • 범위를 잡아야 하는 이유
      • n = len(number) - k 라고 하자
        우리는 n개의 숫자를 뽑아야 한다. 뽑으려는 숫자가 특정 범위 A에 있다고 가정하자.
        첫번째 숫자라면 A의 오른편에는 n-1개의 숫자가 있어야 한다. A에서 가장 오른쪽에 있는 숫자가 가장 큰 수라면, n개의 숫자를 뽑기 위해선 최소 n-1개 이상의 숫자가 남아있어야 하기 때문이다.
    • 범위 지정 조건
      • 선택할 수 있는 범위는 선택한 숫자 오른편에 아직 선택해야 할 개수와 같거나 많은 숫자가 남아 있어야 한다.
      • 조건이 k만큼의 수를 제거했을 때 가장 큰 수이기 때문에, 범위는 탐색해야 하는 문자의 시작(index)부터 앞으로 이어 붙여야 할 문자의 길이 -1이 뒤에 남는 index까지 탐색을 해야 한다.

Stack 활용 - O(nn)

  • 핵심 아이디어
    • 리스트를 순차 탐색하면서 내 앞에 있는 나보다 작은 값들을 빼는 것이다. k번 빼면 종료한다.
  • 구현 방법
    • 스택의 마지막 값이 push 할 값보다 작다면, 크거나 같은 값이 나올 때까지 값들에 대해서 pop을 한다.
    • 만약에 pop을 한 횟수가 k보다 작을 경우, 남은 횟수 만큼 뒤에서 빼준다.
      • 순차 탐색 하면서 나보다 작은 숫자들은 다 스택에서 빼주기 때문에, 뒤로 갈수록 더 작은 숫자들이다. 앞에 아직까지 남아 있었다는 것은 나보다 큰 숫자임을 의미하기 때문이다.

➕ Java 코드

2번 아이디어

import java.util.*;

class Solution {
    public static String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        for(int i=0; i<number.length(); i++){
            int n = number.charAt(i) - '0';

            while(!stack.isEmpty() && (int)stack.peek() < n){
                if(k > 0){
                    stack.pop();
                    k -= 1;
                }else{
                    break;
                }
            }

            stack.push(n);
        }

        // k가 남아있다면, 남은 만큼 뒤에서 빼준다.
        for(int i=0; i<k; i++){
            stack.pop();
        }

        // 스택 문자열로 변환
        for(int i=0; i<stack.size(); i++){
            answer.append(stack.elementAt(i));
        }

        return answer.toString();
    }
}

(참고) 1번 아이디어

```java
public static String solution(String number, int k) {
    StringBuilder answer = new StringBuilder();
    int start = 0, end = 0;
    int max_num, max_idx;

    // number.length()-k개의 큰 수를 뽑음
    for(int i=0; i<number.length()-k; i++){
        max_num = -1; max_idx = 0;
        end = k+i+1;    // 끝 범위: 오른쪽에 앞으로 이어 붙여야 할 문자의 길이 -1개를 남기는 위치

        // 특정 범위에서 최댓값을 뽑음
        for(int j=start; j<end; j++){
            int now_num = number.charAt(j) - '0';
            if(max_num < now_num){
                max_num = now_num;
                max_idx = j;
            }
        }

        start = max_idx+1;  // 시작 범위: 이전 최댓값 위치 + 1
        answer.append(max_num);
        
    }
    return answer.toString();
}
```

➕ Python 코드

2번 아이디어

def solution(number, k):
    stack = []

    for n in number:
        # n 앞에 있는 수 중 n보다 작은 숫자를 뺀다.
        while stack and stack[-1] < n:
            if k > 0:
                stack.pop()
                k -= 1
            else:
                break
            
        stack.append(n)

    if k > 0:
        # 아직 다 빼지 못했다면 뒤에서부터 뺀다
        stack = stack[:-k]

    return ''.join(stack)

(참고) 1번 아이디어

이 코드는 시간 초과로 통과하지 못한다.

 def solution(number, k):
     answer = ''
     start, end = 0, 0
 
     # len(number)-k개의 큰 수를 뽑는다.
     for i in range(0, len(number)-k):
         max_num, max_idx = -1, 0
         end = k + i + 1
         
         # 범위는 이전 최대값 다음 수(=start)에서 len(number)-남은 숫자 개수(=end)까지로 잡는다.
         for j in range(start, end):
             if max_num < int(number[j]):
                 max_num = int(number[j])
                 max_idx = j
         
         answer += str(max_num)
         start = max_idx + 1
 
     return answer

➕ 궁금한 내용 및 소감

  • 처음에 아이디어 생각하기도 너무 힘들고, 이해하기도 힘들었던 문제였다. 몇일 쪼개서 본 것 같다. 문제에서 나온 조건을 다른 방법으로 틀어서 생각할 수 있는 사고력을 키워야 할 것 같다.
    • k개의 문자를 삭제 한다
      • = 전체 길이 - k 개의 문자를 뽑는다.
      • = 순차 탐색하며, 나보다 작은 숫자들을 k개 뽑는다.
  • 자바도 빠른 속도는 아니지만 파이썬 보다는 빨라서 간혹 자바에서는 통과하지만, 파이썬에서는 시간 초과가 뜨는 알고리즘들이 있는 것 같다. 효율적인 측면에서는 파이썬으로 연습하는 것이 좋을 것 같다.

➕ 참고 문헌

profile
yourjin
make it mine, make it yours
이전 포스트

[알고리즘 문제풀이] 프로그래머스 - 조이스틱

다음 포스트

[알고리즘 문제풀이] 프로그래머스 - 구명보트

0개의 댓글