백준 2179 - 비슷한 단어 Java

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

2179번: 비슷한 단어

문제

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

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

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

입력

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

출력

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

예제 입력 1 

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력 1 

noon
noone

예제 입력 2 

4
abcd
abe
abc
abchldp

예제 출력 2 

abcd
abc

 

문제 해설 

처음엔 그냥 문자열 하나씩 잘라서 비교하면서 했다가 시간초과를 맞았다. 그리고 고민고민 하다가 다른 분의 풀이를 보고

다시 시도하였다. Set으로 바꾸려고 바꾸고 나서 문제를 다시 읽어보니 순서가 있었다.... 들어온 문자열의 순서대로... 출력을 해야 하는 경우도 있었기에 Set은 사용하면 안됐는데.. 여튼 3가지 코드를 공유한다. 
정답 코드의 출처는 https://iheeeee6-6.tistory.com/m/93 입니당

그냥 반복문으로 구성된 코드

문자열을 입력받을 때마다 하나씩 잘라서 기존의 문자열들과 비교, 조건에 맞게 가장 긴 문자열과 길이를 저장하는 방식으로 돌렸는데 시간초과 발생.

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class BJ_2179_비슷한단어 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String target = "";
        String result = "";
        int maxLength=0;
        List<String> list = new ArrayList<>();
        for(int i=0; i<N; i++)
        {
            String str = br.readLine();
            String temp = "";
            for(int j=0; j<str.length(); j++)
            {
                temp += str.charAt(j);
                for(int k=0; k<list.size(); k++)
                {
                    if(list.get(k).contains(temp) && !list.get(k).equals(temp))
                    {
                        if(maxLength < temp.length())
                        {
                            target = list.get(k);
                            result = str;
                            maxLength = temp.length();
                        }
                    }
                }
            }
            list.add(str);
        }
        System.out.println(target);
        System.out.println(result);

    }
}

 

Set으로 구성된 코드

Set으로 짰는데.. 근데.. 생각해보니 문제의 조건에 먼저 들어온 순으로 출력하라고 되어 있다. 이걸 왜 늦게봤을까.. 문제를 잘 읽어야겠다.

package BOJ;

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

public class BJ_2179_비슷한단어 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String target = "";
        String result = "";
        int maxLength=0;
        Set<String> set = new HashSet<>();

        for(int i=0; i<N; i++)
        {
            String str = br.readLine();
            set.add(str);
        }
        Iterator<String> iterator = set.iterator();
        String main = "";
        String sub = "";

        while(iterator.hasNext())
        {
            String str = iterator.next();
            Iterator<String> subIterator = set.iterator();
            while(subIterator.hasNext())
            {
                String str2 = subIterator.next();
                if(str.equals(str2))
                {
                    continue;
                }

                int length = 0;
                int size = Math.min(str.length(), str2.length());
                for(int i=0; i<size; i++)
                {
                    if(str.charAt(i)==str2.charAt(i)) length++;
                    else break;
                }
                if(length > maxLength)
                {
                    main = str;
                    sub = str2;
                    maxLength = length;
                }
            }
        }
        System.out.println(main);
        System.out.println(sub);
    }
}

 

정답 코드

리스트에 문자열을 다 넣어놓고, 문자열을 하나씩 꺼내보면서 다른 문자열과 비교하는 방식이다.

두 문자열의 길이 중 가장 짧은것을 기준으로 문자 탐색을 진행하며, 둘이 같다면 count를 ++ 해줌으로써 문자열 중 얼마나 같은지를 체크하고, 지금까지 중 가장 긴 부분문자열과 count를 비교하여 값을 갱신하는 방식으로 구현되어 있었다.

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;


public class BJ_2179_비슷한단어 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<String> list = new ArrayList<>();
        for(int i=0;i<n;i++) {
            String s= br.readLine();
            if(!list.contains(s))
                list.add(s);
        }

        int resultStr1=0;
        int resultStr2=0;
        int maxCount=0;
        for(int i=0;i<n;i++) {
            String str1 = list.get(i);
            for(int j=i+1;j<n;j++) {
                int count=0;
                String str2=list.get(j);
                int size=Math.min(str1.length(),str2.length());
                for(int z=0;z<size;z++) {
                    if(str1.charAt(z)==str2.charAt(z)) count++;
                    else break;
                }
                if(count>maxCount) {
                    resultStr1=i;
                    resultStr2=j;
                    maxCount=count;
                }
            }
        }

        System.out.println(list.get(resultStr1));
        System.out.println(list.get(resultStr2));
    }
}