[백준 13774] Palindromes (C#, C++) - soo:bak

문제 링크

13774번 - Palindromes

설명

소문자 문자열에서 정확히 한 글자를 삭제해 팰린드롬을 만들 수 있는지 확인합니다.

가능하면 가장 앞쪽 글자를 삭제해 얻는 팰린드롬을 출력하고, 불가능하면 “not possible”을 출력합니다.

입력은 여러 줄로 주어지며, #가 나오면 종료합니다.

접근법

삭제 위치를 앞에서부터 순서대로 시도합니다. 해당 위치를 제거한 문자열이 팰린드롬이면 출력하고 종료합니다.

끝까지 찾지 못하면 불가능을 출력합니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static bool IsPal(string s) {
    var l = 0;
    var r = s.Length - 1;
    while (l < r) {
      if (s[l] != s[r]) return false;
      l++; r--;
    }
    return true;
  }

  static void Main() {
    var sb = new StringBuilder();
    string? line;
    while ((line = Console.ReadLine()) != null) {
      if (line == "#") break;

      var found = false;
      for (var i = 0; i < line.Length; i++) {
        var candidate = line.Remove(i, 1);
        if (IsPal(candidate)) {
          sb.AppendLine(candidate);
          found = true;
          break;
        }
      }
      if (!found) sb.AppendLine("not possible");
    }
    Console.Write(sb);
  }
}

C++

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

bool isPal(const string& s) {
  int l = 0, r = (int)s.size() - 1;
  while (l < r) {
    if (s[l] != s[r]) return false;
    l++; r--;
  }
  return true;
}

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

  string s;
  while (cin >> s) {
    if (s == "#") break;

    bool found = false;
    for (int i = 0; i < (int)s.size(); i++) {
      string t = s.substr(0, i) + s.substr(i + 1);
      if (isPal(t)) {
        cout << t << "\n";
        found = true;
        break;
      }
    }
    if (!found) cout << "not possible\n";
  }

  return 0;
}