[Python-CodingTest] 5-1. 가장 큰 수 (스택)

가장 큰 수

문제 정리

입력

5276823 3 // n m

처리 과정

1. int형인 n을 int 리스트로 변경
2. while문 돌면서 스택의 맨 마지막 요소가 나보다 작으면 pop() & m-=1
3. 뺄거 다 뺐으면 내가 들어가기: stack.append(x)
4. 총 m개를 빼야하는데 그것보다 덜 뺐으면 stack의 맨 뒤에서부터 m개만큼 빼기: stack=stack[:-m]

출력

7823

풀이

import sys
sys.stdin = open("./input/in1.txt", "rt")

n,m=map(int,input().split())

# 숫자를 int 리스트화
lst=list(map(int,str(n))) # map에서 n을 스트링화 시켜서 넣어야함!
stack=[] # 빈 리스트 생성

for x in lst:
    while stack and m>0 and stack[-1]<x: # 스택이 비어있지 않으며, 리스트의 맨 마지막 요소가 나보다 작으면 pop
        stack.pop()
        m-=1
    stack.append(x) # 나보다 작은 수를 다 꺼냈으면 내가 들어가기

# m이 0이 아니라면(=리스트에서 더 꺼내야 한다면) 뒤에서부터 m번째까지 꺼내기
if m!=0:
    stack=stack[:-m]

# 리스트인 stack을 다 붙여서 스트링화
res=''.join(map(str,stack)) # 7823
# res='|'.join(map(str,stack)) # 7|8|2|3
print(res)

# 혹은
# for x in stack:
#     print(x,end='')

정리

• 숫자 n을 하나씩 정수 리스트에 넣기: lst=list(map(int,str(n)))

  만약 n이 12345(만이천삼백사십오)였다면, lst에는 [1, 2, 3, 4, 5]가 들어간다.

• 리스트의 맨 뒤부터 m번째까지 slicing: lst=lst[:-m]

  리스트의 맨 뒤 요소는 lst[-1]이다.
  만약 lst에 [1, 2, 3, 4, 5]가 들어있었다면, lst=lst[:-2]한 뒤에 lst는 [1, 2, 3]가 된다.

• 리스트인 stack을 다 붙여서 스트링화: str=''.join(map(str,stack))

  만약 str='|'.join(map(str,stack))이라면?
  stack에 [1, 2, 3, 4, 5]가 들어있었다면, str에는 1|2|3|4|5가 들어간다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기