[백준 9377] String LD (C#, C++) - soo:bak

문제 링크

9377번 - String LD

설명

여러 문자열에 동시에 Stringld 연산을 적용할 때, 빈 문자열이나 중복 문자열이 생기기 전까지 몇 번 적용할 수 있는지 구하는 문제입니다.

접근법

문자열 길이가 최대 100이므로, 실제로 한 단계씩 시뮬레이션해도 충분합니다.

한 번의 단계마다 모든 문자열의 맨 앞 글자를 하나 제거합니다. 그 결과를 보면서 빈 문자열이 생기면 바로 중단하고, 집합에 넣어 보면서 이미 나온 문자열이 다시 나오면 그 단계도 실패입니다.

실패가 발생한 마지막 단계는 세지 않으므로, 조건을 만족한 단계 수만 따로 세다가 문제가 생기면 그 값을 그대로 출력하면 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    while (true) {
      int n = int.Parse(Console.ReadLine()!);
      if (n == 0)
        break;

      string[] words = new string[n];
      for (int i = 0; i < n; i++) {
        words[i] = Console.ReadLine()!;
      }

      int answer = 0;

      while (true) {
        bool ok = true;
        var seen = new HashSet<string>();

        for (int i = 0; i < n; i++) {
          words[i] = words[i].Substring(1);

          if (words[i].Length == 0 || !seen.Add(words[i])) {
            ok = false;
          }
        }

        if (!ok)
          break;

        answer++;
      }

      Console.WriteLine(answer);
    }
  }
}

C++

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

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

  while (true) {
    int n;
    cin >> n;

    if (n == 0)
      break;

    vector<string> words(n);
    for (int i = 0; i < n; i++) {
      cin >> words[i];
    }

    int answer = 0;

    while (true) {
      bool ok = true;
      unordered_set<string> seen;

      for (int i = 0; i < n; i++) {
        words[i] = words[i].substr(1);

        if (words[i].empty() || !seen.insert(words[i]).second) {
          ok = false;
        }
      }

      if (!ok)
        break;

      answer++;
    }

    cout << answer << "\n";
  }

  return 0;
}