8. 큰 수 만들기 ★★ (그리디, 스택)

출처 : https://junebee.tistory.com/43

[LG 전자] VS 연구소 SW R&D 신입사원 채용 지원 후기

 

2022 LG SW 코테에서 비슷한 유형의 문제가 출제되었다고 한다. 

 

유형 : 그리디 (greedy)

풀이 시간: 10분 정도 (처음) -> 인터넷 참고. 

 

1번 코드 : 시간 초과 

def solution(number, k):
    numberlist = list(number)
    for i in range(k):
        for j in range(len(numberlist)-1):
            if numberlist[j] < numberlist[j+1]:
                numberlist.pop(j)
                break
    return ''.join(numberlist)

 

처음 제출한 코드는 정확도 75%. 마지막 tc는 틀렸고 두 개 tc에서 시간 초과

시간 복잡도가 O(N*K) 여서 그런 것 같다...

 

2번 코드 : stack 사용 

인터넷 서칭을 통해, 스택을 이용해서 풀었다. 

def solution(number, k):
    numberlist = list(number)
    stack = []
    
    for j in range(len(numberlist)):
        while (k > 0) and len(stack) != 0 and numberlist[j] > stack[0]:
            stack.pop(0)
            k -= 1
        stack.insert(0, numberlist[j])
    if k > 0:
        for i in range(k):
            stack.pop(0)
    stack.reverse()
    return ''.join(stack

 

1) k> 0이고

2) 스택의 길이가 0이 아니며

3) numlist[j], 즉 현재 원소보다 더 작은 값이 stack의 첫 번째 원소일 때 넣는다. 

 

이렇게 하면 자릿수가 큰 곳에 가능한 조합 중 가장 큰 숫자가 위치하게 되므로 최적화를 할 수 있다.  

만약 결과값이 k보다 길다면, 아랫 자리수를 삭제한다. 

 

9번, 10번 case에서 time out이 나서 더 최적화를 해 본다. 

 

3번 코드 

def solution(number, k):
    numberlist = list(number)
    stack = []
    
    for num in numberlist:
        while (k > 0) and len(stack) > 0 and num > stack[len(stack)-1]:
            del stack[len(stack)-1]
            k -= 1
        stack.append(num)
    if k> 0:
        stack = stack[:len(stack)-k]
    return ''.join(stack)

 

이제야 통과되었다. 

12번째 case에서 오류가 나곤 했는데, 이 오류는 마지막 k개를 제거하는 과정에서 앞선 code와 달리 stack을 뒤집었기 떄문에 뒷부분에서 k개를 제거해주어야 하는데 앞부분에서 k개를 제거해 발생한 오류. 

 

그리고 생각보다 pop, insert의 시간 복잡도가 높다.

append와 O(1)인 del을 사용해 주니 시간 초과 없이 무사히 통과되었다. 

 

여러모로 충격적인 문제였다. 화이팅...