백준 1474번 - 밑 줄(java, 그리디, 구현)

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

 

무슨말인지 잘 모르겠는 문제인데 해석만하면 그렇게 어려운 문제는 아니다. 그러나 문자열을 다루는데 익숙하지 않다면 조금 어려울 수도 있다.

 

사전순으로 앞에 온다는 의미를 잘 해석해야하는데 나도 이것을 잘 못해서 이게 왜 실버1이지 싶었다. 사전순이란 

AABBB

AAABB 

 

-> AAABB 가 먼저온다. 즉, 밑줄 보다 우선순위가 높은 대문자 앞에는 밑줄이 되도록 오지 않는 것이 좋다.

 

AAA_BBaa

AA_ABBaa

 

-> AAA_BBaa 가 먼저온다.  

 

AAA_BBaa

AAABBa_a

 

-> AAABBa_a 가 먼저온다 

 

이제 느낌이 올것이다. 문자열을 탐색하며 먼저 소문자 앞에 밑줄들을 추가하고 만약 더 이상 소문자가 없다면 뒤쪽에 있는 대문자 앞에 밑줄을 추가하면 된다.

 

그래서 이 문제는 그리디 알고리즘이 된다.

 

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);

        ArrayList<String> arrayList = new ArrayList<>();
        int allSize = 0;
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            arrayList.add(str);

            allSize += str.length();
        }

        int cnt = (M - allSize) / (N - 1);
        int tm = (M - allSize) % (N - 1);
        String line = "";
        for(int i = 0; i < cnt; i++){
            line += "_";
        }

        for(int i = 0; i < arrayList.size() - 1; i++){
            arrayList.set(i, arrayList.get(i) + line);
        }

        boolean flag = false;
        if((M - allSize) % (N - 1) != 0){
            for(int i = 1; i < arrayList.size(); i++){
                if(arrayList.get(i).charAt(0) <= 'z' && arrayList.get(i).charAt(0) >= 'a'){
                    arrayList.set(i - 1, arrayList.get(i - 1) + "_");
                    tm--;
                }
                if(tm == 0) {
                    flag = true;
                    break;
                }
            }

            if(!flag){
                for(int i = arrayList.size() - 1; i > 1; i--){
                    if(arrayList.get(i).charAt(0) <= 'Z' && arrayList.get(i).charAt(0) >= 'A'){
                        arrayList.set(i - 1, arrayList.get(i - 1) + "_");
                        tm--;
                    }
                    if(tm == 0) {
                        break;
                    }
                }
            }
        }

        for(int i = 0; i < arrayList.size(); i++){
            System.out.print(arrayList.get(i));
        }
    }
}