[파이썬 알고리즘 문제풀이 입문] 자료구조 활용 (스택, 큐, 해쉬, 힙) - 가장 큰 수 (스택)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요. (단, 숫자의 순서는 유지해야 합니다.)

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

num, m = map(int, input().split())
num = list(map(int, str(num)))
stack = list()

for x in num:
    # 숫자빼주는 로직
    # stack -> 비어있으면 False, 비어있지X면 True
    # 비어있지않고 / 뺀횟수가 0보다 크고 / 가장 최근값이 나보다 작을 때
    while stack and m>0 and stack[-1]<x:
        stack.pop() # 맨 뒤의 값 pop
        m-=1
    stack.append(x)

# 뺀 횟수가 아직 남아있을 때
if m!=0: 
    stack = stack[:-m]

# 리스트 내부의 값이 int이기 때문에 map으로 str로 바꿔주기
res = "".join(map(str, stack))
print(res)

- stack을 사용하여 문제 풀이를 하였다. (stack의 성질 : LIFO)

- 숫자들이 담긴 리스트의 요소에 하나씩 접근하고, while문을 돌려서 stack의 성질을 이용하여 알고리즘을 구현한다.

: stack이 비어있지X, 제거시킬 횟수 > 0보다 크고(= 아직 더 제거할 수 있음), 최근에 stack에 넣은 마지막 값 < 현재 값보다 작을 때 → stack의 마지막 값을 제거하고, 제거시킬 횟수를 1 감소시킨다.

- 제거시킬 것들을 다 제거시켰다면, 해당 숫자를 stack에 넣는다.

- 제거시킬 것들을 다 제거시켰음에도 불구하고 횟수가 남았다면? → 남은 횟수만큼 뒤에서 자른다.

- 리스트를 문자열로 바꿔서 출력한다.

 

 

• 답안 : Kotlin (내가 바꿔본 것 / 정확X) → 직접 구현 (MutableList)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var (num, m) = readLine().split(" ").map { it.toInt() }
    var num_list = num.toString().map { Character.getNumericValue(it) }
    var stack : MutableList<Int> = mutableListOf()

    for(i in num_list) {
        while(stack.isNotEmpty() && m>0 && stack.last()<i) {
            stack.removeLast()
            m -= 1
        }
        stack.add(i)
    }
    
    if(m!=0) {
        stack = stack.slice((stack.size-m)..stack.size).toMutableList()
        // stack = stack.subList(0, stack.size-m).toMutableList()
        println(stack)
    }

    val res = stack.joinToString("")
    println(res)
}

- 숫자 → 문자열로 변경 → map으로 각 문자를 숫자로 변경

: num.toString().map { Character.NumericValue(it) }

 

- 일정 범위의 리스트를 잘라야 할 경우 (범위1 이상, 범위2 미만)

: 방법1 → 리스트.slice(범위1..범위2)

: 방법2 → 리스트.subList(범위1, 범위2) 

 

 

• 답안 : Kotlin (내가 바꿔본 것 / 정확X) → Stack 사용

import java.io.*
import java.util.*
import java.util.Stack

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var (num, m) = readLine().split(" ").map { it.toInt() }
    var num_list = num.toString().map { Character.getNumericValue(it) }
    var stack = Stack<Int>()

    for(i in num_list) {
        while(stack.isNotEmpty() && m>0 && stack.peek()<i) {
            stack.pop()
            m -= 1
        }
        stack.push(i)
    }

    if(m!=0) {
        for(i in 0 until m) {
            stack.pop()
        }
    }
    
    println(stack.joinToString(""))
}

- Kotlin 자체적을 구현된 Stack이 없기 때문에, import java.util.Stack 을 통해 자바에 있는 Stack을 사용할 수 있다.

- push() : 값 삽입 / pop() : 값 삭제 / peek() : 제일 마지막 값 반환 / size() : 스택의 사이즈