[백준] 2179: 스카이라인 쉬운거 - JAVA

13 Oct 2023 in Algorithm on 자료 구조

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

풀이

영단어들이 주어지고 두 단어를 앞에서부터 비교하여 공통적으로 나타나는 부분의 길이가 긴 두 단어를 출력해야한다.

한글자씩 비교하기 위해 트라이 알고리즘을 생각했으나, 시간이 충분하고 메모리 제한이 작아서 트라이를 사용하지 않았다.

길이가 같을 경우 주어진 순서대로 앞쪽에 있는 단어가 답이되므로 순서 유지가 되는 ArrayList를 선택했다.

ArrayList에 단어를 담고 앞에서 부터 순서대로 비교하여 접두사의 길이와 인덱스를 저장했다.

---

메모리: 19328KB

시간: 2008ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            if (!list.contains(word)) {
                list.add(word);
            }
        }

        int max = 0;
        int idx_s = 0;
        int idx_t = 1;
        for (int i = 0; i < list.size() - 1; i++) {
            String s = list.get(i);

            for (int j = i + 1; j < list.size(); j++) {
                String t = list.get(j);

                int tmp = 0;
                for (int k = 0; k < Math.min(s.length(), t.length()); k++) {
                    if (s.charAt(k) == t.charAt(k)) {
                        tmp++;
                    } else {
                        break;
                    }
                }

                if (tmp > max) {
                    max = tmp;
                    idx_s = i;
                    idx_t = j;
                }
            }
        }

        System.out.println(list.get(idx_s));
        System.out.println(list.get(idx_t));
    }

}