[BOJ] 2866번: 문자열 잘라내기

copyrat90·2022년 3월 12일

문제 설명

문제 설명 그대로 우직하게 위에서부터 substr을 매 행마다 하나씩 만들면, $O(R^2C)$ 로 시간 초과다.
substr 을 만드는 데만 $O(RC)$ 걸리는데, 그걸 $R$ 행만큼 반복을 하니...

가만 생각해보니, 거꾸로 접근하는 게 좋을 것 같았다.
"아래에서 위로 쌓아가며" 문자열을 만들면, 기존 문자열에 append 해서 전체를 $O(RC)$ 만에 생성할 수 있다.

예를 들어서, 문자열이 아래처럼 주어졌다고 하자.

l m n o p q
g g g g g g
u k k k u k
x x y y z z
a a a b b b

1행과 2행을 지워도, 문자열은 아래와 같이 서로 구분이 된다.

u k k k u k
x x y y z z
a a a b b b

하지만 3행을 지우는 순간, xa xa 와 zb zb 가 중복되므로, 최대 $2$ 개 행까지만 지울 수 있다.
고로 이 예제의 답으로 2가 출력되어야 한다.

x x y y z z
a a a b b b
중복 발생! 이전 행까지 포함해야 함!

3행을 다시 포함시켜놓고 보면, 5~4행의 중복을 3행이 막아주는 것을 볼 수 있다.
제일 아랫행부터 윗행으로 훑어봤을 때, 3행까지 왔을 때야 중복이 모두 분리된다는 의미.

u k k k u k
x x y y z z
a a a b b b

아래에서 위로 행을 쌓으면서, 모두 분리된 순간이 몇 번째 행인지를 알아내는 게 관건이다.
이 아이디어까지는 1시간 안에 떠올렸지만,
substr 을 매번 Hash 에 넣었다가 $O(R^2C)$ 로 틀렸던 기억 때문에, 답을 보고 말았다.

그런데 이렇게 행을 쌓으면서 접근하면, substr 을 매번 Hash 에 넣어도 가능한게,
이전 행까지의 substr 에 이번 행의 글자 1개를 append 하면, 전체를 $O(RC)$ 만에 다 볼 수가 있기 때문이다.

틀렸던 풀이는, 위에서부터 보는 바람에 매번 substr 을 처음부터 다시 생성해서 $O(R^2C)$ 로 느렸을 뿐.

결론
아랫행에서 윗행으로 한 행씩 보면서,
이전 행까지의 문자열에다가 이번 글자를 append 하고,
Hash 로 중복이 존재하는지 검사하자.

gamedev stuff