[프로그래머스] level 2 - 큰 수 만들기 (탐욕법)

 

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

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

 

def solution(number, k):
    answer = ''
    # 당장의 최선만 선택해도 되는가? >> 그리디알고리즘
    
    # 숫자를 담을 리스트 선언
    num = []
    
    # 반복문으로 인덱스와 값을 각각 나열하도록 함 
    for index, value in enumerate(number):
        # 반복문으로 조건을 달아서 돌려야함 
        # 일단, num리스트안에 뭐라도있어야함 그래야 비교해서 큰걸 넣어둠
        # 두번째로 마지막에 추가된 원소와 다음에 추가할 원소를 비교해야 함
        # 마지막으로 k가 0보다 커야함
        while len(num) > 0 and num[-1] < value and k > 0:
            num.pop()
            k -=1
        
        # k가 0인경우, 더이상 제거할것이 없는경우 나머지를 붙여줘야함 
        if k == 0:
            num += list(number[index:])
            break
            
        # 조건을 다 돌고오면 이제 원소를 넣어줘야함
        num.append(value)
        
    # 조건에 걸리지는 않지만 k가 0 이상인 경우
    num = num[:-k] if k > 0 else num
    
    answer += "".join(num)
    
    return answer

 

처음에 그리디알고리즘을 선택해도 되는지 생각해보고 가능하다는 가정하에 코드를 작성한다

문자열을 왼쪽 맨앞의 숫자부터 차례로 비교하며 제일 큰수만 남겨두고 작은수를 차례로 k개만큼 삭제하는 알고리즘을 작성하도록 한다.

---

문자열을 리스트안에 넣어서 정수다루듯이 하는것이 수월하므로 빈 리스트를 선언한다.

enumerate 함수를 사용하여 index값과 value 값을 각각 다룰수있도록 만들어준다.

 

list[-1] 은 마지막원소를 지칭하므로 그 다음 추가될 value 값과 비교할때 사용하기 유용하다.

마지막에 추가된 원소보다 그다음 추가될 원소가 크다면 직전 원소를 제거해준다.

또한 k개를 0으로 만들어줘야하므로 한개 삭제할때마다 k를 -1 씩 빼줘야한다.

그다음 k가 0인경우를 생각해줘야한다.

 

k가 0인경우, 뒤에 문자열을 붙여줘야하므로

index값을 기준으로 새로운 리스트를 선언하여 붙여주도록 한다.

그리고 여기까지의 조건을 모두 충족한경우 리스트안에 원소를 삽입하여 채워가야한다.

 

마지막으로 앞의 조건에 걸리지않지만, k가 0보다 큰경우가 있다.

이경우를 생각했을때, 뒤에서부터 제거를 하고 붙여주면되는데

슬라이싱을 사용하여 num = num[:-k] 가 되도록 정의해준다.

answer이라는 문자열에 리스트를 추가해줘야하므로, join을 이용하여 마무리 작업을 해주면 된다.

 

---

* enumerate 

열거하다 라는뜻으로 순서가 있는 자료형 (리스트, 튜플, 문자열) 을 입력으로 받아

인덱스 값을 포함하는 enumerate 객체를 돌려준다.

for문과 함께 사용하면 자료형의 현재 순서(인덱스) 와 그 값을 쉽게 알수 있다.

 

*  join

리스트에 특정 구분자를 추가하여 문자열로 변환한다.

ex)

list = [ a, b, c]

print(",".join(list))

# a, b, c 로 출력이 된다.