BOJ 5013 - Death Knight Hero

문제

BOJ 5013 - Death Knight Hero

데스 나이트(Death Knight) 영웅은 특정 능력(ability)이 주어졌을 때 그 능력을 사용할 수 있다. 이 문제에서는 N개의 영웅 세트가 주어지고, 각 영웅이 가진 능력 문자열에 CD가 포함되어 있지 않은 경우 그 영웅이 승리(win)로 간주된다.

N명의 영웅 중에서 CD 연속 부분 문자열이 없는 영웅의 수를 출력한다.

입력

• 첫째 줄에 테스트 케이스 수 N이 주어진다.
• 이후 N개의 줄에 각각 능력을 나타내는 대문자 알파벳 문자열이 주어진다.

출력

CD 부분 문자열이 없는 영웅의 수를 출력한다.

예제

풀이

각 능력 문자열을 순회하며 CD 연속 패턴이 존재하는지 확인한다. 존재하지 않으면 승리 카운트를 증가시킨다.

1. N개의 능력 문자열을 입력받는다.
2. 각 문자열에서 인접한 두 문자 쌍 (abilities[j], abilities[j+1])을 확인한다.
3. C와 D가 연속으로 등장하면 hasCD = true로 표시하고 순회를 중단한다.
4. hasCD가 false인 경우 cntWins를 증가시킨다.
5. 최종 cntWins를 출력한다.

핵심 아이디어: 문자열에서 연속 패턴을 탐색할 때는 인덱스 j와 j+1을 동시에 검사하는 방식으로 O(L) 시간에 처리할 수 있다. (L은 문자열 길이)

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n;
  cin >> n;
 
  int cntWins = 0;
  for (int i = 0; i < n; i++)
  {
    string abilities;
    cin >> abilities;
 
    bool hasCD = false;
    for (size_t j = 0; j < abilities.size(); j++)
    {
      if (abilities[j] == 'C' && abilities[j + 1] == 'D')
      {
        hasCD = true;
        break;
      }
    }
 
    if (!hasCD)
      cntWins++;
  }
 
  cout << cntWins << "\n";
 
  return 0;
}

복잡도

• 시간: O(N * L) — N개의 문자열, 각 문자열 길이 L만큼 순회
• 공간: O(L) — 단일 문자열 저장