백준 21314 민겸 수 Python

🐸 문제 정보

21314번: 민겸 수

 

🤖 알고리즘

그리디, 구현

 

⏱️ 풀이 시간

12.59m

 

📝 풀이

예제를 직접 손으로 그려보면 그리디라는 것을 쉽게 파악할 수 있었다.

각각 최대값과 최소값을 찾는 순서는 아래와 같다.

둘다 기본적으로 주어진 입력에 대해 앞에서부터 순회한다.

 

최대값

1. M이 나오면 stack에 담는다.
2. K가 나오면 K를 포함한 stack의 길이(n) 만큼 5 * (10 ^ (n - 1))를 문자열로 바꿔 정답 문자열에 더해준다.
3. 마지막에 stack에 담겨진 M을 모두 1로 치환하여 정답 문자열에 더해준다.

최소값

1. M이 나오면 stack에 담는다.
2. K가 나오면 현재까지 stack의 길이(n) 만큼 10 ^ (n - 1)를 문자열로 바꿔 정답 문자열에 더해준다.
3. 마지막에 stack에 담겨진 M의 수(n) 만큼 10 ^ (n - 1)을 문자열로 바꿔 정답 문자열에 더해준다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

nums = list(input().rstrip())

def minn():
    stack = []
    res = ''
    for num in nums:
        if num == 'K':
            if len(stack): res += str(10 ** (len(stack) - 1))
            res += '5'
            stack = []
        else:
            stack.append(num)
    if len(stack): res += str(10 ** (len(stack) - 1))
    return res

def maxx():
    stack = []
    res = ''
    for num in nums:
        if num == 'K':
            res += str(5 * (10 ** len(stack)))
            stack = []
        else:
            stack.append(num)
    for _ in stack:
        res += '1'
    return res

print(maxx())
print(minn())