[백준] #21314 민겸 수 (python)

21314번: 민겸 수 (acmicpc.net)

21314번: 민겸 수

문제

민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.

민겸 숫자는 0 이상의 정수 N에 대해 10N 또는 5 × 10N 꼴의 십진수를 대문자 M과 K로 이루어진 문자열로 표기한다. 10N 꼴의 십진수는 N + 1개의 M으로, 5 × 10N 꼴의 십진수는 N개의 M 뒤에 1개의 K를 이어붙인 문자열로 나타낸다. 즉, 아래 표처럼 나타낼 수 있다.

변환 전	변환 후
1	M
5	K
10	MM
50	MK
100	MMM
500	MMK
1000	MMMM
5000	MMMK
...	...

민겸 수는 한 개 이상의 민겸 숫자를 이어붙여 만든다. 예를 들어, 민겸 수 MKKMMK는 MK, K, MMK의 세 민겸 숫자를 이어붙여 만들 수 있다.

민겸 수를 십진수로 변환할 때는, 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면 된다. 민겸 숫자를 십진수로 변환하는 것은 십진수를 민겸 숫자로 변환하는 과정을 거꾸로 하면 된다. 예를 들어, 민겸 수 MKKMMK는 아래 그림과 같이 여러 가지 십진수로 변환할 수 있다.

민겸이는 위와 같이 하나의 민겸 수가 다양한 십진수로 변환될 수 있다는 사실을 알았다. 문득 민겸이는 변환될 수 있는 십진수 중 가장 큰 값과 가장 작은 값이 궁금해졌다. 민겸이를 위해 하나의 민겸 수가 십진수로 변환되었을 때 가질 수 있는 최댓값과 최솟값을 구해주자.

입력

민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다.

출력

주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.

 

예제 입력1

MKM

예제 출력1

501
151

 

예제 입력2

MKKMMK

예제 출력2

505500
155105

 

# Code

import sys
input = sys.stdin.readline

s = input().rstrip() # rstrip 없으면 for문 한 번 더 돌아서 틀린 답이 나옴.

m = 0
max = ''
min = ''

for i in s:
    if i == 'M':
        m += 1
    else: # i가 k일 경우
        if m>0:
            max += str(5*(10**m))
            min += str(10**m + 5)
        else:
            max += '5'
            min += '5'
        m = 0

# 'M'으로 끝날 경우
if m>0:
    max += '1' * m
    min +=  str(10**(m-1))

print(max)
print(min)

# Comment

야심짜게 알고리즘을 짜고 풀어보려고 했는데.. 잘못된 방법이었다. ㅎㅎ. .

민겸 수가 최댓값이 나오려면 K가 나올 때, (10 ** (앞에서 나온 M의 갯수)) * 5 를 계속해서 뒤에 더해줘야 한다.
ex) MMK => 10^2 * 5 = 500
민겸 수가 최솟값이 나오려면 K가 나올 때, (10 ** (앞에서 나온 M의 갯수) + 5) 를 계속해서 뒤에 더해줘야 한다. 
ex) MMK => 10^2 + 5 = 105 //만약에 M을 따로따로 계산하면 115가 되어서 최솟값이 아니게 됨(내가 간과했던 부분)

풀이에서는 K가 나올 경우에 앞에서 M이 나왔는지 안나왔는지 m이라는 변수로 파악을 해서 m이 양수일 경우(M이 앞에서 나왔을 경우) 위의 알고리즘대로 진행해주고, 그렇지 않을 경우(M이 앞에서 나오지 않았을 경우 or 이미 계산되었을 경우) 최댓값 최솟값 모두 동일하게 뒤에 '5' 를 추가해준다.
그리고 K를 만났을 때는 m 변수를 0으로 초기화해준다.

만약에 for문을 다 돌고 나왔을 때 m이 양수라면, M으로 끝났을 경우이므로 최댓값의 경우엔 M의 갯수만큼 1을 추가해주고 (10^0 이기때문에) 최솟값의 경우엔 10**((M의 갯수)-1) 을 추가해준다.

** 처음에 작성하고 나서 바로 제출했더니 "틀렸습니다."가 떠서, 한 번 출력을 해봤다. 그런데 MK 로 끝나는 경우인데 뒤에 자꾸 '5'가 추가되는 문제가 발생했다. 즉.. for문을 한 번 더 돌아서 else로 넘어가서 '5'를 추가해준다는건데.. 혹시나해서 s = input 뒤에 .rstrip() 을 추가했더니 문제가 해결됐다. 하놔 이거 유의해야겠다. 다시 개념 다지러 가야겠음..   

readline으로 입력받으면 뒤에 개행문자가 추가되기 때문에 공백을 제거해줘야 한다.
* rstrip() : 오른쪽 공백을 삭제
* lstrip() : 왼쪽 공백을 삭제
* strip() : 왼쪽, 오른쪽 공백을 삭제

 

아래는 개념 참고한 사이트이다.

https://yang-wistory1009.tistory.com/54

[파이썬] 다양한 입력함수 input(), sys.stdin.readline(), rstrip(), lstrip(), strip() 사용 - 공부하는 도비