BOJ 6616 - 문자열 암호화

문제

BOJ 6616 - 문자열 암호화

문자열을 N열짜리 격자에 공백을 제외한 문자를 행 우선으로 채운 뒤, 열 우선으로 읽어 암호화하는 열 전치 암호(Columnar Transposition Cipher)를 구현한다. 공백은 무시하고, 모든 문자는 대문자로 변환하여 출력한다. N이 0이면 종료한다.

입력

줄마다 N과 암호화할 문자열이 주어진다. N이 0이면 종료한다.

출력

각 케이스에 대해 암호화된 문자열을 출력한다.

예제

풀이

공백을 제거한 문자들을 N열 격자에 행 우선으로 배치한 뒤, 열 우선으로 읽어 출력하는 방식을 구현한다.

1. N을 입력받고, getline으로 나머지 문자열을 읽는다.
2. 공백을 제외한 문자 수만큼의 결과 문자열 ans를 'A'로 초기화한다.
3. i번 열(0 ~ N-1)에 해당하는 위치를 차례로 채운다. j는 i에서 시작하여 n씩 증가하며 ans.length() 미만인 동안 반복한다.
4. 각 위치 j에 대해 원본 문자열에서 공백을 건너뛰며 다음 문자를 가져와 toupper로 대문자 변환 후 배치한다.
5. 완성된 ans를 출력한다.

핵심 아이디어: 열 전치 암호는 결과 배열의 인덱스를 [열][행] 순서로 채우는 것과 같다. 결과 문자열의 j번째 위치는 i열 (j-i)/N행에 해당한다. 이를 역으로 활용하여 i(열 번호)와 j(결과 인덱스)를 직접 계산함으로써 격자를 명시적으로 생성하지 않고도 암호화를 수행한다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
 
using namespace std;
 
#define IO ios::sync_with_stdio(0), cin.tie(0)
 
int main()
{
  IO;
  int n;
  string s;
  while (cin >> n && n)
  {
    cin.ignore();
    getline(cin, s);
 
    string ans(s.length() - count(s.begin(), s.end(), ' '), 'A');
 
    int idx = 0;
    for (int i = 0; i < n; i++)
    {
      for (size_t j = i; j < ans.length(); j += n)
      {
        while (s[idx] == ' ')
        {
          idx++;
        }
        ans[j] = toupper(s[idx++]);
      }
    }
    cout << ans << '\n';
  }
}

복잡도

• 시간: O(L) — L은 문자열 길이 (공백 포함)
• 공간: O(L) — 결과 문자열 저장