[python/파이썬] 백준 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

 

 

 

[소스 코드1 - 틀렸습니다]

 

틀린 코드지만 테스트 케이스를 돌렸을 때에는 잘 돌아갔다

그런데 어느 부분이 틀린지 잘 모르겠어서 일단 남겨두고 후에 다시 고쳐보려고 한다.

 

최댓값은 M뒤에 K가 나온다면 둘을 하나의 수로 자르면 된다.

최솟값은 M으로만 구성되거나, K는 1개만 되도록 자르면 된다.

import re #정규표현식 사용
data = input()
data = re.split('(K)', data) #'K'를 없애지 않고 'K'로 split
data = list(filter(None, data)) # 리스트 내의 빈 원소를 제거

max_list = [] 

for i in range(len(data)): 
    if data[i]=='K': #현재 원소가 'K'이고 이전의 원소가 'M..'일 때 
        if i>0 and data[i-1]!='K': #i가 첫번째가 아니어야 함
            max_list.append(data[i-1]+data[i]) #둘을 붙혀서 저장
        else: #둘의 경우가 아니면 'K'를 저장 -> 'KK'인 경우
            max_list.append(data[i]) 
if data[-1] != 'K': #마지막이 'M..'으로 끝났다면
    max_list.append(data[-1])

#각 원소의 값을 계산하여 string으로 저장
result_max = []           
for m in max_list: #최댓값을 구할 때
    m_count = m.count('M')
    k_count = m.count('K')

    result = 1

    if m_count:
        if k_count:
            result = 5 * int(pow(10,m_count))
        else:
            result = int(pow(10,m_count-1))
    else:
        if k_count:
            result = 5

    result_max.append(str(result))

result_min = []
for m in data: #최솟값을 구할 때
    m_count = m.count('M')
    k_count = m.count('K')

    result = 1

    if m_count:
        if k_count:
            result = 5 * int(pow(10,m_count))
        else:
            result = int(pow(10,m_count-1))
    else:
        if k_count:
            result = 5

    result_min.append(str(result))

print(''.join(result_max)) #각 원소들을 연결해서 출력
print(''.join(result_min))

 

[소스 코드2 - 맞았습니다]

 

소스 코드1을 제출하고 틀려서 혹시 다른 사람의 코드를 보면 답이 나오지 않을까 해서 찾아보았는데

다른 코드들은 아예 다른 방법들로 구현되어있어서 고치지 못했다

 

최댓값을 구하기 위해서는 최대한 M과 K로 구성된 숫자를 많이 만들어야 하고

최솟값을 구하기 위해서는 MK가 같이 포함된 숫자를 만들면 안된다.

M과 K로 구성된 숫자는 10을 (M의 개수) 만큼 거듭제곱해주고 5를 곱해준다

ex) MK -> (10^1) * 5 = 50

M과 K가 연속되었는데 둘이 같은 숫자가 아니라면 10을 (M의 개수) 만큼 거듭제곱 해주고 5를 더해준다 

ex) M K -> (10^1) + 5 = 15

data = input()
max = "" #최댓값 결과
min = "" #최솟값 결과
m = 0

for i in range(len(data)):
    if data[i] == 'M':
        m += 1 #M이 나온다면 m을 증가
    elif data[i] == 'K':
        if m: #M후에 K가 연속해서 나온 경우라면
            min += str(10**m + 5) #최솟값의 경우 5를 더해주고
            max += str(5 * (10**m)) #최댓값의 경우 5를 곱해준다
        else: #만일 K만 두번이상 연속된 경우
            min += "5" 
            max += "5"
        m = 0
if m: #'K'없이 'M'들로 문자열이 끝난 경우
    min += str(10 ** (m-1))
    while m:
        max += "1"
        m -= 1
print(max)
print(min)