[AtCoder] ABC295 A~D 업솔빙

---

안녕하세요 Gliver 입니다.

이번 글은 앳코더 ABC295에 대해 업솔빙하는 글입니다.

 

이번 대회는 약 60분 정도부터 시작하였다.

 

A번

  - 단순 구현 문제이다.

B번

  - 단순 구현 문제로 $O(R^2 \cdot C^2)$으로 해결할 수 있다.

  - 조금 더 효율적으로 구현하면 $O(R \cdot C \cdot 9^2)$으로 해결할 수 있다.

C번

  - 약간의 사고력을 요구하는 문제이다.

  - sort(정렬)을 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다.

  - map 자료구조를 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다.

D번

  - 대회가 끝나고 본 문제이며, prefix xor을 이용하면 $O(N)$으로 해결할 수 있다.

 

 

 

A. Probably English

$N$개의 문자열($W_1, W_2, \cdots, W_N)$이 주어지고 특정 문자열이 포함되었는지를 판별하는 문제이다.

배열을 순회하면 특정 문자열 and, not, that, the, you 이 들어있는지를 판단하면 된다.

 

 

$1 \leq N \leq 100$, $1 \leq |W_i| \leq 50$ 이므로 최악의 경우에도 $O(N \cdot 50)$에 해결할 수 있다.

 

 

 

B. Bombs

$R \times C$ 행렬에 대해 폭탄이 터진 후의 모습을 출력하는 문제이다.

행렬을 순회하며 폭탄을 만날 때마다 .이 되는 장소들을 기록해 두면 쉽게 해결할 수 있다.

 

 

폭탄을 만날 때마다 행렬 전체를 탐색하면 $O(R^2 \cdot C^2)$으로 해결할 수 있으며,

조금 더 효율적으로 폭탄의 범위만 탐색하면 $O(R \cdot C \cdot 9^2)$으로 해결할 수 있다.

 

 

 

C. Socks

$N$개의 양말이 주어질 때, 같은 색의 쌍의 최대값을 구하는 문제이다.

같은 색의 양말을 묶을 수 있을 때마다 묶으면 해결할 수 있다.

이를 효율적으로 구현하기 위해서는 sort(정렬)을 이용하거나, map 자료구조를 이용하면 된다.

 

 

 

 

 

 

D. Three Days Ago

이 문제는 이전 문제들에 비해서 난이도가 있었던 문제였다.

(well-known 형식의 풀이가 쓰이지만, 이를 감안해도 난이도가 꽤 있었던 거 같다.)

 

문자열 $S$가 주어지며 문자열의 길이는 $1 \leq |S| \leq 5 \cdot 10^5$이다. (편의상 $|S|$를 $N$으로 표기하겠다)

문제에서 요구하는 것은 happy한 substring(부분 문자열)의 개수를 구하는 것이다.

 

happy한 substring의 조건

먼저, 어떠한 substring이 happy한지를 정확히 알아야 한다.

문제의 설명에서는 순서를 바꿔서 어떤 문자열이 2번 반복되면 happy하다고 하였다.

이를 조금만 생각해 보면 각 문자의 개수가 짝수개이면 happy하다는 것을 알 수 있다.

 

기초적인 방법

가장 기초적인 풀이는 모든 부분 문자열을 탐색하며 조건을 만족하는지를 확인하는 것이다.

substring의 경우의 수는 $_{N}\mathrm{C}_{2}$이고, substring이 happy한지를 알아볼 때 $|substring|$의 연산이 걸린다.

따라서, 약 $O(N^3)$의 시간 복잡도가 걸리는 것이다.

조금 더 효율적으로

여기서, 어떤 substring이 happy한지를 prefix sum 기법을 이용하면 $O(1)$로 줄일 수 있다.

하지만, 이렇게 줄인다 해도 시간 복잡도는 $O(N^2)$으로 TLE(Time Limit Exceeded) 오류가 나게 된다.

정답 풀이

위의 과정에서 알 수 있었던 점은 substring의 개수를 일일이 확인하는 과정 자체가 $O(N^2)$라는 점이다.

즉, 일일이 substring을 확인하는 과정 자체가 이미 TLE 오류가 난다는 것이다.

 

따라서, 우리는 happy한 substring을 한 번의 연산으로 여러 개 구해야 한다!

 

substring $A$와 substring $B$가 happy하며 이 둘이 이어져 있다면, 이 둘을 합친 문자열도 happy하다!

이어지는 happy한 substring $k$개를 구한다면 위의 성질을 이용하여 $\frac{(k) \cdot (k+1)}{2}$개의 happy한 substring이 있음을 알 수 있다.

 

그렇다면, 이어져 있는 happy한 substring을 어떻게 찾을 수 있을까?

이는, 각 위치에서의 상태를 저장하는 prefix xor 기법을 이용하여 효율적으로 구할 수 있다.

pxor[i]는 0에서 i번째 원소까지 살펴봤을 때 0~9 숫자의 개수가 짝수개인지 홀수개인지 상태를 나타낸다.

여기서 핵심은 pxor[a]와 pxor[b]가 같다면 p[a+1:b]가 happy하다는 것이다. (단, a < b)

즉, pxor[x]가 $k$개 있다면 $k-1$개의 이어지는 happy한 substring이 있는 것이므로 $\frac{(k-1) \cdot (k)}{2}$개의 happy한 substring이 있다는 것이다.

 

 

pxor 배열의 값 별로 개수만 카운팅하면 되기 때문에 $O(N)$으로 해결 가능하다.

(이 문제에서 map 크기의 상한은 $2^{10}$으로 $N$의 상한에 비해서 작으므로, 시간 복잡도 표기상 제거하였다)

(참고로, map을 전체 순회하는 데 걸리는 시간은 $O($map의 크기$)$이다) (참조 링크)

 

 

 

느낀점

저번 LeetCode Weekly Contest 336의 C번 문제(링크)에서 prefix xor 기법을 배웠었다.

비록 대회 시간 안에는 못 풀었지만, 이번 대회의 D번 문제에 prefix xor 기법을 바로 적용할 수 있었다는 점이 좋았다.