Even Idiots Can Make Game

백준 1213 S3 팰린드롬 만들기

Date/Lastmod
Section
PS
Title
백준 1213 S3 팰린드롬 만들기
Ps-Tags
Solved
03-06/25

#1 접근

임한수와 임문빈씨는 완전히 정신나간 커플이어서 이런 말도안되는 선물을 주고받나 보다.

아무튼, 입력으로 들어오는 문자열의 최대 길이 50에 비해 시간제한 2초는 매우 넉넉하므로, 최적화를 빡빡하게 하는 문제가 아니라 정말로 팰린드롬을 어떻게 만들 것인가에 대한 지저분한 구현 문제처럼 접근하면 된다.

#1 주어진 문자열을 팰린드롬으로 만드는 법

문자열을 구성하는 문자의 갯수를 모두 세 보자.

입력은 어차피 알파벳 대문자로만 들어오므로 {'A': 2, 'B': 3} 과 같은 해시 테이블에 기록할 수 있을 것이다.

만일 모든 문자가 짝수번 등장하면, 팰린드롬을 만들 수 있다.

문자열 구성하는 모든 문자 $c_i$가 $n_i$번 등장한다면, 이 문자는 팰린드롬의 앞 쪽 절반에 $\frac{n_i}{2}$번, 뒤 쪽 절반에 $\frac{n_i}{2}$번 등장하면 되기 때문이다.

홀수 번 등장하는 문자가 단 하나 존재하면, 팰린드롬을 만들 수 있다.

팰린드롬이 문자 $c_i$를 중심으로 앞뒤로 대칭이라고 생각하자. 문자 $c_i$는 팰린드롬의 전반부, 후반부를 합해 일단 짝수 번 등장하고, 중앙에 한 번 등장하므로 $c_i$의 갯수 $n_i$는 홀수이다.

홀수 번 등장하는 문자가 하나를 초과하여 존재하면, 팰린드롬을 만들 수 없다.

#1 알고리즘

#1 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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

using namespace std;

#define IMPOSSIBLE "I'm Sorry Hansoo"

int main() {
  string name; cin >> name; // [A-Z], len <= 50

  // 사전순 출력을 원하므로 키가 정렬되어 있어야 해서 map 선택
  map<char, int> freq;

  // 빈도 초기화
  for (char c = 'A'; c <= 'Z'; ++c) freq[c] = 0;

  // 빈도 기록
  for (char const &c: name) ++freq[c];

  pair<char, int> odd_data {'\0', 0};
  bool already_found_odd = false;

  for (auto &[k, v]: freq) {
    if (v == 0) continue;

    if (v % 2 != 0) {
      if (!already_found_odd) {
        // 홀수 빈도 문자를 처음 발견한 상황
        already_found_odd = true;

        odd_data.first = k;
        odd_data.second += 1;

        --v;
      } else {
        // 이미 홀수 빈도 문자가 있었는데 또 발견한 상황
        cout << IMPOSSIBLE;
        return 0;
      }
    }
  }

  string h_palin = "", ret = "";

  // 팰린드롬의 전반부 구성
  for (auto const &[c, c_count]: freq) {
    h_palin.append(c_count / 2, c);
  }

  ret += h_palin;

  // 홀수 문자 하나가 존재한다면 붙여둠
  if (already_found_odd)
    ret += odd_data.first;
  
  // 팰린드롬의 후반부 구성
  reverse(h_palin.begin(), h_palin.end());

  ret += h_palin;

  cout << ret;
}

#1 기타

#2 문자열

#2 문자열 붙이기

C++ std::string의 append 메서드에는 질릴 정도로 많은 바리에이션이 있다.

원형을 다 적고 분석하는건 의미가 없을 것 같고 다음을 보자.

string a = "abc";

// 문자를 여러개 붙이기
cout << "he"s.append(2, 'l') << endl; // hell

// 문자열을 붙이기
cout << "str"s.append("ring") << endl; // string

// 붙일 문자열의 특정 인덱스부터 갯수만큼 짤라 붙이기
cout << "str"s.append("foo", 1, 2) << endl; // stroo

// 붙일 문자열의 시작부터 지정한 갯수만큼 짤라 붙이기
cout << "str"s.append("foobar", 3) << endl; // strfoo 

// 반복자로 가져다 붙이기
cout << "str"s.append(a.begin(), a.end()) << endl; // strabc

// 초기화 리스트로 가져다 붙이기
cout << "str"s. append({'a', 'b', 'c'}) << endl; // strabc

#2 std::map과 std::unordered_map

둘 다 연관 컨테이너이며, 키-값 쌍을 저장하고 관리하는 데에 사용된다.

키를 저장하는 방식에 있어서 약간 다른 점이 있고 이 점이 성능적인 차이로도 연결되기 때문에 해결하려는 문제에 맞는 컨테이너를 사용하는 것이 중요하다.

간단히 얘기하면 std::map은 키를 항상 정렬된 상태로 유지하며, std::unordered_map은 이름이 암시하는 것처럼 키의 정렬을 보장하지 않는다.

이 문제에서는 팰린드롬이 여러 개 만들어질 수 잇는 경우 사전순으로 앞선 것을 출력하라고 하였다. 때문에 문자의 빈도를 기록할 때 문자의 사전순을 유지하는 것이 중요했으므로 std::map을 사용했다.

std::unordered_map은 키의 정렬을 보장하지 않는 대신에 삽입, 삭제, 검색 연산의 평균적인 시간복잡도가 $O(1)$이다. 1 이는, 사실상 std::unordered_map의 내부 구현이 키의 해시 값을 인덱스로 하는 배열 접근과 유사하기 때문에 그렇다.

반면, std::map은 정렬된 상태를 유지해야 하기 때문에 삽입, 삭제, 겁색 연산의 평균적인 시간 복잡도가 $O(\log{n})$이다. 내부적으로는 레드 블랙 트리를 이용하여 구현한다.

#1 참고 문헌

  1. 해시 충돌이 발생하는 경우 $O(N)$까지 늘어날 수는 있다. ↩︎

comments powered by Disqus