[Programmers] 큰 수 만들기

1. 개념 : 탐욕법 (Greedy Algorithm)

현재 상황에서 가장 좋은것(최선의 선택)만을 선택하는 알고리즘.
매 순간 가장 좋아 보이는 것을 선택하며, 최종 결과가 최적해 보장 X (작성 후 검증 필요)
대표 유형 : 거스름돈 문제, 다익스트라 알고리즘

2. 풀이

2.1 조합 활용

- 코드

python

닫기 줄바꿈

from itertools import combinations

def solution(number, k):
​​​​lst = combinations(number,len(number)-k)
​​​​return "".join(max(lst))

제한 조건이 1,000,000 이기 때문에 시간 초과가 날 것을 예상했지만, 가장 단순하기 때문에 풀어보았다.

k개를 제거한 뒤, 가장 큰 수를 구하는 것이기 때문에, 뽑는 순서는 중요하지 않다고 생각해서, 조합을 활용하였다.

결과는 예상한 대로 시간초과,,,, 🥲

 

- 실행 결과

 

 

2.2 작은 수 부터 제거 (딕셔너리)

가장 큰 수를 만들려면 작은 수부터 제거하면 되지 않을까 하는 생각했다.

number에 포함된 숫자들의 빈도수를 센 뒤, 작은 수 부터 k개 만큼 제거하였다.

결론적으로는, 실패했습니다 🥲🥲

전체에서 작은 수를 제거하는게 아니라, 앞에서부터 제거해가면서 가장 큰 숫자를 만들어야 하기 때문이다.

 

- 코드

collections.Counter() 함수를 사용해도 되지만, 직접 작성했다

로직은 다음과 같다 :

1. 새로운 리스트 생성 - number 리스트의 distinct 값 (set 특성 활용 : 중복x)

2. 정렬

3. 리스트를 키로 가지는 딕셔너리 생성 (value는 0)

딕셔너리 생성할 때, count_dict = {string : number.count(string) for string in set(number)} 처럼, 요소의 빈도수를 count한 값을 바로 넣을수도 있지만, n개의 요소를 가진 number 리스트를 n회 반복 탐색해야 하기 때문에, 효율이 좋지 못하다고 판단했다

따라서, value가 0인 딕셔너리를 초기에 생성 한 뒤, 리스트를 1회 돌아서 value를 수정했다.

python

닫기 줄바꿈

def solution(number, k):
​​​​# 초기 딕셔너리 생성 
​​​​count_dict = {string : 0 for string in sorted(set(number))} # 중복x, 정렬

​​​​for n in number:
​​​​​​​​if n in count_dict:
​​​​​​​​​​​​count_dict[n] += 1
​​​​​​​​else:
​​​​​​​​​​​​count_dict[n] = 1

​​​​for key in count_dict.keys():
​​​​​​​​if(k <= 0): 
​​​​​​​​​​​​break

​​​​​​​​count = count_dict[key]

​​​​​​​​if(count <= k):
​​​​​​​​​​​​number = number.replace(str(key), '')
​​​​​​​​else:
​​​​​​​​​​​​number = number.replace(str(key), '', k)
​​​​​​​​k -= count

​​​​return number

 

- 실행 결과

 

2.3 Stack

전의 풀이들은 값을 삭제하는데 집중을 했다면, 이번에는 조건에 맞는 값을 리스트에 담아 반환해 보았다.

로직은 다음과 같다 :

- k < 0 or 빈 리스트 or 리스트 마지막 값 > num : 값 추가

- 리스트 마지막 값 < num : 삭제

 

문제 중 하나였던 number = "4177252841", k=4 로 테스트를 해보자면

- lst = [],                        k = 4,      num = 4                  # 리스트 비었으므로, 값 추가 

- lst = [4] ,                     k = 4,      num = 1     

- lst = [4, 1] ,                 k = 4,      num = 7

- lst = [4] ,                     k = 3                                      #1<7 이므로 1삭제

- lst = [] ,                       k = 2                                      #4<7 이므로 4삭제

- lst = [7] ,                     k = 2,      num = 7

- lst = [7, 7] ,                 k = 2,      num = 2

- lst = [7, 7, 2] ,             k = 2,      num = 5            

- lst = [7, 7] ,                 k = 1                                     #2<5 이므로 2삭제

- lst = [7, 7, 5] ,             k = 1,      num = 2

- lst = [7, 7, 5, 2] ,         k = 1,      num = 8

- lst = [7, 7, 5] ,             k = 0                                    #2<8 이므로 2삭제

- lst = [7, 7, 5, 8] ,         k = 1,      num = 4                # k =0 이므로 값 추가 

- lst = [7, 7, 5, 8, 4] ,     k = 1,      num = 1

- lst = [7, 7, 5, 8, 4, 1] , k = 1

retrun "775841"

 

- 코드 

처음에, "''.join(lst) 를 반환했는데 12번 테스트 케이스가 실패했다. 

반례를 찾을 수 없어, 프로그래머스 질문하기를 보니까 어떤 분이, 332211 처럼 갈수록 작아지는 숫자를 대입해 보라고 했다.

실제로 대입해보니 pop을 아예 하지 못해 전체 문자열을 반환하는 것을 확인하였다. 

따라서 반환값을 "''.join(lst[:len(lst) - k]) 로 바꾸니 통과~

python

닫기 줄바꿈

def solution(number, k):
​​​​lst = []
​​​​for idx in range(len(number)):
​​​​​​​​num = number[idx]
​​​​​​​​while(k>0 and len(lst)>0 and lst[-1]<num):
​​​​​​​​​​​​lst.pop()
​​​​​​​​​​​​k-=1
​​​​​​​​lst.append(num)
‌​​​​# return ''.join(lst)                # <--- 1번
‌return ''.join(lst[:len(lst) - k])   # <--- 2번

 

 

- 실행결과 

 

 

참고 사이트 :

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98