서론
그리디 문제입니다.
어떤 식으로 최솟값과 최댓값을 구할 수 있는지 생각하려다 K를 기준으로 앞에 M의 갯수를 세어 구해주었습니다.
난이도
실버 1
문제
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 1024 MB |
민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.
민겸 숫자는 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풀이
- 문자열을 순서대로 탐색하며 M과 K일 경우를 계산한다.
현재 문자가 M인 경우, M이 현재 몇 개가 연속으로 있는지 카운트를 해준다.
현재 문자가 K인 경우, 바로 앞에 있는 M의 개수만큼10^M을 해주고 최댓값은X5, 최솟값은+5를 해준다.
만약 K 앞에 M이 없는 경우(K가 연속으로 나온 경우,5만 더해주면 된다.
(더하는 수는 계산 식을 제외하고는 문자열로 바꾸어서 더해주어야 한다.) - 문자열 탐색이 끝난 후 M이 연속으로 존재하는 경우, 최댓값은 남은 M의 개수만큼 문자열 1을 추가하고 최솟값은 남은 M의 갯수 - 1만큼 10의 제곱을 한 후 더해준다.
최댓값에서 문자열 1을 해주는 이유는 MMMM이 나오면, 1000보다 M을 하나씩 자른1111이 더 크기 때문이다.
(MMMMM 또는 KKMMMKMMMM의 경우, 탐색이 끝난 후에도 M이 남아있기 때문에 후처리를 해주어야 한다.)
코드
s = input()
m = 0 # M의 개수
ans = ['', ''] # 최댓값, 최솟값
for i in s:
if i == 'M': # 현재 문자가 M이면 m 카운트 증가
m += 1
else: # 현재 문자가 K이면
if m: # 바로 앞이 M이면
ans[0] += str(10 ** m * 5) # 최댓값: M의 개수만큼 10을 제곱한 후 5를 곱하여 문자열 추가
ans[1] += str(10 ** m + 5) # 최솟값: M의 개수만큼 10을 제곱한 후 5를 더하여 문자열 추가
else: # 바로 앞이 K이면 최댓값 최솟값 모두 문자 '5' 추가
ans[0] += '5'
ans[1] += '5'
m = 0 # K가 나왔으니 M의 갯수 다시 초기화
if m: # 문자열이 끝났을 때 M이 존재하는 경우(K가 없거나 문자열 중간에 마지막으로 나온 경우)
ans[0] += '1' * m # 최댓값: 남은 M의 수만큼 문자 '1' 추가
ans[1] += str(10 ** (m - 1)) # 최솟값: 남은 M의 수 - 1만큼 10을 제곱한 후 문자열 추가
print('\n'.join(ans))실행 결과
