[프로그래머스] (Python-Greedy) 체육복, 큰 수 만들기

1. https://nowolver.tistory.com/155 : 알고리즘 중 탐욕 알고리즘에 대한 개요를 공부했으니 이를 적용해보자. 

[알고리즘] Greedy Algorithm[그리디; 탐욕법]

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

프로그래머스

Q. 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항
전체 학생의 수는 2명 이상 30명 이하(2<=n<=30)입니다.체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

이때, 나는 먼저 여벌체육복이 있는 학생도 도난당할 수 있다는 것을 생각해서, lost와 reserve 자체에 중복이 가능하기에(체육복이 없지만 않다면 ... 도둑맞을 수 있는 거니까) 이런 중복값이 있는지, 있다면 제거하는 것을 1순위로 두기로 했다. 또한, 이를 list에 포함한 다음, n에서 list 개수만큼 제거해주면 된다고 생각했다(하나하나 세는 것보단 뺴는 게 낫다고 판단했음!)

def solution(n, lost, reserve):
    # 오름차순 정렬
    lost.sort()
    reserve.sort()
	
    # lost, reserve의 중복 요소 제거
    for i in reserve[:]:
        if i in lost:
            reserve.remove(i)
            lost.remove(i)
	
    # 체육복 빌려주기(나의 앞 번호부터 확인(앞번호나 뒷번호 중 한 명이 빌려주면 되므로 작은 번호부터 체크))
    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    
    return n-len(lost)

결과적으로 풀렸다 :)

---

2. 큰 수 만들기

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

프로그래머스

문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.k는 1 이상 number의 자릿수 미만인 자연수입니다.

사실 k개 수의 조합을 모두 만든 다음, 리스트로 변환해 i번째 요소와 i+1번째 요소를 각각 비교하는 방식으로 진행해도 되긴 한다. 그러나 이렇게 되면 시간소모가 엄청나다는 단점이 있기에, 어쨌든 그리디 카테고리니까 그리디를 써보기로...

: k개 수 리스트 작성 시, 큰 수부터 앞에 오도록 선택하는 것이다. 처음 선택한 수부터 자료구조 stack에 넣어 삭제(pop) 및 push를 진행하면 된다는 아이디어.

def solution(number, k):
    stack = []
    for n in number:
        while stack and stack[-1] < n and k > 0:
            stack.pop()
            k -= 1
        stack.append(n)

    # 아직 제거되지 못 한 숫자를 뒤에서 삭제
    if k > 0:
        stack = stack[:-k]

    return ''.join(stack)

성공하긴 했다 너무 오래 걸려서 그렇지

---

그리디 알고리즘은 선택하는 대상의 범주(동전인지 숫자인지 등)를 명확히 골라서 어떻게 선택할 것인지(정렬 후에 선택할 건지, 뭐 pop으로 제거하면서 선택할 건지 등) 정하기만 하면 절반은 온다고 생각한다. 연습 많이 해야지 ....