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

---

🤦‍♂️ 실패한 풀이

처음에는 itertools의 combinations 함수를 이용하여 문제를 풀었다.

from itertools import combinations

def solution(number, k):
    answer = '0'
    for combi in combinations(number, len(number) - k) :
        combinumber = ''.join(combi)
        if int(combinumber) > int(answer) :
            answer = combinumber
    return answer

하지만 위 코드는 테스트케이스는 모두 통과했지만 채점할때 시간초과가 뜬다...ㅠ

 

 

🙋‍♀️ 정답

combinations 함수가 실패했으니문제가 탐욕법에 속해있기 때문에 앞에서부터 작은 수를 지워나가는 식으로 만들어보자는 생각에 문제를 풀어보았다.

하지만 왜인지 모르게 12번 케이스를 통과하지 못해서 질문하기쪽을 찾아보니..

같은숫자가 여러개 있는 경우 k값이 줄어들지 않아 문제가 생기는듯했다. 😥

 

그렇게 계속해서 앞에서부터 작은 수를 지워나가는 식으로 풀다가 접근을 잘못하고있는것같다는 생각에 다른 사람들의 풀이를 찾아보니..

Stack을 이용하여 앞에서부터 작은값을 없애주면 된다는 풀이를 보게되었고, 아래의 코드로 문제를 풀수있었다.

 

def solution(number, k):
    stack = []
    leng = len(number) - k
    for n in number :
        # 지울수 있고, 새로 넣을 값이 stack의 마지막 값보다 크다면 stack의 값들을 계속 지워줌
        while stack and k > 0 and stack[-1] < n :
            stack.pop()
            k -= 1
        stack.append(n) # stack의 값이 없거나 더이상 지울수있는 수가 없거나 위를 통과했다면 그냥 넣기
        
    return ''.join(stack[:leng])

1. number를 앞에서부터 탐색한다. number의 각 숫자는 n이다.

2. stack에 값이 있고, 제거할수 있는 숫자가 아직 있으며, stack의 마지막 값이 stack에 새로 들어갈 n보다 작다면 stack의 마지막 값을 제거한다.

3. 2의 과정을 제거할 숫자가 있을때까지 계속 반복한다.

4. 만약 2의 조건에 해당하지 않는 경우 n을 stack에 추가한다.

5. 2~4의 과정을 number의 모든 수를 빼서 stack에 넣을때까지 확인한다.

6. stack을 조건에 맞게 잘라서 반환한다.

 

이렇게해서 오늘의 문제 끝~

---

탐욕법의 경우 현재 상황에서 가장 최선의 상황을 선택해나가는 것이라고 이론적으로는 알고있다.

하지만 실제로 문제를 풀때는 이론적으로만 아는건 도움이 되지 않았다.

 

Stack도 알고 탐욕법에 대한 것도 알지만 두시간동안 문제 하나로 끙끙대다 결국 해설을 찾아보았으니..결국 중요한건 이론이 아니라 그것을 어떻게 사용하느냐인것같다.

 

프로그래머스에서도 레벨1 문제들은 거의 풀었으니 이제 난이도를 조금씩 올려가면서 응용문제를 풀어봐야겠다 😂