[CNU SW 아카데미 / 파트 3.실전문제] Umm 문자열 2

앞으로 코딩테스트 풀 때, 기억해놔야 하는 것들을 적어둬야겠다. 

---

문제

Umm 문자열이란 알파벳 대문자 U 뒤에 알파벳 소문자 m 이 2개 이상 연속하는 문자열이다. 

예시는 아래와 같다. 

Umm
Ummm
Ummmm

아래의 문자열은 Umm 문자열이 아니다.

U
Um
mm
UmmmU
UmmUmm

문자열이 주어지고, 문자열 슬라이스 범위가 주어졌을 때(a 부터 b까지) 해당 문자열이 Umm 문자인지 아닌지 출력하자. 

 

입력

(1) 테스트 케이스 개수 T

(2) 문자열 길이 S의 길이 N(1<= N <= 200 000) 관찰 횟수 M(1<= M <= 200 000),

(3) 입력 문자열 S (U, m으로만 이루어짐)

(4) M 개의 인덱스 A, B (1 <= A <= B <= N)

2
10 5
UmmUmmmUmm
1 3
1 4
8 10
3 4
4 7
7 3
mmUmmmU
3 5
1 3
3 6

출력

관찰횟수 중에서 Umm 인 경우의 수를 모두 합해 출력한다. 

3
2

---

해결방법 / 코드

처음에는 정규표현식을 사용해서 Umm 문자인지 판단하려고 했다. 

하지만 역시나 효율성 테스트에서 시간 초과가 났다. 

 

Umm  문자열의 특징을 다시 곱씹어봤다. 

1. U 로 시작한다. 

2. U 다음 mm 이 붙는다. 

3. 1, 2의 조건이 충족되었다면 계속 m이 붙을 수 있다. 

 

위의 조건을 약간 누적합(?) 같이 만들어서 DP로 풀어볼 수 있을 것 같았다. 

 

입력 문자열의 길이와 똑같은 배열을 만들어서, 

1. U로 시작하면 1

2. U 다음 m 이면 +1

3. m 다음 m 이면 +1 (2의 조건을 만족해야 함)

의 규칙으로 채워넣는다. 

 

m	m	U	m	m	m	U
0	0	1	2	3	4	1

위는 입력 문자열이 mmUmmU일 경우의 DP 배열이다. 

관찰 횟수에 따라 a, b가 입력될 때,

DP 배열의 인덱스를 비교해서 Umm 조건이라면 b - a의 수와 DP[b] - DP[a] 가 같을 것이다. 

(Umm 이 만족되는 길이를 구하는 거라고 생각하면 쉽다.)

 

아래 git은 내가 짠 코드다. 

https://github.com/nub8p/CNU_SW_Academy/blob/main/Coding_Test/Umm%EB%AC%B8%EC%9E%90%EC%97%B42.py

GitHub - nub8p/CNU_SW_Academy