16172번 나는 친구가 적다 (Large)

이왜틀?

---

16172번 나는 친구가 적다 (Large) - 백준

요것도 5년전 시간초과다.
대체로 경향이 단순 시뮬레이션으로 소스 넣어보고 시간초과뜨면 도망갔던 것으로 보인다.

String a=br.readLine().replaceAll("[0-9]","");
String b=br.readLine();
bw.write(a.contains(b)?"1":"0");

입력받은 S의 숫자를 replaceAll로 제거하고 contain을 사용했다.
Small 문제는 이걸로 통과했나본데 Large의 경우 S와 K가 20만개까지 있을 수 있어 택도 없다.

설계

---

문제 자체가 한글로 되어있고 쉬워보여서 코드 제출이 많은 경우
통과해선 안되는 코드를 저격하기위해 수많은 반례가 존재한다.

이 문제도 그런 류에 속한다.
처음에 특별한 알고리즘을 쓸 일 있나 싶어서 포인터를 2개 두고 S와 K를 시간복잡도 O(N) 으로 탐색하려했는데
자꾸 무슨 반례에 걸렸는지 틀렸습니다를 뿜어내기 시작…

화가났지만 KMP 알고리즘을 써서 통과했다.

구현

---

// KMP 배열
int[] kmp = new int[K.length()];

int idx = 0; 

for (int i = 1 ; i < kmp.length ; i++) {
	
	if (K.charAt(i) == K.charAt(idx)) {
		kmp[i] = ++idx; 
	} else if (idx != 0) {
		// aabc abc 같은 패턴
		idx = kmp[idx -1]; 
		i--;
	}else {
		kmp[i] = 0;
	}
}

boolean result = false;

int j = 0;
for (int i = 0 ; i < S.length() ; i++) {
	if (Character.isLetter(S.charAt(i))) {
		
		while(j > 0 && S.charAt(i) != K.charAt(j)) {
			j = kmp[j - 1];
		}
		
		if (S.charAt(i) == K.charAt(j)) {
			j++;
			if (j == K.length()) {
				result = true;
			}
		}
	}
}

채점

---

반성

---

진짜 무슨 예제가 자꾸 틀렸던 걸까?
이것저것 만들어서 넣어봤는데 알 수가 없다.
브론즈 문제 무서워…

코드 확인

---

Link to GitHub