[LeetCode - Easy] 14. Longest Common Prefix

해석과 풀이는 개인적인 부분이기 때문에 참고만 하시길 바랍니다. 다른 접근 및 풀이는 언제나 환영합니다. 댓글로 남겨주세요.

1. 문제

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]

Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation: There is no common prefix among the input strings.

2. 해석

주어진 배열에서 공통적으로 들어가는 가장 긴 prefix를 추출해서 반환한다.

3. 풀이

- 이번 문제를 엉망진창으로 풀어서 leetCode 고수분의 풀이로 바로 가시길 추천한다. (정신건강에 해롭습니다ㅠㅠ)

- 핑계를 좀 대자면 prefix라는 것을 잊어버리고 공통적으로 들어가 있으면서 긴 문자열을 찾는 문제로 착각을 했다. 암튼 나의 풀이는...

 

 ① 배열에 공통적으로 들어가 있을 것이기에 배열의 길이(length) 만큼 공통횟수(commonCnt)가 나올 것이고

 ② 배열을 1차 for문 돌려서 각 문자열을 가져와 내부 2차 반복문으로 문자를 하나씩 분리해서 재조합을 했다.

예를들면, flower는 f, fl, flo, flow, flowe, flower 이런식으로 재조합한 문자열을 map에 담았다.(key가 문자열이고 value는 반복횟수, 초기값은 0)

③ map을 돌리면서 다시 배열과 비교하여 중복되는 문자열이 있으면 해당 문자열에 반복횟수(value)를 올렸다. 여기서 비교할 때 indexOf()가 아닌 prefix를 찾아야해서 startsWith()를 사용했다.

④ map에 반복횟수(value)가 공통횟수(commonCnt)와 동일하고 prefix길이가 가장 긴 문자열(key)을 찾도록 했다.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        // 공통적으로 모두 가지고 있어야하기에 배열의 길이만큼 횟수를 가지고 있어야 한다.
        int commonCnt = strs.length;
        
        // 배열의 각 요소 하나씩 꺼내서
        for(int i=0; i<strs.length; i++) {
            String tmp = "";
            
            // 단어를 한 문자씩 쪼개어 재조합
            for(int j=0; j< strs[i].length(); j++) {
                tmp += strs[i].charAt(j); // ex) f, fl, flo, flow 이런 식으로 문자열 재조합하여 map의 key에 저장
                map.put(tmp, 0); // 초기 value값은 0
            }
        }
        
        // map을 돌리며 처음 주어진 배열의 문자열과 비교하여 겹치는 카운트를 map의 value로 업데이트
        for(Map.Entry<String, Integer> e : map.entrySet()) {
            String comp = e.getKey();
            int cnt = 0;
            
            for(int i=0; i<strs.length; i++) {
                if(strs[i].startsWith(comp)) { // prefix를 찾아야하기에
                    cnt++;
                    map.put(comp, cnt);
                }
            }
        }
        
        // 배열길이 만큼 반복 횟수를 가진 문자열 중에서 긴 문자열 길이를 찾는다.
        int longestCnt = 0;
        for(Map.Entry<String, Integer> e : map.entrySet()) {
            int size = e.getKey().length();
            
            if(e.getValue() == commonCnt && longestCnt < size) {
                longestCnt = size;
            }
        }
        //System.out.println("longestCnt => "+ longestCnt);
        
        
        // 두 조건(횟수와 긴 문자열)을 만족하는 문자열을 반환한다.
        String rtnStr = "";
        for(Map.Entry<String, Integer> e : map.entrySet()) {
            
            if(e.getKey().length() == longestCnt && e.getValue() == commonCnt) {
                //System.out.println("return => " + e.getKey());
                rtnStr = e.getKey();
            }
        }
        
        return rtnStr;
    }
}

- map과 for문을 남발한, 정신이 혼미한 하수의 코드다.😭

- 거추장스럽고 복잡하게 쥐어짠 느낌이랄까ㅠㅠ

 

4. LeetCoder의 접근 및 풀이

- 일단 주어진 배열을 알파벳순(사전순)으로 정렬을 한다.

- 배열을 정렬한 뒤 첫 번째과 마지막 문자열을 비교해서 첫 번째 문자열의 접두사와 마지막 문자열의 접두사가 같다면 공통 접두사를 찾을 수가 있다. (알파벳순으로 정렬했기때문에 가운데 문자열은 안봐도 공통 접두사가 있음은 자명하다.)

- 예를 들어, 문자열 {"flower", "flow", "flight"} 의 경우 배열을 정렬하면 {"flight", "flow", "flower"} 이 상태이고 'flight' 와 'flower'를 앞 문자부터 하나씩 비교해보면 'f'와 'l'까지는 동일한데 세번째 'g'와 'o' 에서 갈린다. 즉 두번째 문자까지만 동일하기에 가장 긴 접두사의 길이가 2가 되고 반환되는 접두사는 'fl'이 된다. 

→ 어떻게 이런 사고를 할 수가 있을까!! 물 흐르듯 자연스럽다.👍

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 우선 배열을 정렬한다.
        Arrays.sort(strs);
        String s1 = strs[0];
        String s2 = strs[strs.length-1];
        
        int idx = 0;
        String rtnStr = "";
        // 공통 접두사가 어디까지 같을지 모르기에 문자열 길이만큼 반복한다.
        while(idx < s1.length() && idx < s2.length()){
            if(s1.charAt(idx) == s2.charAt(idx)){ // 비교하여 같을 경우 최종 idx가 접두사길이가 된다.
            	rtnStr += s1.charAt(idx);
                idx++;
            } else {
                break;
            }
        }
        return rtnStr;
    }
}

- 코드 역시 심플 그 잡채!!