리트코드 - 14. Longest Common Prefix

리트코드 - 14. Longest Common Prefix

출처 - https://leetcode.com/problems/longest-common-prefix/submissions/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

여러 문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성합니다.

공통된 접두사가 없는 경우, 빈 문자열 ""을 반환합니다.

 

의사코드

반복문 시작 (i=0부터 strs배열의 첫번째 string의 길이까지 하나씩 순회)     c = strs 배열의 첫번째 string을 가져와서 한글자씩 char로 바꿈       반복문 시작 (         if ( i == 다음 단어 길이 || 다음 단어 char와 c가 다른 경우)             첫번째 String을 0부터 i까지 잘라냄     반복문 종료 strs[0] 리턴 반복문 종료

 

풀이코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);

            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

코드설명

문자열을 자르는 문제이다.

기준값을 배열의 첫번째 String값으로 잡고, 이 String을 잘라서 한개씩 비교해본다.

 

첫번째 문자열이 "abc"라면, a로 잘라서 strs 배열에 모든 string의 첫번째 글자가 a인지 모두 확인한다.
(정확히는 두번째 요소부터 확인한다.)

다음으로 b를 확인하고, c를 확인하는 식이다.

 

만약 값이 다르면 substring(0, i)을 사용하여 바로 앞까지 잘라주면 된다.

 

"abc" 다음 문자열이 "ab"라면 IndexOutOfBound가 뜰 수 있으므로, 다음 문자열 길이에 도달했다면 값을 비교하기 전에 그냥 잘라주면 된다.

 

시간복잡도 - O(n*m) (n은 첫번째 문자열 길이, m은 strs배열 크기)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

첫번째 코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String standard = strs[0];
        char[] c1 = standard.toCharArray();
        String prev = standard;
        String answer = "";
        
        for (int i = 1; i < strs.length; i++) {
            String str = strs[i];
            
            for (int j = 0; j < prev.length(); j++) {
                if (j > str.length() - 1) {
                    break;
                }

                char c2 = str.charAt(j);

                if (c1[j] == c2) {
                    answer += String.valueOf(c2);
                } else {
                    break;
                }
            }
            prev = answer;
            answer = "";
        }

        return prev;
    }
}

처음에는 answer를 계속 갱신하는 방법으로 했었다.

첫번째 요소를 저장해서, 이를 prev에 넣어놓고, 두번째 요소와 비교해서 answer를 만들었다.

그리고 이 값을 prev에 넣고 다시 answer를 초기화하는 방식으로 구현했는데 runtime이 5ms(20%)로 하위권이었다.

 

그동안 풀었던 문제들 때문에 재귀에 빠져있다보니 약간 재귀방식을 구현하려고 했던 것 같다.

 

정리

prefix를 빠르게 비교하는 방법