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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3 

코딩테스트 연습 - 큰 수 만들기

 

풀이 

- 처음엔 i , i+1 비교해서 풀려고 했는데 

"4177252842" 처럼 처음부터 끝까지 한바퀴 돌았는데도 k의 개수가 남아있을 경우를 해결하지 못했다.

- 다른 블로그를 보니 스택을 사용해서 풀었다.

- 스택에서 나올 숫자가 넣을 숫자보다 작으면 스택에서 숫자를 빼낸다. 숫자 빼낼 때마다 k-1 하고 k가 0보다 클 때까지 숫자 빼기를 반복한다. 

- k의 개수가 남았으면 남은 개수만큼 숫자를 뺀다.

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

  for i in number :
    
    while stack and i > stack[-1]:
      if k > 0:
        stack.pop()
        k -=1
      else:
        break
    
    stack.append(i)

  if k > 0 :
    for _ in range(k):
      stack.pop()
    
  answer = "".join(stack)

  return answer

+ 2022.04.21 다시 풀이 

앞에 위치할수록 숫자가 커야하므로, 

현재 위치의 숫자가 다음 숫자보다 작으면 제거하는 방식으로 구현하였다. 

- 이 때 만약에 제거 되었다면, 인덱스 위치를 하나 줄여서 다시 다음 숫자와 비교하도록 하였다.

하나만 줄여도 되는 이유는 앞에는 이미 다 현재 위치숫자보다 크기 때문. 

 

- 만약 현재위치가 더 크다면 인덱스 1 증가 

 

- 만약 인덱스가 숫자의 길이와 같다면, 끝까지 비교했는데 앞자리 숫자가 모두 뒷자리수들보다 크다는 것이므로 맨 끝 숫자 제거 후 반복문 중단 -> 이 부분을 고려해주지 못하고 아직 제거할 숫자가 남았으면 계속 인덱스를 0으로 설정하여 처음부터 비교해주었는데, 

n = "654321" , k= 1 인 테스트 케이스에 대하여 반복문이 종료되지 않아 런타임 에러가 발생하였다. 

def solution(number, k):
    # 제거한 숫자의 개수 
    cnt = 0 
    # index 
    idx = 0 
    
    while True :
        # 현재 위치의 숫자가 다음 숫자보다 작으면 제거 
        if number[idx] < number[idx + 1]:
            number = number[:idx] + number[idx+1:]
            cnt += 1
            if idx != 0 :
                # 앞에서부터 다시 비교 
                idx -= 1 
        else :
            idx += 1 
            # 끝까지 비교했는데 다 앞 숫자가 크면 
            if idx == len(number) - 1 :
                # 맨 끝 숫자 제거 
                number = number[:-1]
                break 
            
        # 제거 다 했으면 
        if cnt == k :
            break 
        
    return number