BOJ 5365 - Decoder

문제

BOJ 5365 - Decoder

암호화된 메시지를 해독한다. N개의 단어가 주어지며, i번째 단어에서 추출할 문자의 위치는 이전 단어의 길이 len으로 결정된다.

• 첫 번째 단어: 1번째 문자를 추출한다.
• i번째 단어 (i >= 2): 이전 단어의 길이 위치에 해당하는 문자를 추출한다. 현재 단어의 길이가 이전 단어의 길이보다 짧으면 공백(' ')을 추출한다.

입력

• 첫 번째 줄: 단어 수 N
• 이후 N줄: 각 단어

출력

• 해독된 메시지를 한 줄로 출력한다.

예제

풀이

len 변수로 이전 단어의 길이를 추적하며 각 단어에서 len번째 위치의 문자를 추출한다.

1. N을 입력받고, 초기 추출 위치 len을 1로 설정한다.
2. N번 반복하며 단어를 입력받는다.
3. 현재 단어의 길이가 len보다 작으면 공백을 출력하고, 아니면 word[len - 1]을 출력한다.
4. len을 현재 단어의 길이로 갱신한다.

핵심 아이디어: 현재 단어에서 추출할 위치는 이전 단어의 길이이므로 len을 계속 갱신하며 사용한다. 1-indexed이므로 배열 접근 시 word[len - 1]을 사용한다. 단어 길이가 부족하면 공백을 출력하는 예외 처리가 핵심이다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n;
  cin >> n;
  size_t len = 1;
  for (int i = 0; i < n; i++)
  {
    string word;
    cin >> word;
    char decodedC;
    if (word.size() < len)
      decodedC = ' ';
    else
      decodedC = word[len - 1];
    len = word.size();
 
    cout << decodedC;
  }
  cout << "\n";
 
  return 0;
}

복잡도

• 시간: O(N) — N개의 단어를 순서대로 처리
• 공간: O(L) — L은 한 단어의 최대 길이