[백준 1474] 밑 줄 - JAVA

BOJ Link

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

 

 

 

 

풀이 과정

 

1. 채워야할 _ 개수를 구하는 방법

 

M => 만들어야 할 단어 길이

N => 사용할 단어의 개수

S => N개 단어의 길이 합

U => 빈 공간의 개수 == N - 1

 

min : (M - S) / U => 빈 공간마다 필요한 최소 _의 개수

remain : (M - S) % U => 추가로 사용해야 할 _ 개수

 

remain = 0이라면, 모든 빈 공간을 같은 개수의 _로 채울 수 있음을 의미한다.

0이 아니라면, 일단 모든 빈 공간을 min 개수로 채운다.

이후 각 공간마다 최대 1개씩 더하며 remain을 0으로 만든다.

• 모두 같게 만드는 것이 불가능한 경우 단어와 단어 사이에 있는 _의 개수의 최댓값과 최솟값의 차이는 1이 되어야 한다.

 

2.  1개씩 더 하며, 사전 순으로 앞서는 방법 (그리디)

 

'A' ~ 'Z' < '_' < 'a'  ~ 'z' 이므로,

 

2-1. 소문자로 시작하는 단어 중 앞부터 _를 1개 더한다.

2-2. 대문자로 시작하는 단어 중 뒤부터 _를 1개 더한다.

 

시간 복잡도는 충분하므로 두 번 탐색해도 된다.

단순히 2-1을 수행한 이후에, 대문자 비교 없이 뒤부터 채우지 않은 곳을 채워주면 된다.

 

3. 헷갈렸던 점

 

spot[2]을

"2번째 단어의 앞"으로 설정할지

"2번째 빈 공간"으로 설정할지 명확히 해야한다.

 

2번째 단어의 앞은 1번째 빈 공간이 되기 때문이다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main2 {
    public static void main(String[] args) throws IOException {

        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]);
        int U = N - 1;
        int S = 0;

        String[] strings = new String[N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            strings[i] = s;
            S += s.length();
        }

        int remain = (M - S) % U;
        int min = (M - S) / U;

        String under = "";

        for (int i = 0; i < min; i++) {
            under += "_";
        }
        String under2 = under + "_";

        boolean[] spot = new boolean[U];

        // 소문자 마킹
        for (int i = 1; i < N; i++) {

            if (remain == 0) break;

            if (strings[i].charAt(0) > 'Z') {
                spot[i - 1] = true;
                remain--;
            }
        }

        // 대문자 마킹
        for (int i = N - 1; i > 0; i--) {

            if (remain == 0) break;

            if (!spot[i - 1]) {
                spot[i - 1] = true;
                remain--;
            }
        }

        for (int i = 0; i < N - 1; i++) {
            System.out.print(strings[i]);
            System.out.print(spot[i] ? under2 : under);
        }
        System.out.print(strings[N - 1]);
    }
}