4일 (14. Longest Common Prefix)

    class Solution {
        
        public String longestCommonPrefix(String[] str) {
            Arrays.sort(str);

            StringBuilder answer = new StringBuilder(); // append, delete, insert 등

            String firstStr = str[0];
            String lastStr = str[str.length - 1];

            for (int i = 0; i < Math.min(firstStr.length(), lastStr.length()); i++) {
                if (firstStr.charAt(i) != lastStr.charAt(i)) {
                    return answer.toString();
                }
                answer.append(firstStr.charAt(i));
            }
            return answer.toString();
        }

    }

* 배열의 요소들의 공통 접두사를 찾아서 반환하거나, 존재하지 않을 경우 공백을 반환하면 된다.

n^2으로 밖에 하지 못해서 솔루션들을 보던 중에 참신한 솔루션이 있어서 그걸로 올림

 

가장 중요하다고 생각한 부분은 Arrays.sort()로 배열을 정렬하는과정이다.

각 배열의 요소중 공통된 접두사를 찾는 것을 목표로 하는 중이다.

ex) {"ab", "abc", "abcd"}의 answer = "ab"

 

그렇다면 굳이 200개까지나 되는 배열의 요소를 모두 비교해야 할 필요는 없다. (문제 제약조건)

특정 문자에 대해 배열의 요소가 200개중 199개가 일치한다고 해도 1개가 일치하지 않는다면 일치하지 않기 때문이다.

 

그렇기 때문에 의미없어보이는 Arrays.sort()로 배열을 정렬하여

배열의 첫 값과 끝 값이 일치하는지만 비교하면 되었다.

 

힙 소트 정렬방식처럼 더 이상 확인해야 할 필요가 없는 부분들을 논리적으로 제거해 나가는 것이 중요하다고 생각되었다.

 

 

 

https://leetcode.com/problems/longest-common-prefix

LeetCode - The World's Leading Online Programming Learning Platform