(Week4)[그리디] 큰 수 만들기

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

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

프로그래머스

2. 접근 방식_해답참고

• 초기 조합을 활용한 풀이의 경우 시간 효율성 문제 통과 못함
• 그리디: 현재 제일 좋은 경우를 생각하면서 나아가는 방법
• 스택을 활용해 문제를 해결할 수 있음
  • 스택에 높은 값을 하나 씩 넣어준다
  • 스택에 넣은 값 중 작은 값이 생긴다면 그보다 큰 값이 나올 때까지 빼고, 그 자리에 넣어준다.
  • 스택에 있는 값을 뺄 때, K값도 1씩 빼준다. 
  • K가 0이 되면 나머지 값들을 넣어준다.
  • (예외 케이스) K가 0이 되기 전에 for문이 다 끝나는 경우가 있기 때문에 뒤에서부터 남은 k값을 제외하고 출력이 필요하다. `answer[:len(answer)-k]`

3. 코드

def solution(number, k):
    answer = []
    for i in number:
        while k > 0 and answer and answer[-1] < i: # 4,1, 7이면 pop을 2번 해야 함.
            answer.pop()
            k-=1
        answer.append(i)
    return "".join(answer[:len(answer)-k])

4. 코멘트

• 조합을 활용했을 때는 안 될 거라고 생각했었다. 
• 스택 자료구조를 활용할 생각을 하지 못헀었다. (사실 어차피 왼쪽에 오는 값들이 크는게 제일 중요하니까 스택이 찰떡이었던 것 같다.)