[LeetCode] 14. Longest Common Prefix

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

Longest Common Prefix - LeetCode

자신감을 되찾기 위한 쉬운 문제였는데, 문제에게 농락당함 😂

분명 방법을 어떻게 해야할 지 알았는데, 항상 예외를 마주치는 코드가 되어있었다..

 

+ 예외 케이스 해결해서 이 코드도 작동을 했다 !

케이스 : ["ac","ac","a","a"]

추가조건 :

                    if(j == len-1 && common[j] == next[j]){
                        prefix = prefix.substring(0,j+1);
                    }

작동 코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // null 일 경우
        if (strs == null){
            return "";
        }
        // 요소가 하나일 경우
        if(strs.length == 1){
            return strs[0];
        }

        // 비교할 요소가 2개 이상인 경우
        String prefix = "";
        for (int i = 0; i < strs.length; i++) {
            // 하나라도 공백이면 공백 리턴
            if(strs[i].equals("")){
                return "";
            }

            // 0, 1 요소 비교
            if(i == 0){
                char [] first = strs[0].toCharArray();
                char [] second = strs[1].toCharArray();
                int len = Math.min(first.length, second.length);
                for (int j = 0; j < len; j++) {
                    if(first[j] == second[j]){
                        prefix += first[j];
                    }else {
                        break;
                    }
                }
            }

            // 세 번째 요소부터
            if(i > 1 && !strs[i].startsWith(prefix)){    //prefix = "flow"
                char [] common = prefix.toCharArray();
                char [] next = strs[i].toCharArray();   //"flig"
                int len = Math.min(common.length, next.length);
                for (int j = 0; j < len; j++) {
                    if(j == len-1 && common[j] == next[j]){
                        prefix = prefix.substring(0,j+1);
                    }
                    if(common[j] != next[j]){
                        prefix = prefix.substring(0,j);
                        break;
                    }
                }
            }
        }
        return prefix;
    }
}

 

다른 풀이

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }

        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            // prefix로 시작하지 않을 때
            while (strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0, prefix.length()-1);
            }
        }
        return prefix;
    }
}

느낀 점

1. 첫번째 요소와 두번째 요소를 따로 비교할 필요없이 prefix를 첫번째 요소로 설정한 뒤 작업을 진행하는 것이 낫다.

2. indexOf 에 대한 이해가 부족했다. 같은 prefix를 포함하고 있는 문자열이라면 indexOf(prefix) == 0 이어야 한다. 가장 첫 index를 반환하기 때문이다. 이 때, 0이 아니라면 prefix에 알맞지 않은 문자가 포함된 것이므로 현재 prefix의 뒤부터 한글자씩 지운다. (indexOf(prefix) == 0 이 될때까지) substring 사용 => while문을 통해 반복해서 모든 요소에 맞는 prefix를 찾는다.

 

쉬워보이는 문제여도, 사용하는 함수에 대한 명확한 이해 없이는 문제 풀이가 산으로 가거나, 길어지거나, 예외에 대비하지 못하는 경우가 발생한다. 기본을 탄탄히 다지자 👩‍💻