백준 24431번 유사 라임 게임 Java

: ) YOUNG·2024년 9월 20일
1

알고리즘

목록 보기
399/417

백준 28064번 유사 라임 게임 Java

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

문제



생각하기


  • 문자열, 구현 문제이다.
  • HashMap을 통해서 푸는게 더 빠르다.


동작

접미사이므로 뒤를 기준으로 생각.

HashMap에서 부분문자열을 저장.

쌍을 기준으로 숫자를 세기 때문에,


        int ans = 0;
        for (int value : map.values()) {
            if (value >= 2) {
                ans += value / 2;
            }
        }


결과


코드


endsWith

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, L, F;
    private static String[] arr = new String[501];

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            input();

            bw.write(solve());
        }

        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int count = 0;
        boolean[] isVisited = new boolean[N];
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (!isVisited[i] && !isVisited[j] && arr[i].endsWith(arr[j].substring(L - F))) {
                    isVisited[i] = true;
                    isVisited[j] = true;
                    count++;
                }
            }
        }

        sb.append(count).append('\n');
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = st.nextToken();
        }
    } // End of input()
} // End of Main class

HashMap


import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, L, F;
    private static String[] arr = new String[501];

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            input();

            bw.write(solve());
        }

        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String subStr = arr[i].substring(L - F);
            map.put(subStr, map.getOrDefault(subStr, 0) + 1);
        }

        int ans = 0;
        for (int value : map.values()) {
            if (value >= 2) {
                ans += value / 2;
            }
        }

        sb.append(ans).append('\n');
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = st.nextToken();
        }
    } // End of input()
} // End of Main class

0개의 댓글