[코딩테스트] 백준 - 유사 라임 게임

유사 라임 게임 24431번 [15일차]

시간제한	메모리 제한
1초	512MB

문제

Alice는 영어 단어를 조합하여 라임(Rhyme)을 만드는 단어 게임을 즐겨한다. Bob도 라임을 만들고 싶지만, 아직 어려서 단어를 잘 모르기 때문에 Alice가 "유사 라임 게임"을 제안했다.

먼저, 영문 대문자로만 구성된 길이가 L인 서로 다른 단어 n개를 종이에 적는다: 편의상 W1,W2,…Wn을 n개의 단어라 하자.

어떤 한 쌍의 단어 Wi와 Wj를 비교했을 때 최대 공통 접미사의 길이가 F이상이면 두 단어는 "유사 라임"을 이룬다고 정의한다. 이러한 단어 쌍을 "유사 라임 쌍"이라 부르자.

"유사 라임 게임"은 주어진 단어들을 이용하여 최대한 많은 "유사 라임 쌍"을 만드는 게임이다. 단, 한 단어는 최대 하나의 유사 라임 쌍에만 속할 수 있다.

예를 들어 n=4, L=4일때, 4개의 단어가 다음과 같다고 하자: W1= "WALK", W2= "TALK", W3= "MILK", W4= "BULK".

• 만약 F≤2라면, 아무렇게나 두 쌍으로 묶어도 유사 라임 쌍이 되므로 2개의 쌍을 찾을 수 있다. 예를 들면 ("WALK", "BULK"), ("TALK","MILK")가 있다.
• 만약 F=3라면, ("WALK", "TALK")를 묶어 하나의 유사 라임 쌍을 만들 수 있지만, 2개 이상을 만들 방법은 없다.
• 만약 F≥4라면, 유사 라임 쌍을 만들 방법은 없다.

입력으로 F 그리고 길이가 L인 n개의 단어가 주어졌을 때, Bob이 만들 수 있는 최대 개수의 "유사 라임 쌍"이 몇 개인지 구해보자.

 

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 입력은 두 줄에 걸쳐 주어진다. 첫 줄에 n, L, F가 공백으로 구분되어 주어진다. 둘째 줄에 영문 대문자로만 구성된 길이 L인 문자열 n개 W1,W2,…Wn이 공백으로 구분되어 주어진다.

 

출력

각 테스트 케이스의 정답을 각 줄에 출력한다.

 

제한

•  1≤T≤10
•  1≤F≤L≤10
•  2≤n≤500
• 각 문자열 Wi는 알파벳 대문자로만 구성되어 있다.
• 각 테스트 케이스에 주어지는 n개의 문자열은 중복되지 않는다.

 

나의코드

package day15;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

// 유사 라임 게임 -  24431번
public class Solution2 {
    public static void main(String[] args) throws IOException {

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

        // 테스트 케이스
        int T = Integer.parseInt(br.readLine());

        for(int i = 0;i < T;i++){
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st1.nextToken());
            int L = Integer.parseInt(st1.nextToken());
            int F = Integer.parseInt(st1.nextToken());

            String[] word = new String[n];

            Set<String> set  = new HashSet<>();
            int count = 0; // 유사 라임 쌍의 수

            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j =0; j <n;j++) {
                word[j] = st2.nextToken();
            }

            for (int j = 0; j < n; j++) {
                // 각 단어의 길이 L에서 마지막 F 글자를 추출
                String substring = word[j].substring(L - F, L);

                // 접미사가 이미 Set에 존재하는 경우, 유사 라임 쌍을 하나 만들 수 있음
                if (!set.contains(substring)) {
                    // 접미사가 Set에 없으면 추가
                    set.add(substring);
                } else {
                    // 접미사가 이미 존재하면 유사 라임 쌍을 형성할 수 있음
                    count++;
                    // 이미 존재한 접미사는 제거하여 중복 사용 방지
                    set.remove(substring);
                }
            }

            // 결과를 StringBuilder에 추가
            sb.append(count).append('\n');

        }
        // 모든 테스트 케이스에 대한 결과 출력
        System.out.print(sb);

    }


}