[Leetcode][C++][난이도 Easy] Longest Common Prefix

Longest Common Prefix 문제 분석

 

[사진 1] Leetcode Longest Common Prefix 문제

 

Leetcode의 난이도 easy 4번째 문제는 longest common prefix 입니다. 위 [사진 1]과 같이, 문자열들이 나열되어 있을 때, 공통적으로 나열된 접두사 (prefix) 문자열을 탐색하고 반환해주면 됩니다. 아래 Example 1에서 "flower", "flow", "flight"는 앞에 "fl" 이라는 접두사가 공통으로 들어가 있기 때문에, "fl"이 반환됩니다. Example 2의 경우, "dog", "racecar", "car" 이므로, 서로 공통으로 갖는 접두사가 없기 때문에 빈 string "" 을 반환해야 합니다. 문제의 조건인 constraints를 보니, 영어 소문자들로만 문자열 목록이 주어진다고 하네요. 

 

 

Longest Common Prefix 문제 해결을 위한 C++ 코드

 

#include <algorithm>
#include <set>

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string result = "";
        int str_size = strs.size();
        
        if (str_size == 1)
        {
            result = strs[0];
            return result;
        }
        
        int flag = 0;
        sort(strs.begin(), strs.end());
        
        
        for (int i = 0; i < strs[0].length(); i++)
        {
            for (int j = 1; j < str_size; j++)
            {
                if (strs[0][i] != strs[j][i])
                {
                    result = strs[0].substr(0,i);
                    flag = 1;
                    break;
                }
            }
            
            if (flag == 1)
                break;
        }
        
        if (flag == 0)
            result = strs[0];
        
        return result;
    }
};

 

제가 작성했던 코드는 위와 같습니다. 문제에서 주어진 함수 longestCommonPrefix의 argument로 문자열 목록을 vector로 받고 있습니다. 우선 최종 결과 string을 result라는 변수에 저장하고 반환할 예정인데요, 빈 스트링 ("")으로 초기화 시켰습니다. 그리고 문자열 목록에 문자열이 몇 개가 저장되어 있는지를 str_size라는 integer 변수에 저장했습니다. 우선 str_size가 1이라면, 문자열 목록에 문자열이 1개밖에 없기 때문에, 비교할 문자열이 없죠? 이 말은 결국 반환할 prefix 문자열도 없다는 의미입니다. 따라서 바로 result를 반환했습니다. 

 

만약 str_size가 2 이상이라면, 주어진 vector strs를 알파벳 순서로 정렬시켰습니다. 이렇게 했던 이유는, 알파벳 순서대로 길이가 제일 짧은 문자열이 vector의 0 번째 인덱스로 오게 되는데요, 0번째 인덱스로 온 문자열을 key로 고려해서, 1번째부터 (str_size - 1)번째 문자열까지 prefix를 탐색하기 쉽다고 생각했습니다. 이후에 등장하는 2중 for loop을 통해, 중복되는 prefix 문자열을 찾는데요, 만약 탐색 중에 서로 다른 문자를 만나게 되면, 지금까지 선택됬던 0번째 문자열의 prefix 문자열을 result에 저장하고 flag를 1로 만들어서 2중 for loop을 탈출합니다. 만약 2중 for loop을 다 돌았는데도 flag가 바뀌지 않았다면, 0번째 문자열이 다른 모든 문자열의 prefix가 된다는 의미이므로, 이 문자열을 result에 저장하고 반환했습니다. 

 

 

Longest Common Prefix 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

[사진 2] Leetcode Longest Common Prefix 문제의 솔루션 코드 중 제일 많은 추천 받은 코드

 

이번에는 다른 사람이 작성한 코드를 살펴보겠습니다. 이 분이 작성한 코드는 처음에 아무런 문자열 목록을 입력받지 않았다면 빈 string을 반환하고 있습니다. 사실 문제에서는 무조건 1개 이상의 문자열을 입력받는다고 명시되어 있었는데요, 이런 식으로 예외처리를 항상 염두해두는 것도 좋은 코드를 작성하는 방법이라고 생각했습니다. 

 

예외처리를 진행하고, 2중 for loop을 진행하는데요, 이 코드와 제가 짠 코드의 차이점은 (아마 아시겠지만) vector를 정렬하지 않고, 그냥 vector의 0번째로 문자열을 key로 잡고 다른 문자열들과 비교하고 있습니다. 지금 생각해보면, prefix가 모든 문자열에 동일하게 존재하는 경우, vector 내 어떤 문자열을 key로 잡든지 간에 상관이 없다는 것을 깨달았습니다. 그리고 구지 flag를 둬서 for loop을 탈출하는 루틴을 만들지 않고, key와 다른 문자가 발견되면, 그 즉시 지금까지 탐색된 prefix 정보를 바로 return 하고 있었습니다. 역시 코딩의 세계는 갈 길이 멀다고 생각했습니다.

 

 

지금까지 leetcode easy 난이도 문제 중 하나였던 longest common prefix 문제를 살펴보았씁니다. 다음 문제도 이어서 포스팅 올리겠습니다!