오늘의 학습 키워드

Greedy , 순열과 조합

공부한 내용 본인의 언어로 정리하기

• 여러 숫자에게 K 개 수를 제거했을 때 얻을 수 있는 가장 큰 수를 구하는 함수 작성

어떤 문제가 있었고, 나는 어떤 시도를 했는지

첫번째 시도

• 만들 수 있는 모든 조합을 리스트에 추가

from itertools import combinations, permutations


def solution(number, k):
    answer = ''
    nums = list(map(int,number))
    nums_list = list(combinations(nums,k))
    arr = list()
    for x,y in nums_list:
        arr.append(x*10+y)
    print(max(arr))
    return answer

• ValueError: too many values to unpack (expected 2)
  이 에러를 구글링 해보내, 저장할 값의 개수가 변수 개수보다 많은 경우 발생
• 아마 아래 for 문에서 에러가 난 듯하다

    for x,y in nums_list:
        arr.append(x*10+y)

두번째 시도

from itertools import combinations, permutations


def solution(number, k):
    n = len(number) - k
    nums_list = list(combinations(map(int,number),n))
    arr = list()

    for num in nums_list:
        number = 0
        for i in range(n):
            number += num[i] * (10**(n-1-i))
        arr.append(number)

    return str(max(arr))

• 시간 초과로 인한 실패
  채점 결과
  정확성: 25.0
  합계: 25.0 / 100.0

• 이중 for 문을 조금 더 간단하게 만들 수 있는 방법은 없을까

from itertools import combinations, permutations

def solution(number, k):
    n = len(number) - k
    nums_list = list(combinations(number,n))
    arr = list()

    for num in nums_list:
        arr.append(''.join(num))

    return (max(arr))

• 시간 초과로 인한 실패
  채점 결과
  정확성: 33.3
  합계: 33.3 / 100.0

세번째 시도

결국 모르겠어서 구글링을 통해 stack 을 활용한다는 것을 알게됨. 하지만 그래서 잘 이해가 안되어서 다른 풀이를 참고했다

• Stack 을 이용한 구현
• 주어진 수를 하나씩 push 하는데 만약에 push 할 값보다 스택의 [-1]번째 요소가 더 작으면 pop
• pop 은 결국엔 수를 제거한다는 것 -> k -=1 을 해줌

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

• 먼저 stack 에 첫번재 요소를 넣어준다
• 두번째 요소부터 반복문을 적용
• stack 의 길이가 0보다 크고, stack[-1] < num 일 경우, k >0 일 경우에 pop, k-=1 을 적용한다
• k!= 0 일 경우는, 이미 for 문을 돌았는데도 k가(잘라내야할 수가 남아있ㅇ르 경우) 슬라이싱을 통해 잘라낸다

무엇을 새롭게 알았는지

• 스택을 이용한 Greedy 적용
• 직관적인 코드로 작성하지 않고, 스택을 사용하면 더 시간복잡도를 낮추면서도 간단하게 풀 수 있음을 알게됨 -> 하지만 다시 하라고 하면 생각못할것같은 방법

순열과 조합

• 순열

from itertools import permutations

nums = [1,2,3,4]
perm = list(combinations(nums, 2))

#[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)] 

• 조합

from itertools import permutations

nums = [1,2,3,4]
combi = list(combinations(nums, 2))

#[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 

• 순열은 순서를 고려한다. 즉 순서가 다르면 다른 숫자로 인식
• 조합은 가능한 모든 조합. 순서가 달라도 (1,2) (2,1) 같은 것으로 인식

학습할 것은 무엇인지

• 그리디에 스택, 데크 같은 자료구조를 적용하는 문제를 더 풀어봐야겠다
• Permuation, combination 라이브러리 사용에 대해서도 익혀야 겠다

출처

• 참고한 블로그