Leetcode 14. Longest Common Prefix

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

 

질문1

특정 인덱스의 문자가 일치한다는 것을 표시하기 위해 for문이 다 돌았을 때 문자를 추가해서 출력할 결과 변수에 넣어주도록 작성했는데 예외가 발생했다. 중간 문자가 불일치하고 다시 일치하는 인덱스일 경우를 생각치 못하여 이 때는 종료하도록 flag를 추가하였다.

그런데 예외 케이스를 하나씩 if로 추가해서 break를 거는 게 좋은 코드인지 모르겠다. 답을 알려주지 말고 내가 자연스럽게 과정을 유추할 수 있도록 아주 작은 힌트만 줘. 혹시 내가 접근을 잘못했니?

답변1

코드가 동작하긴 하지만, 좀 더 단순화할 여지가 있어 보입니다.

공통 접두사를 찾는 건데, 첫 번째 문자열을 기준으로 삼는 접근은 좋습니다 그런데 지금은 각 문자 위치마다 모든 문자열을 비교하고 있죠 만약 어떤 위치에서 하나라도 다른 문자가 나오면... 그게 의미하는 건 뭘까요? 그리고 check 변수가 하는 일을... 다른 방식으로 할 수 있지 않을까요?

여러 개의 break와 flag 변수(check) 대신, 문제의 본질에 더 가까운 방식으로 접근할 수 있을 것 같아요. 공통 접두사가 깨지는 순간에 대해 생각해보세요.

 

질문2

if 예외를 체크하는 순서가 중요하지 않니? 조건을 잘못 체크한 걸까?

답변2

"공통 접두사가 끊기는 순간"에 대해 생각해보세요.

'o' vs 'o' (일치)
'o' vs 'i' (불일치)

이 시점에서 우리가 아는 건 뭘까요? 더 비교할 필요가 있을까요? check 변수 없이도 이 "깨짐"을 표현할 수 있지 않을까요?

현재 코드는

1. 매 위치(k)마다 모든 문자열을 확인하고
2. 마지막 문자열까지 확인했을 때(i==count-1)만 result에 추가하고 있죠

근데... 첫번째 문자열이 이미 기준이라면, 굳이 마지막 문자열의 문자를 result에 더할 필요가 있을까요? 아니면 다른 방식으로 접근할 수 있지 않을까요?

 

질문3

배열이 1일때 예외가 발생한다 이것도 따로 if문으로 추가해줘야 하는게 맞을까?

답변3

배열 크기가 1이면 첫번째 문자열 전체가 return
불일치가 발견되면 해당 위치까지의 부분 문자열이 return
모든 문자열이 같다면 전체 문자열이 return

추가 if문 없이도 모든 케이스를 커버할 수 있겠죠?

 

초기 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public String longestCommonPrefix(String[] strs) {

        String result = "";
        
        if (strs == null || strs.length == 0) {
            return result;
        }

        int j = strs[0].length()-1;
        int count = strs.length;
        int check = 0;

        for(int k=0; k<=j; k++){
            String standard = String.valueOf(strs[0].charAt(k));
            int i=0;

            if(check==-1) {
                break;
            }

            while(i<count) {
                if(k>strs[i].length()-1){
                    break;
                }
                char strs_ch = strs[i].charAt(k);
                String comparison = String.valueOf(strs_ch);
                if(!standard.equals(comparison)){
                    check = -1;
                    break;
                }
                if(i==count-1) {
                    result += String.valueOf(strs[i].charAt(k));
                    System.out.println(result);
                }
                i++;
            }
        }

        return result;
    }
}

 

개선 코드

import java.util.*;
import java.lang.*;
import java.io.*;

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

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