BOJ_2179_비슷한 단어 (Java, C++)

[Gold III] 비슷한 단어 - 2179

문제 링크

성능 요약

메모리: 2856 KB, 시간: 0 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열

제출 일자

2024년 12월 6일 17:12:10

문제 설명

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

문제 풀이

먼저 푼 방법은 완전탐색이다. 반복문을 통해 O(N^2)에도 통과할 것 같아 바로 Java로 작성후 통과했다.

이후 좋은 풀이를 탐색 하던 중 HashMap을 활용해 Key에 문자를 넣고 그 인덱스를 Value로 넣어 i, j 형식으로 i문자열에서 j문자열을 모두 쪼개 패턴매칭해보며 최대길이를 찾았고 그 인덱스를 res1 res2에 기억해두었다. 해당 로직은 c++로 작성해봤다.

코드

Java코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N;
    static String[] arr;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2179_비슷한단어/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new String[N];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }

        int max = 0;
        String str1 = "", str2 = "";
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int len = getLen(arr[i], arr[j]);
                if (len > max) {
                    str1 = arr[i];
                    str2 = arr[j];
                    max = len;
                }
            }
        }

        bw.write(str1 + "\n" + str2);

        bw.flush();
        bw.close();
        br.close();
    }

    private int getLen(String s1, String s2) {
        int minLen = Math.min(s1.length(), s2.length());
        int cnt = 0;
        for (int i = 0; i < minLen; i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                cnt++;
            } else break;
        }
        return cnt;
    }

}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N;
    cin >> N;

    vector<string> arr(N);

    map<string, int> prefixMap;
    int res1 = 0, res2 = 1;
    int maxLen = 0;

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        string str = arr[i];

        for (int j = str.length(); j >= 1; j--) {
            string pattern = str.substr(0, j);
            if (pattern.length() < maxLen) break;

            /*
            map.find(key)는:

            키를 찾으면 해당 요소를 가리키는 반복자(iterator)를 반환
            키가 없으면 map.end()를 반환

            그래서 it != map.end()는 "키가 존재한다"는 의미.
            */
            auto p = prefixMap.find(pattern);
            if (p != prefixMap.end()) {
                if (pattern.length() == maxLen && prefixMap[pattern] > res1)
                    break;

                if (pattern.length() == maxLen && prefixMap[pattern] == res1 &&
                    res2 < i)
                    break;

                res1 = prefixMap[pattern];
                res2 = i;
                maxLen = pattern.length();
                break;
            }
            prefixMap[pattern] = i;
        }
    }
    cout << arr[res1] << "\n" << arr[res2] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}