[BOJ] 2713 규현이의 사랑을 담은 문자메시지

https://www.acmicpc.net/problem/2713

BOJ - 규현이의 사랑을 담은 문자메시지

문제 유형: 행렬, 구현, 문자열 처리

문제 난이도: Silver I

시간 제한: 1초

메모리 제한: 128MB

 

문제

규현이는 승환이에게 사랑을 담은 문자 메시지를 자주 보낸다. 이것을 남에게 보이기 싫었던 규현이는 승환이와 비밀 규칙을 만들었다.

규현이는 비밀 메시지를 만들기 위한 행렬의 행의 수 R과 열의 수 C를 정했다. 그 다음 다음과 같은 규칙으로 비밀 메시지를 만든다.

1. 모든 글자는 알파벳 대문자와 공백으로 이루어져 있다.
2. 글자는 다음과 같이 숫자로 바뀐다. 공백 = 0, A = 1, B = 2, ..., Y = 25, Z = 26

먼저 규현이는 문자를 위 규칙을 이용해 글자를 숫자로 바꾼 다음에 이것은 5자리 이진수로 바꾼다. 그 다음 아래 그림과 같이 소용돌이 패턴으로 행렬에 채운다. 행렬의 모든 칸을 채우지 못할 때는, 0으로 계속 채운다. 예를 들어 규현이가 보내려는 메시지가 "ACM"이고, R=4, C=4로 정했다면, 다음과 같이 행렬을 채우면 된다.

A = 00001, C = 00011, M = 01101, 모자라는 칸은 0으로 채운다.

그 다음 행렬을 행 우선으로 읽은 뒤 (Row Major Order)에 승환이에게 보낸다.

위의 예시를 메시지로 보낸다면 0000110100101100이 된다.

R, C, 규현이가 보내려고 하는 메시지가 주어졌을 때, 이를 승환이에게 보내는 비밀 메시지로 변환하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 1,000) 각 테스트 케이스는 한 줄로 이루어져 있고, R, 공백, C, 공백, 규현이가 보내려고 하는 메시지로 이루어져 있다. (1 ≤ R,C ≤ 21) 메시지는 [A-Z]와 공백으로만 이루어져 있고, 이 길이는 항상 (R*C)/5보다 작거나 같다.

 

출력

각 테스트 케이스에 대해 규현이가 문자로 보낼 비밀 메시지를 출력한다.

 

풀이

글자별 5비트 매핑테이블을 만들어줬다.

이걸로 인코딩했다.

인코딩된 문자열을 달팽이 모양으로 행렬에 넣고 나머지 부분은 0으로 채운다.

달팽이모양로 행렬을 도는 구현은 코드 참조.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int t;

unordered_map<char, string> base32 = {
    {' ', "00000"}, {'A', "00001"}, {'B', "00010"}, {'C', "00011"},
    {'D', "00100"}, {'E', "00101"}, {'F', "00110"}, {'G', "00111"},
    {'H', "01000"}, {'I', "01001"}, {'J', "01010"}, {'K', "01011"},
    {'L', "01100"}, {'M', "01101"}, {'N', "01110"}, {'O', "01111"},
    {'P', "10000"}, {'Q', "10001"}, {'R', "10010"}, {'S', "10011"},
    {'T', "10100"}, {'U', "10101"}, {'V', "10110"}, {'W', "10111"},
    {'X', "11000"}, {'Y', "11001"}, {'Z', "11010"}};

string encode(string msg) {
  string res = "";
  for (char ch : msg) {
    res += base32[ch];
  }
  return res;
}

void solve() {
  int r, c;
  cin >> r >> c;
  string msg;
  cin.ignore();
  getline(cin, msg);

  vector<vector<char>> mat(r, vector<char>(c));
  string encoded = encode(msg);

  int tot_length = r * c;
  int minx = 0;
  int miny = 0;
  int maxx = r - 1;
  int maxy = c - 1;
  int k = 0;
  int n = encoded.size();
  while (k < tot_length) {
    for (int i = miny; i <= maxy && k < tot_length; ++i) {
      mat[minx][i] = k < n ? encoded[k] : '0';
      k++;
    }
    minx++;
    if (k >= tot_length)
      break;

    for (int i = minx; i <= maxx && k < tot_length; ++i) {
      mat[i][maxy] = k < n ? encoded[k] : '0';
      k++;
    }
    maxy--;
    if (k >= tot_length)
      break;

    for (int i = maxy; i >= miny && k < tot_length; --i) {
      mat[maxx][i] = k < n ? encoded[k] : '0';
      k++;
    }
    maxx--;

    if (k >= tot_length)
      break;

    for (int i = maxx; i >= minx && k < tot_length; --i) {
      mat[i][miny] = k < n ? encoded[k] : '0';
      k++;
    }
    miny++;
  }

  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      cout << mat[i][j];
    }
  }
  cout << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}