99클럽 코테 스터디 16일차 - 백준 , 비슷한 단어

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

1. 단어 N개가 주어진다.

2. 두 단어를 비교해서 가장 비슷한 두 단어를 출력하면된다.

3. 비슷한 것의 기준은 같은 접두사의 길이가 길면 비슷한 것이다.

4. 만약 최대로 겹치는 값이 여러개 일 경우에는 앞쪽에 있는 단어를 우선으로 한다.

문제 풀이

1. 시간도 널널하고 비교적 데이터의 수가 20,000개로 많지 않기 때문에 단순 비교로 풀이 가능

2. 앞에 단어부터 시작해서 비교해가면서 max값보다 겹치는 접두사의 길이가 크다면 변경해주고 인덱스를 저장해준다.

3. 자세한것은 코드 참조

소스코드

package online.judge;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Duplication {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] strArr = new String[n];

        for (int i = 0; i < n; i++) {
            strArr[i] = br.readLine();
        }

        int a = 0, b = 0, max = 0;
        for (int i = 0; i < n-1; i++) {
            //현재 최대 값 보다 짧은 길이라면 pass
            if(max > strArr[i].length()) continue;
            for (int j = i + 1; j < n; j++) {
                //현재 최대 값 보다 짧은 길이라면 pass
                if(max > strArr[j].length()) continue;

                //비교 횟수 짧은 문자열 만큼
                int repeat = Math.min(strArr[i].length(), strArr[j].length());

                //반복되는 문자 개수 세기
                int cnt = 0;
                for (int k = 0; k < repeat; k++) {
                    if(strArr[i].charAt(k) != strArr[j].charAt(k)) break;
                    cnt++;
                }

                //max값보다 크다면 저장
                if(max < cnt){
                    max = cnt;
                    a = i;
                    b = j;
                }
            }
        }

        System.out.println(strArr[a]);
        System.out.print(strArr[b]);
    }
}

 

 

TIL

• 풀이했던 문제라 쉽게 풀이했다.