[알고리즘] 프로그래머스 큰 수 만들기 파이썬

[프로그래머스] LEVEL2 큰 수 만들기

✅ 문제

✅ 나의 풀이

그리디 알고리즘 연습을 위해 문제를 풀었다. 그리디 알고리즘은 지금 당장 최적인 경우를 따르는 근사적인 방법이다.

1. 첫번째 수가 될 숫자 찾기

   • 최대한 큰 수이자 k개 수의 삭제로 첫번째 수가 될 가능성이 있는 수

2. 1번에서 결정된 첫번째 수의 앞자리 수들 빼기 (slice)

3. 오른쪽의 수가 왼쪽의 수보다 큰 경우 왼쪽 수 빼기

✅ 다른 풀이

• 스택의 마지막 값이 push할 값보다 작다면 크거나 같은 값이 나올 때까지 스택 내의 값들 pop

구글링을 통해 얻은 아이디어와 나의 아이디어는 어느정도 일치했지만 나의 풀이는 정돈되지 않았다. 구글링 후 stack을 사용해 코드를 수정해야겠다는 생각을 했고 재구현하였다.

def solution(number, k) :
    answer = []
    for num in number :
      if k <= 0 :
        answer.append(num)
        continue
      if not answer or answer[-1] >= num:
        answer.append(num)
      else :
        while answer and answer[-1] < num and k > 0:
          answer.pop()
          k -= 1
        answer.append(num)
    if k > 0 :
        for i in range(k) :
            answer.pop()
    return ''.join(answer)

아래의 if문을 놓쳐서 마지막 케이스를 통과하지 못했고 급히 추가했다.

문제 통과 후 반복되는 코드들을 줄이고 최적화한 코드는 아래와 같다.

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

✅ 얻어가기

코딩테스트 준비를 이제서야 본격적으로 시작했다. 그래서 알고 있지만 생각이 나지 않는 개념이 많아 정리해보려고 한다. 확실하게 머리에 넣기 위해 적어본다. 일명 졌잘싸를 위해. 졌지만 잘 싸웠다...

얕은 복사

copyNumList = numList

위 코드는 얕은 복사로, 같은 메모리를 참조한다. 따라서 함께 움직인다.
깊은 복사를 위해서는 copy 모듈의 copy.deepcopy()를 사용해야 한다.

리스트의 인덱스

idx = numList.index(value)

중복된 값이 존재하면 첫번째 인덱스를 반환한다.

join

''.join(map(str, numList))

리스트의 원소들이 integer 타입인 경우 string으로 변환 후 join해야 한다.

slice

꼭 애용하기... 자꾸 잊는다. 잘 사용하면 코드가 확실히 단축된다.

빈 리스트인가

파이썬에서는 [list].empty()와 같은 함수를 제공하지 않는다. not [list]를 쓰자.