baekjoon. 크게 만들기 (2812) [python][Gold III]

문제 링크 : https://www.acmicpc.net/problem/2812

>> 접근방법

- 숫자 k개를 지웠을때 맨 앞의 수가 가장 클수로 정답인 가장 큰 수를 얻을 수 있다.

내가 처음에 풀었던 접근은 숫자 중에서 제일 큰 숫자들을 남기는 방식으로 접근했는데,
그럴경우 세번째 예시에서 477584가 남으면서 775841에서 답이 틀린다.

 

- 이를 위해 현재 인덱스 위치값보다 왼쪽(-1 위치)값이 작고 지울 수 있는 횟수 k가 남아있다면 현재 인덱스 왼쪽 (-1) 값을 지워주면 된다.

 

 

>> 내가 푼 풀이

N, K = map(int, input().split())
num = input()


stack = []
cnt = K
for i in num:
    # 현재 i가 stack에 있는 값보다 크다면 제거 
    while (cnt > 0 and len(stack) > 0 and stack[len(stack) - 1] < i): 
        stack.pop(len(stack) - 1)
        cnt = cnt - 1
    stack.append(i)


answer = ''
for i in range(len(stack) - cnt):
    answer += stack[i]
print(answer)

 

>> <보통의 취준생을 위한 코딩 테스트 with 파이썬> 풀이 p.173

N, K = map(int, input().split())
num = input()


answer = []
cnt = K
for i in num:
    while answer and cnt > 0 and answer[-1] < num:
        del answer[-1]
        cnt -= 1
    stack.append(i)


print(''.join(answer[:n-k]))

책에서 제공하는 풀이에서 보면, 내가 푼 풀이와 다르게 간단하게 가져올 수 있는 부분이 있었다.

1/ answer[len(stack) -1] => answer[-1]

cf1) 배열 인덱스 음수 의미  https://www.codingem.com/python-indexing-from-end/

 

2/ print(''.join(answer(\[:n-k\]))

cf2) 파이썬 코딩 도장 : 슬라이스 사용하기  https://dojang.io/mod/page/view.php?id=2208

 

answer = ''
for i in range(len(stack) - cnt):
    answer += stack[i]
print(answer)

=> print(''.join(answer([:n-k]))

 

 

* 75% 실패 

참고로, 75%에서 틀렸을 경우, 마지막 join해줄때 n-k만큼 가져오는 부분을 안 넣었을 가능성이 큰데, (내가 그랬다.)

이부분은 아래 예시에서 결국 마지막까지 k 개 숫자를 자르지 못했을때, 앞에서부터 n-k만큼 가져오는 부분을 넣어야 한다.

5 1
54321

답 : 5432

 

cf1) 백준 반례 예시 https://ideone.com/EWRsQr

cf2) 백준 질문게시판 https://www.acmicpc.net/board/view/108820

 

 

 

---

아래 책 <보통의 취준생을 위한 코딩 테스트 with 파이썬> 7-6절을 읽고 정리한 글입니다. 

http://www.yes24.com/Product/Goods/107478270

보통의 취준생을 위한 코딩 테스트 with 파이썬 - YES24