[백준] 2179번 비슷한 단어 자바

문제 (구현)

 

https://www.acmicpc.net/problem/2179

 

 

문제 풀이

 

처음에는 문제 내용에 있는 '부분 문자열'이 LCS를 말하는 줄 알고 부분 문자열 구하는 함수를 작성하면서 메모리 초과, 시간 초과를 다 맞이했는데 구글링해서보니까 그냥 앞에서 동일한  개수만 카운팅해주면 되는 듯 하다.

카운팅 함수만 그렇게 바꿔줬더니 바로 성공 떴다.

 

✅ 알고리즘

1. 출력할 단어 두 개를 변수로 선언해두고, 순서대로 단어를 비교해나간다.

2. 부분문자열 개수가 기존 가지고 있던 개수보다 클 때만 출력 단어 변수를 업데이트 한다.

 

⁉️ 만약 모든 단어들이 겹치는 것이 없다면, 맨 앞에 입력된 두 개의 단어를 출력해야 할 것 같아서 마지막에 max == 0 이면 맨앞 단어를 출력했는데 해당 분기문이 없어도 성공이 뜬다.

이 문제.. 테스트 케이스가 부족한 것 같다...

 

 

소스 코드

 

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int max = 0;
		String str1 = "", str2 = "";
		String[] keywords = new String[N];
		
		for(int i = 0; i < N; i++)
			keywords[i] = sc.next();
		
		for(int i = 0; i < N; i++) {
			for(int j = i + 1; j < N; j++) {
				int countKeyword = countWord(keywords[i], keywords[j]);
				if(countKeyword > max) {
					max = countKeyword;
					str1 = keywords[i];
					str2 = keywords[j];
				}
			}
		}
		if(max == 0) {
			System.out.println(keywords[0]);
			System.out.println(keywords[1]);
		}else {
			System.out.println(str1);
			System.out.println(str2);
		}
		sc.close();
	}
	
	//부분 문자열 구하는 함수
	public static int countWord(String s1, String s2) {
		int count = 0;
		
		for(int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
			if(s1.charAt(i) == s2.charAt(i))
				count++;
			else
				break;
		}
		
		return count;
	}
}