Intro


쉬웠죠?

Qual 못하신 분들은 진출하기 훨씬 쉬운 1B 1C 남아있으니 그때를 노립시다

오늘 고인물들 다 빠져나가서 괜찮을 거에요

난이도 순서는 A-B-C이고, 항상 있던 인터랙티브는 없었습니다 :(

인터랙티브 빠지고 나온 문제가 C같은 핵노잼 문제라니 많이 아쉽네요

질문은 댓글로 하시면 빠르게 받아드립니다. 코드도 요청하면 보내드림


A: Pattern Matching


각 단어에는 *이 반드시 하나 있습니다. *은 존나 쩌는 만능 문자니까 최대한 우려먹을 생각을 해 봅시다.

*을 최대한 우린다고 생각할 때 아무리 우려도 결국 일치해야 되는 부분은, *이 등장할 때 까지의 prefix와 *이 등장할 때 까지의 suffix입니다.

예를들어 convex*hull*trick이 있으면 convex랑 trick은 얄짤없이 다른 단어의 prefix/suffix와 일치하거나, 포함 관계여야 한다는 거죠.

만약에 이게 아다리가 안 맞으면, 어떤 방식을 써도 맞추는 건 불가능 하니 * 찍고 퇴갤하면 됩니다.

반대로 이게 모두 다 맞아서 하나의 prefix/suffix로 모든 패턴을 매칭시킬 수 있으면, * 사이에 있는 문자들을 판단하는 건 매우 쉽습니다.

예를 들어 iha*vea*pen과 ihav*eaa*pplep*en이 있으면, prefix ihav와 suffix pen을 좌우에 걸쳐놓고 ihav - veaeaapplep - pen과 같이 가운데는 와일드카드를 빼고 모두다 뭉쳐서 출력해주면 됩니다. 길이 제한이 널럴하기 때문에 이렇게 해도 무방합니다. 


시간복잡도는 O(SN)이어요



B: Pascal Walk


고등학교 확통시간에 배우지만, 파스칼 삼각형의 가로줄을 쭉 이으면 2의 거듭제곱이 됩니다.

모든 수는 2의 거듭제곱의 합으로 표현이 가능하니, 가로줄을 이진수 표현과 비슷하게 선택하면 끝나겠군요.

문제는 하나인데, 연속된 경로를 지나야 하기 때문에 모든 줄의 맨 왼쪽이나 오른쪽 중 하나는 반드시 지나야 한다는 점입니다. 이러면 숫자가 예상보다 커지죠.

해결법은 의외로 간단한데, n이 있으면 n-32정도를 임시 n으로 설정해 둔 후 경로를 지나게 하면 됩니다. 그러면 실제보다 조금 작은 이진수 경로 + 연속된 경로 제한때문에 어쩔 수 없이 선택하는 1들을 합한 값이 n보다 조금 작은 수로 나오겠고(경로의 높이가 32를 안 넘을테니), 그 뒤는 끄트머리를 따라가면서 1로 마저 채워주면 됩니다.


시간복잡도는 O(lg N ^ 2) 정도이어요


C: Square Dance


개씹노잼 삼성A형 문제였습니다.

가장 먼저 해야 하는 관찰은 각 원소는 최대 한 번 지워진다는 거고, 두 번째로 해야 하는 관찰은 원소가 지워질 때 연속해서 지워질 수 있는 원소는 최대 4개라는 거죠.

그래서 시뮬레이션을 그대로 돌리면 됩니다. 구체적으로는 다음과 같습니다.


0. 집합 S에 모든 칸을 삽입

1. S에 있는 모든 원소들에 대해 지워지는 지 확인하고 S를 비움

2. 모든 칸이 지워졌을 때, 각 지워지는 칸에서 가장 사방으로 가까운 원소(최대 4개)를 S에 삽입

3. 실제로 원소를 지움


이게 왜 되냐면, S에 원소가 들어갈 때는 맨 처음과 원소가 삭제될 때 밖에 없기 때문에 각 원소는 S에 최대 5번만 들어갑니다.

사방으로 가장 가까운 원소 찾는 건 리스트로 O(1)에 해도 되고, set으로 O(lg N)에 해도 됩니다.


시간복잡도는 O(NM) 또는 O(NM(lgN+lgM))이어요



댓글로 궁금한점 질문하세요