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

문제 링크

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

프로그래머스

 

접근 방식1 (틀림)

1. 입력값인 number를 정렬

2. 정렬된 값에서 순서대로 작은 숫자 k를 삭제한다.

3. 값을 지우고 남은 숫자들을 원래 순서대로 다시 조합한다.

풀이 코드1  (틀림)

def solution(number, k):
    answer = ''
    numbers = []
    
    for idx, num in enumerate(number):
        numbers.append((idx, int(num)))
        
    numbers.sort(key = lambda x : (x[1], x[0]), reverse = True)
    
    for _ in range(k):
        numbers.pop()
        
    numbers.sort(key = lambda x : x[0])
        
    for i in range(len(numbers)):
        answer += str(numbers[i][1])
        
    return answer

 

- 문제의 1, 2번 예시는 맞는데 3번 예시는 틀림

-> 작은수를 k개 빼는 게 아니라 자릿수의 대소관계를 생각해야 함.

 

접근방식 2 (시간초과)

1. number의 맨 앞자리와 바로 뒷자리를 비교

2. 앞자리가 더 작을경우 삭제

3. 위 과정을 k번 반복

4. 앞자리가 더 작은 경우가 없으면 number의 맨 뒤 숫자 삭제

 

풀이코드 2 (로직은 맞음, 시간초과)

def solution(number, k):
    answer = ''
    front_num = ''
    back_num = ''
    
    # i가 i+1보다 커야만 함, 작으면 지워져야함
    for count in range(k):
        for i in range(len(number)-1):
            if int(number[i]) < int(number[i+1]):
                front_num = number[:i]
                back_num = number[i+1:]
                number = front_num + back_num
                break
        else:
            number = number[:-1]
            
    return number

 

- 로직은 맞는데, 시간초과가 남

- stack을 이용한 아래 코드로 개선

 

풀이코드3 (정답)

def solution(number, k):
    answer = ''
    stk = []
    
    for num in number:
        while stk and stk[-1] < num and k > 0:
            stk.pop()
            k -= 1
        stk.append(num)
    
    answer = "".join(stk)
    
    if k > 0:
        answer = answer[:-k]
    
    return answer

 

주의사항

- number가 "333222111"처럼 맨 앞에서 맨 뒤까지 계속해서 같거나 작아지는 경우만 있는 경우 while을 들어가지 못함

--> 이런 경우 맨 뒷자리를 지우면 되기 때문에 남은 k만큼 뒤를 지워주면 됨