[Codeforces] Round 855 Div.3 후기

대회링크 : https://codeforces.com/contest/1800

 

A. Is It a Cat?

문제 : 주어진 문자열에서 m, e, o, w 가 순차적으로 나오는지 판별

 

간단하게 meow가 순차적으로 나왔는지 판단하고

해당차례에 해당 문자 혹은 해당 이전의 문자가 아닌 다른문자가 나올 경우 불가능으로 판단

 

 

B. Count the Number of Pairs

문제 : 대, 소문자의 같은 알파벳끼리 최대로 이루는 짝의 개수 출력

대문자에서 소문자, 소문자에서 대문자로 최대 K번 바꿀 수 있음

 

각 알파벳 별로 대문자와 소문자를 나누고

이때 짝을 이루는 개수는 각 알파벳별로 min(대문자, 소문자) 이고

대소문자를 치환하여 짝을 만들수 있는 경우는 abs(대문자 - 소문자)/2 가 되며

K번 초과 해서 짝을 만들 수 있는 경우엔 최대 K개의 짝을 만들 수 있다.

 

 

C. Powering the Hero

문제 : 카드를 순차적으로 뽑아 얻을 수 있는 최대 파워 출력

0번 카드(히어로)를 뽑은 경우 더미 가장 위의 에너지카드 만큼 파워를 얻는다.

그외의 카드(보너스)인 경우 더미 위에 카드를 올리거나 버릴 수 있다.

 

우선순위큐를 사용하여 보너스 카드인 경우에는 항상 넣어주며

히어로 카드인 경우에는 우선순위큐가 비어있지 않다면 하나를 꺼내 파워를 얻는다.

 

D. Remove Two Letters

문제 : 주어진 문자열에서 연속된 2글자를 제거했을 때 나올 수 있는 문자열의 개수 출력

 

해당 문제에서 substr을 이용해 단순하게 구현 했을 때 메모리초과를 당하였다.

 

길이가 N인 문자열에서 문자열을 2개 제거 했을 경우 만들 수 있는 경우는 총 N-1가지 이며

문자열을 처음부터 비교했을때 2칸 뒤의 문자열이 현재 문자열과 같은 경우에 중복되므로 1가지씩 줄인다.

ex) @aba# -> @(ab)a# = @a#, @a(ba)# = @a# 로 중복되게 된다. 

 

E. Unforgivable Curse

문제 : 주어진 문자열을 이동시켜 원하는 문자열로 변환 할 수 있는지 판별

해당 위치의 문자열은 K칸 앞, 뒤 혹은 (K+1)칸 앞, 뒤 문자와 교환 할 수 있으며 횟수 제한은 없다.

 

해당 위치에서 BFS탐색을 통해 연결 된 곳은 모두 서로 하나의 집합에 속하게 된다.

따라서 BFS를 통해 집합을 나누고 각 집합의 알파벳 개수가 동일하다면 A문자열에서 B문자열로 치환이 가능하다.

 

 

F, G - 아직 실력이 부족해 풀지 못하였다.