[백준 27466] 그래서 대회 이름 뭐로 하죠 (C#, C++) - soo:bak

문제 링크

27466번 - 그래서 대회 이름 뭐로 하죠

설명

길이 n인 문자열에서 일부 문자를 지워 길이 m인 부분 수열을 만들 때, 끝 세 글자가 A, A, 자음 순서가 되도록 하는 문제입니다.

가능한 부분 수열이 존재하면 아무거나 하나를 출력합니다.

접근법

부분 수열의 끝 세 글자가 A, A, 자음이어야 하므로, 앞쪽 m - 3 글자는 원본 문자열의 처음 m - 3 글자를 그대로 사용할 수 있습니다.

따라서 m - 3 번째 위치 이후에서 A, A, 자음 순서로 나타나는 세 문자를 찾으면 됩니다.

먼저 각 위치에서 다음 A의 위치와 다음 자음의 위치를 역방향으로 전처리합니다.

이후 m - 3 번째 위치부터 순회하며 A를 찾고, 그 뒤에 A가 있는지, 다시 그 뒤에 자음이 있는지 확인합니다.

세 조건을 모두 만족하는 위치를 찾으면 앞쪽 m - 3 글자와 찾은 세 글자를 이어 붙여 출력합니다.

시간 복잡도는 O(n)입니다.

---

Code

C#

using System;

class Program {
  static bool IsVowel(char c) => c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';

  static void Main() {
    var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
    var n = line[0];
    var m = line[1];
    var s = Console.ReadLine()!;

    var nextA = new int[n + 2];
    var nextC = new int[n + 2];
    nextA[n] = nextC[n] = -1;
    for (var i = n - 1; i >= 0; i--) {
      nextA[i] = (s[i] == 'A') ? i : nextA[i + 1];
      nextC[i] = (!IsVowel(s[i])) ? i : nextC[i + 1];
    }

    int a1 = -1, a2 = -1, cPos = -1;
    for (var i = m - 3; i <= n - 3; i++) {
      if (s[i] != 'A') continue;
      var na = nextA[i + 1];
      if (na == -1) continue;
      var nc = nextC[na + 1];
      if (nc == -1) continue;
      a1 = i; a2 = na; cPos = nc;
      break;
    }

    if (a1 == -1) {
      Console.WriteLine("NO");
      return;
    }

    Console.WriteLine("YES");
    var res = new char[m];
    for (var i = 0; i < m - 3; i++) res[i] = s[i];
    res[m - 3] = s[a1];
    res[m - 2] = s[a2];
    res[m - 1] = s[cPos];
    Console.WriteLine(new string(res));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

bool isVowel(char c) {
  return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  string s; cin >> s;

  vi nextA(n + 2, -1), nextC(n + 2, -1);
  for (int i = n - 1; i >= 0; --i) {
    nextA[i] = (s[i] == 'A') ? i : nextA[i + 1];
    nextC[i] = (!isVowel(s[i])) ? i : nextC[i + 1];
  }

  int a1 = -1, a2 = -1, cPos = -1;
  for (int i = m - 3; i <= n - 3; ++i) {
    if (s[i] != 'A') continue;
    int na = nextA[i + 1];
    if (na == -1) continue;
    int nc = nextC[na + 1];
    if (nc == -1) continue;
    a1 = i; a2 = na; cPos = nc;
    break;
  }

  if (a1 == -1) {
    cout << "NO\n";
    return 0;
  }

  cout << "YES\n";
  string res;
  res.reserve(m);
  for (int i = 0; i < m - 3; ++i) res.push_back(s[i]);
  res.push_back(s[a1]);
  res.push_back(s[a2]);
  res.push_back(s[cPos]);
  cout << res << "\n";

  return 0;
}