삼성 8934. 팰린드롬 공포증

8934. 팰린드롬 공포증

링크

난이도 : d4
정답률 : _42%

설계

어떤 경우에라도 팰린드롬이 나타나는 경우

• aba
• aaba
• aabca
• aabaa
• aabbca

절대 팰린드롬을 만들지 않기 위해 abc순으로 계쏙 나열한다고 하자.

(가장 많이 나온 알파벳을 a, 그 다음 많이 나온 알파벳을 b라고 할 때)

abc로 만들고 남은 알파벳의 수는

a의 남은 개수 : count(a)-count(c)

무조건 팰린드롬이 나오는 경우는

count(a_left) > 1 인 경우이다.

a가 2개 이상인 경우 b의 개수가 아무리 많아도,
양 끝에 a를 넣으면 팰린드롬이 되기 때문이다.

정리

내 코드 : 32 ms;
빠른 코드 : 25 ms; Mon Dec 02 2019 23:05:35 GMT+0900 (한국 표준시) 기준

문제의 설명이 너무 적어 규칙을 찾기 어려웠던 문제.

풀이법

1. 펠린드롬이 무조건 나오는 경우를 만들어 본다.
2. a, b, c의 갯수들을 count한 수를 비교해가며 정답의 갯수를 늘려간다.
3. 펠린드롬이 무조건 나오지 않는 경우를 남은 a,b,c의 수를 카운트한다.

3번에서 abc순으로 계속 나열할 때,
남은 인자들로 팰린드롬을 만들지 못하면 YES인 것을 확인.

고생한 점

문제의 설명이 너무 적었다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalin(string word) {
  int length = word.length();

  string first = word.substr(0, length / 2);
  string second = word.substr((length + 1) / 2, length);

  reverse(second.begin(), second.end());

  for (int index = 0; index < length / 2; index++) {
    if (first[index] == '?' || second[index] == '?') {
      continue;
    }
    if (first[index] != second[index]) {
      return false;
      break;
    }
  }
  return true;
}

void solution(int test_case) {
  string answer = "YES";
  string str;
  vector<int> count;
  count.resize(3, 0);

  cin >> str;

  for (char c : str) {
    count[c - 'a']++;
  }

  sort(count.begin(), count.end());

  count[2] -= count[0];

  if (count[2] > 1) {
    answer = "NO";
  }

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

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}