[백준] 21314번. 민겸 수(JAVA)

문제

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

---

풀이(12분)

import java.io.*;
import java.util.*;

public class Main {

    static final String FIVE = "5";
    static final String ZERO = "0";
    static final String ONE = "1";

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String line = br.readLine();

        String max = findMax(line);
        String min = findMin(line);
        System.out.println(max);
        System.out.println(min);
    }

    static String findMax(String line){ // 최댓값을 찾는 경우
        StringBuilder sb = new StringBuilder();
        int mCnt = 0; // m이 나온 횟수
        for(int i = 0; i < line.length(); i++){
            if(line.charAt(i) == 'K'){ // K를 만났을 때
                sb.append(FIVE); // 일단 5를 추가
                for(int j = 0; j< mCnt; j++){ // 자릿수만큼 0을 추가
                    sb.append(ZERO);
                }
                mCnt = 0;
            }else{
                mCnt++;
            }
        }
        for(int i = 0; i < mCnt; i++){ // 최종적으로 남은 M의 개수만큼 ONE를 +
            sb.append(ONE);
        }

        return sb.toString();
    }

    static String findMin(String line){ // 최솟값을 찾는 경우
        StringBuilder sb = new StringBuilder();
        int mCnt = 0; // m이 나온 횟수
        for(int i = 0; i < line.length(); i++){
            if (line.charAt(i) == 'K'){ // K를 만났을 때
                if(mCnt > 0){ // m이 1개 이상 나왔던 경우만
                    sb.append(ONE); // 1을 추가
                    for(int j = 0; j < mCnt-1; j++){
                        sb.append(ZERO); // 자릿수만큼 0을 추가
                    }
                }
                mCnt = 0;
                sb.append(FIVE); // 최종적으로 5를 추가
            }else{
                mCnt++;
            }
        }
        if(mCnt > 0){ // 1을 추가
            sb.append(ONE);
            mCnt--;
        }
        for(int i = 0; i < mCnt; i++){ // 자릿수만큼 0을 추가
            sb.append(ZERO);
        }

        return sb.toString();
    }

}

---

문제 풀이 전략

 

각자 문제 조건과 자릿수에 맞춰 최댓값과 최솟값을 찾는 전략이다.

 

문자열이 3000자리까지 가능하기에 숫자타입이 아닌 문자열로 진행하자.

 

1️⃣ 최댓값(Max Value) 만들기

1. mCnt = 0 초기화
2. 문자열을 왼쪽부터 순회하며 다음을 반복:
   • 현재 문자가 'K'일 때:
     1. '5' 추가
     2. 지금까지 센 mCnt만큼 '0' 추가
     3. mCnt = 0 초기화
   • 현재 문자가 'm'일 때:
     1. mCnt++
3. 순회가 끝난 후, mCnt가 남아있으면:
   • '1'을 추가하고, mCnt - 1 만큼 '0' 추가 (혹은 mCnt만큼 '0' 추가 depending on convention)

핵심: 'K' 나오면 즉시 5 + 0 반복, 마지막 남은 'm'은 뒤에 1과 0으로 처리

---

2️⃣ 최솟값(Min Value) 만들기

1. mCnt = 0 초기화
2. 문자열을 왼쪽부터 순회하며 다음을 반복:
   • 현재 문자가 'K'일 때:
     1. mCnt > 0이면:
        • '1' 추가
        • '0'을 mCnt - 1만큼 추가
     2. '5' 추가
     3. mCnt = 0 초기화
   • 현재 문자가 'm'일 때:
     1. mCnt++
3. 순회가 끝난 후, mCnt가 남아있으면:
   • '1' 추가
   • '0'을 mCnt - 1만큼 추가

핵심: 'K' 전에 남은 'm'은 1과 0으로, 'K'가 나오면 5를 최대한 뒤로 보내는 전략