📒문제

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하세요.
공통 접두사가 없으면 빈 문자열을 반환합니다. ""

예시

input: strs = ["flower", "flow", "flight"]
output : "fl"

제약

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 영문 소문자로만 구성됩니다.

😆풀이

문제를 풀면서 가장 먼저 떠오른건 StringBuilder를 사용해 조건에 맞는 문자들만 append하려고 했으나 2중 반복문에 여러 조건으로 시간초과에 걸릴거 같아 다른 방법을 생각해보았다.

문제에 대해 어떻게 하면 좋을까 하다가 다른 정답을 참고하던 중 엄청 기발한 문제 풀이 방법을 발견해서 복기하기 위해 작성한다.

먼저 배열을 오름차순으로 정렬한다.

오름차순으로 정렬하면 문자열(알파벳)의 경우 알파벳 순서로 정렬된다.

public String longestCommonPrefix(String[] strs) {
	Arrays.sort(s);		// 오름차순 정렬 -> 사전순으로 정렬
    // [flight, flow, flower]와 같이 정렬 된다.
}

정렬된 배열의 첫번째와 마지막번째 문자열을 저장한다.

public String longestCommonPrefix(String[] strs) {
	Arrays.sort(s);
    
    String first = strs[0]; // flight
    String last = strs[strs.length - 1];	// flower
}

인덱스로 사용할 변수 선언

public String longestCommonPrefix(String[] strs) {
	Arrays.sort(s);		// 오름차순 정렬 -> 사전순으로 정렬
    // [flight, flow, flower]와 같이 정렬 된다.
    
    String first = strs[0]; // flight
    String last = strs[strs.length - 1];	// flower
    
    int c = 0;	// 공통된 접두사가 어디까지인지 확인하는 용도의 인덱스
}

반복 및 조건

public String longestCommonPrefix(String[] strs) {
	Arrays.sort(s);		// 오름차순 정렬 -> 사전순으로 정렬
    // [flight, flow, flower]와 같이 정렬 된다.
    
    String first = strs[0]; // flight
    String last = strs[strs.length - 1];	// flower
    
    int c = 0;
    
    // first의 끝까지 검사
    while(c < first.length()) {
    	// 문자열을 한 글자씩 비교
    	if(first.charAt(c) == last.charAt(c)) {
        	// 비교하여 같다면 c(인덱스)를 증가 시킴
        	c++;
        } else {
        	// 검사하다가 같지 않으면 반복 종료
        	break;
        }
    }
}

반환

public String longestCommonPrefix(String[] strs) {
	Arrays.sort(s);		// 오름차순 정렬 -> 사전순으로 정렬
    // [flight, flow, flower]와 같이 정렬 된다.
    
    String first = strs[0]; // flight
    String last = strs[strs.length - 1];	// flower
    
    int c = 0;
    
    // first의 끝까지 검사
    while(c < first.length()) {
    	// 문자열을 한 글자씩 비교
    	if(first.charAt(c) == last.charAt(c)) {
        	// 비교하여 같다면 c(인덱스)를 증가 시킴
        	c++;
        } else {
        	// 검사하다가 같지 않으면 반복 종료(여기선 i와 o가 달라서 c가 2가 되면 멈춘다.)
        	break;
        }
    }
    
    // c가 0이 아니라면 공통 접두사가 있다는 말.
    // first 문자열의 0번부터 c번 인덱스까지 잘라서 반환하면 정답.
    // 공통 접두사가 없으면 c == 0일테니 비어있는 문자열 ""이 반환됨
    return c == 0 ? "" : first.substring(0, c);
}