[김태원 알고리즘] 가장 큰 수 (스택)

사용 언어: Python3

문제

풀이

내 풀이

# 기준(i번째)보다 앞에 위치한 원소를 순회하면서 값이 더 작은 원소 수 카운트
def process(cnt, i):
    global N
    for j in range(i-1, -1, -1):
        if N[j] != -1 and N[j] < N[i]:
            N[j] = -1 # N.pop(j) 대신
            cnt += 1
        if cnt == K:
            return cnt
    return cnt

N, K = map(int, input().split())
N = list(map(int, str(N)))

cnt = 0
for i in range(len(N)):
    if cnt == K:
        break
    cnt = process(cnt, i)

if cnt < K: # 카운트한게 K보다 작으면 맨 뒤에서부터 이어서 pop
    for i in range(K-cnt):
        N[len(N)-1-i] = -1

for x in N:
    if x == -1:
        continue
    print(x, end='')

• 맨 처음 원소부터 기준점으로 세팅한다.
• 기준점 앞쪽을 역으로 순회하며 기준점의 값보다 작은 값이 있으면 pop(=-1대입)하며 카운트하기
  • 원래는 pop해야하지만 pop하면 인덱스가 바뀌기때문에 -1로 변경하고, 맨 마지막에 -1은 출력하지 않을 것이다.
  • 기준점보다 작은 값을 판단할 때에는 -1은 고려하지 않는다.
• 카운트 값이 K가 될 때까지 pop하기
• 만약 모든 원소를 기준점으로 순회했는데도 카운트 값이 K보다 작다면, 맨 뒤 원소부터 K-cnt만큼 pop
  • 초기: 9 9 7 7 2 5 2 6 4 1, K=5
  • 기준: 9
    • 앞쪽( )에 9보다 작은 수가 없으니 패스 (cnt = 0)
  • 기준: 9
    • 앞쪽(9)에 9보다 작은 수가 없으니 패스 (cnt = 0)
  • 기준: 7
    • 앞쪽(9 9)에 7보다 작은 수가 없으니 패스 (cnt = 0)
  • 기준: 7
    • 앞쪽(9 9 7)에 7보다 작은 수가 없으니 패스 (cnt = 0)
  • 기준: 2
    • 앞쪽(9 9 7 7)에 2보다 작은 수가 없으니 패스 (cnt = 0)
  • 기준: 5
    • 앞쪽(9 9 7 7 2)에 5보다 작은 수가 있다!
    • 2를 -1으로 변경 (cnt = 1)
  • 기준: 2
    • 앞쪽(9 9 7 7 -1 5)에 2보다 작은 수가 없으니 패스 (cnt = 1)
  • 기준: 6
    • 앞쪽(9 9 7 7 -1 5 2)에 6보다 작은 수가 있다!
    • 2를 -1으로 변경 (cnt = 2)
    • 5를 -1으로 변경 (cnt = 3)
  • 기준: 4
    • 앞쪽(9 9 7 7 -1 -1 -1 6)에 4보다 작은 수가 없으니 패스 (cnt = 3)
  • 기준: 1
    • 앞쪽(9 9 7 7 -1 -1 -1 6 4)에 1보다 작은 수가 없으니 패스 (cnt = 3)
  • 모든 원소를 기준점으로 두고 순회했는데 cnt(=3)가 K(=5)보다 작다.
    • 맨 뒤에서 2개(K-cnt)를 -1로 변경한다.
    • 9 9 7 7 -1 -1 -1 6 4 1 => ✅ 9 9 7 7 -1 -1 -1 6 -1 -1
  • -1을 제외하면 정답은 9 9 7 7 6

다른 풀이 - 🌟 스택 사용

로직은 위와 같지만 스택이라는 자료구조를 사용해 더욱 효율적으로 구현할 수 있다.

N, K = map(int, input().split())
N = list(map(int, str(N)))
stack = []

cnt = 0
for x in N:
    while stack and cnt<K and stack[-1]<x:
        stack.pop()
        cnt += 1 # ✅ cnt 증가
    stack.append(x)

print(''.join(map(str, stack[:len(N)-K]))) # ✅ int를 str으로 변환한 뒤 join
# for x in stack[:len(N)-K]: # ✅ 원하는 만큼만 슬라이싱 해 출력
#    print(x, end='')

다른 풀이 - 🌟 스택 사용

스택을 사용하는 것은 위와 같다. cnt 변수를 두지않고 K 값을 줄인다.

N, K = map(int, input().split())
N = list(map(int, str(N)))
stack = []

for x in N:
    while stack and K>0 and stack[-1]<x:
        stack.pop()
        K -= 1 # ✅ K 차감
    stack.append(x)

if K != 0:
    stack = stack[:-K]  # ✅ 뒤에서부터 K개 떼어버리기

print(''.join(map(str, stack))) # ✅ int를 str으로 변환한 뒤 join
# for x in stack:
#     print(x, end='')

---

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

맨 위로 이동하기