문제 푼 날짜 : 2021-11-24

문제

문제 링크 : https://leetcode.com/problems/longest-common-prefix/

접근 및 풀이

엄청 간단해보이지만 바로 풀이가 떠오르지 않았는데, 생각을 차근차근하다보니 떠올랐다.
풀이는 비교적 간단하다.

1. 주어진 문자열 배열에서 가장 짧은 문자열을 찾는다.
2. 가장 짧은 문자열의 길이를 기준으로 모든 문자열의 앞자리부터 prefix를 비교해준다.
3. prefix가 일치하지 않는 곳을 찾는다면, 그 위치에서 stop
4. 멈춘 위치까지 substr로 가장 짧은 문자열을 잘라주고, return 해준다.

코드

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) {
            return "";
        }
        
        string shortStr = strs[0];
        int minLen = strs[0].length();
        
        for (int i = 1; i < strs.size(); i++) {
            if (strs[i].length() < minLen) {
                shortStr = strs[i];
                minLen = strs[i].length();
            }
        }
        
        bool prefixCheck = true;
        int i;
        for (i = 0; i < minLen; i++) {
            for (int j = 0; j < strs.size(); j++) {
                if (strs[j] == shortStr) {
                    continue;
                }
                if (strs[j][i] != shortStr[i]) {
                    prefixCheck = false;
                    break;
                }
            }
            if (!prefixCheck) {
                break;
            }
        }
        return shortStr.substr(0, i);
    }
};

결과

피드백

최근에 알고리즘 문제 풀이가 뜸해서 그런지 감을 잃은 것 같다.
LeetCode를 추천받아서 Easy문제부터 풀고 있는데, 난이도가 낮은데도 문제 풀이를 떠올리는게 쉽지 않았다. 물론, ps를 조금 쉰 것이 영향이 있을 수도 있겠지만...
진작에 LeetCode를 풀었다면 어땠을까 싶을 정도로 문제의 질이 좋은 것 같다.
앞으론 LeetCode 위주로 문제를 풀어야겠다.