[백준] 21314번: 민겸수 Python

https://www.acmicpc.net/problem/21314

21314번: 민겸 수

규칙을 발견하면 바로 구현할 수 있는 문제이다 

최솟값의 경우 M이 등장할때 M과 K를 최대한 적게 묶는다 K는 각각 하나씩 분해해서 묶고, M은 M끼리 묶는다 

 

M/K/K/MM/K = 155105

 

최댓값의 경우 K가 등장할때 최대한 많은 M이랑 묶어주어야 한다. 그런데 K는 M보다 뒤에 오니까, 문자열을 선형탐색할 때 마지막 인텍스부터 첫번째 인덱스를 탐색해주어야 한다. 

MK/K/MMK = 505500

 

전체 코드는 다음과 같다 

data = input()
min_value = ''
max_value = ''
n = len(data)
visited = [False] * n
# 최솟값 : M은 최대한 적게 묶고 K는 무조건 각각 묶는다
# ex) M/K/K/MM/K = 155105
for i in range(n):
    if data[i] == 'K':
        min_value += '5'
        visited[i] = True
    else: #M
        count = 1
        if not visited[i]:
            visited[i] = True
            for j in range(i+1, n):
                if data[j] == 'M' and not visited[j]:
                    count += 1
                    visited[j] = True
                else:
                    break
            min_value += str(10**(count-1))

visited = [False]*n # 다시 초기화

# 최댓값 : 뒤에서부터 탐색해서 K가 등장하면 M이랑 최대한 많은 개수를 묶어서 십진로 변환한다. 수
# ex) MK/K/MMK
for i in range(n-1, -1, -1): # 뒤에서 부터 확인
    if data[i] == 'K': # K 등장하면 M의 개수를 센다
        visited[i] = True
        count = 1
        for j in range(i-1, -1, -1):
            if data[j] == 'M' and not visited[j]:
                count += 1
                visited[j] = True
            else:
                break
        # 앞에서 부터 이어 붙이기
        max_value = str(5*10**(count-1)) + max_value
    else: # M 발견
        if not visited[i]:
            max_value = '1' + max_value

print(max_value)
print(min_value)