학습주제
탐욕적 기법을 이용한 코드 구현

학습 내용

def solution(number, k):
    # mutable 한 리스트를 답안 자료형으로 선택

    collected = []
    for i, num in enumerate(number):
        # 쌓아놓은 글자가 0보다 크고
        # 지금 꺼낸 글자가 쌓아놓은 마지막 글자 보다 큼
        # k 가 0 보다 큼
        # collected는 내림차순으로 쌓여있음.
        # 두번째 글자부터 최소 조건 만족 가능.
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        # 뺄 수 있는 갯수를 모두 소진 했을 경우,
        # if문이 없더라도 collected.append(num)에 의해 for 문을 돌며 1개씩 저장되지만,
        # 보다 직관적이고 효율성을 위해 아래와 같은 if 문 작성.
        # i부터 넣는 이유는 while문에서 걸러내고, k값 감소만 있고 collected에 넣는 기능은 없기 때문. 
        if k == 0:
            collected += list(number[i:])
            break
        # 최초의 값이 여기서 그대로 들어감. while문 넘김.
        collected.append(num)

    # k가 0인 경우 빈 리스트로 만들어버리기에, if 문으로 0개 이상의 조건을 제시.
    # 아래 형식의 if문은 많이 써보지 않음. 자주 봐둬서 익숙하게 하자.
    collected = collected[:-k] if k > 0 else collected
    answer = ''.join(collected)
    return answer

테스트 6 ~ 10 의 경우 소요시간이 긴데, 인자로 주어진 number와 k가 상대적으로 크다는 것을 알 수 있음.

복잡도

for i, num in enumerate(number):
	while len(collected) ~~~ k > 0:

이중 순환문처럼 보인다.
앞서 말했던 것처럼. collected에 들어가는 것 1회, 나오는 것 1회 O(n)이다.
앞서의 선택이 마지막 최적성에 영향을 미치지 않음.
모든 조사를 마치지 않더라도, 한 단계마다 지금 최적이라고 생각하는 것이 끝까지 최적일 것이다가 보장되기에 Greedy를 사용하 수 있었다.

어려운 점

복잡도 부분이 왜 선형시간 내인지 조금 이해가 가지 않았다. 일단 계속 정렬이 되는 식이기에 n^2 처럼 정말 모든 경우에 대해서 하나씩 n번 순환하는 것이 아닌 일부에 대해서 순환하기에 선형이다. 정도로 이해가 되었다.