[ICPC] Problem C - 행복 점수 (Java)

이 문제는 오늘 다녀온 ICPC 예선전에서 C번 문제로 나왔던 행복 점수이다.

 

문제 지문

코로나 19 이후 우울함에 빠져 있는 소년 짐은 세상의 모든 짐을 지고 있는 느낌이다. 짐은 친구들의 행복 정도를 측정하고 싶어졌다. 짐이 생각한 한 가지 방법은 친구들이 보낸 문자 메시지를 분석하여 친구들이 행복한지 판단하는 것이다. 문자 메시지의 글자가 단어 "HAPPY"에 나타나면 그 글자는 행복한 글자이고 단어 "SAD"에 나타나면 그 글자는 우울한 글자이다. 글자 'A'는 양쪽에 모두 나타나므로 행복하기도 하고 우울하기도 한 글자이다. 글자 'B'는 어느 쪽에도 나타나지 않으므로 행복하지도 않고 우울하지도 않은 글자이다.

 

메시지의 행복 지수는 우울 점수를 이용하여 계산하는데, 행복 점수와 우울 점수는 글자가 행복한 글자인지 우울한 글자인지 여부에 따라 계산한다. 어떤 글자가 행복하면 행복 점수 P(H)를 증가시키고 어떤 글자가 우울하면 우울 점수 P(G)를 증가시킨다. 행복 지수 H는 다음과 같이 계산한다.

H = P(H) / (P(H) + P(G))

 

지문 요약

결국엔 입력받은 문장에서 "HAPPY" 즉, {'H', 'A', 'P', 'Y'} 중 하나가 포함될 때마다 P(H)를 증가시키고 "SAD"도 마찬가지로 P(G)를 증가시킨 다음, 위의 수식을 이용해서 결과 값을 도출하는 문제이다.

 

 

Sample Input

SAD MOVIES ALWAYS MAKE ME CRY

Output for the Sample Input

42.86

 

 

문제 해설

먼저 입력받은 문장을 split으로 쪼갠 문자들을 String 배열에 담은 다음, 원소 하나씩 Happy 혹은 Sad 문자열에 포함되는지를 검사하기 위해 KMP 알고리즘을 사용했다.

 

package ICPC;

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Board {

    public static int[] computePrefixArray(String pattern) {

        int[] lps = new int[pattern.length()];

        int index = 0;

        for (int i = 1; i < pattern.length();) {

            if (pattern.charAt(i) == pattern.charAt(index)) {

                lps[i] = index + 1;

                index++;

                i++;

            } else {

                if (index != 0) {

                    index = lps[index - 1];

                } else {

                    lps[i] = 0;

                    i++;

                }

            }

        }

        return lps;

    }

    public static boolean KMPsearch(String text, String pattern) {

        int[] lps = computePrefixArray(pattern);

        int j = 0;

        int i = 0;

        while (i < text.length() && j < pattern.length()) {

            if (text.charAt(i) == pattern.charAt(j)) {

                i++;

                j++;

            } else {

                if (j != 0) {

                    j = lps[j - 1];

                } else {

                    i++;

                }

            }

        }

        return j == pattern.length();

    }

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String sad = "SAD";

        String happy = "HAPY";

        int sad_cnt = 0;

        int happy_cnt = 0;

        String input = br.readLine();

        String[] input_arr = input.split("");

        for (int i = 0; i < input_arr.length; i++) {

            if (KMPsearch(sad, input_arr[i])) {

                sad_cnt++;

            }

            if (KMPsearch(happy, input_arr[i])) {

                happy_cnt++;

            }

        }

        float H = 0;

        if(happy_cnt == 0 && sad_cnt == 0){

            H = (float)0.5;

        }else{

            H = (float)happy_cnt/(happy_cnt + sad_cnt);

        }

        String answer = String.format("%.2f" ,Math.round(H*10000)/ 100.0);

        System.out.println(answer);

    }

}