99클럽 코테 스터디 16일차 TIL [완전 탐색]

- 오늘의 학습 키워드 : 완전 탐색

[문제 이름 : 비슷한 단어 (백준 2179, G4)]
문제 url : https://www.acmicpc.net/problem/2179

내가 작성한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String[] words = new String[num];

        for(int i=0; i<num; i++) {
            words[i] = br.readLine();
        }

        int maxLen = 0;
        int s = -1;
        int e = -1;

        // 모든 쌍을 비교하여 가장 긴 공통 접두사를 찾음
        for (int i = 0; i < num - 1; i++) {
            for (int j = i + 1; j < num; j++) {
                int curLen = getLen(words[i], words[j]);
                if (curLen > maxLen) {
                    maxLen = curLen;
                    s = i;
                    e = j;
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        sb.append(words[s]).append("\n").append(words[e]);
        System.out.println(sb.toString());
    }

    // 공통 접두사 길이 계산
    static int getLen(String a, String b) {
        int len = 0;
        int minLen = Math.min(a.length(), b.length());

        for(int i=0; i<minLen; i++) {
            if(a.charAt(i) == b.charAt(i)) {
                len++;
            } else {
                break;
            }
        }

        return len;
    }
}

풀이 과정 (풀이 시간 : 40분)

처음에 문제를 이해 못해서, 시간이 오래 걸렸다. 접두열이 다른 경우에는 문자열이 ""로 된다고 했는데, 이에 대한 반례 케이스가 존재하지 않았다. 이 부분을 고려해서 시간이 오래 걸렸는데, 고려 안하고 푸니까 문제가 풀려서 당황했다 ..

1. 문자열 배열로 입력값을 저장하고, 이중 for문으로 완전탐색을 돌린다.

2. 접두사가 일치하는지를 확인하고, 이 값(curLen)이 maxLen(최대 접두사 길이)보다 크다면 maxLen, s(startIndex), e(endIndex)값을 갱신해준다. 이렇게 하면 입력되는 순서대로 값을 가져올 수 있다.

 

내일은 SSAFY 시험을 위해 코딩 SWEA에서 D2~D4 문제를 풀어볼 예정이다.