BOJ 7513 - 준살 프로그래밍 대회

문제

BOJ 7513 - 준살 프로그래밍 대회

여러 테스트 케이스가 주어진다. 각 테스트 케이스에서 m개의 단어를 순서대로 저장한 후, n개의 줄에 대해 각 줄마다 k개의 인덱스를 입력받아 해당 인덱스의 단어를 공백 없이 이어붙여 출력한다.

입력

첫 번째 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스는 다음과 같다.

• 단어 수 m, 이후 m개의 단어
• 쿼리 수 n, 이후 n개의 줄에 단어 수 k와 k개의 인덱스(0-indexed)

출력

각 테스트 케이스마다 Scenario #T: 헤더를 출력한 후, 각 쿼리에 대한 결과를 한 줄씩 출력한다. 테스트 케이스 사이에 빈 줄을 출력한다.

예제

풀이

단어 배열에 저장 후 인덱스 기반 접근으로 각 쿼리를 처리한다.

1. 테스트 케이스 수 T를 읽고, 1부터 T까지 반복한다.
2. 각 테스트 케이스에서 m개의 단어를 words[] 배열에 저장한다.
3. n개의 쿼리에 대해 k를 읽고, k개의 인덱스를 순서대로 읽어 words[idx]를 출력한다.
4. 각 쿼리 줄 끝에 개행, 테스트 케이스 끝에 추가 개행을 출력한다.

핵심 아이디어: 단어를 배열에 0-indexed로 저장하면 인덱스로 O(1) 접근이 가능하다. 단어 사이 구분자 없이 연속 출력(cout << words[idx])하므로 별도 공백 처리가 필요 없다.

코드

#include <iostream>
using namespace std;
int tc, m, n, k, idx;
string words[51];
int main()
{
  ios::sync_with_stdio(0), cin.tie(0);
 
  cin >> tc;
 
  for (int t = 1; t <= tc; ++t)
  {
    cout << "Scenario #" << t << ":\n";
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
      cin >> words[i];
    }
 
    cin >> n;
 
    while (n--)
    {
      cin >> k;
 
      while (k--)
      {
        cin >> idx;
 
        cout << words[idx];
      }
      cout << "\n";
    }
 
    cout << "\n";
  }
  return 0;
}

복잡도

• 시간: O(T * (m + n * k)) — T는 테스트 케이스 수, m은 단어 수, n은 쿼리 수, k는 쿼리당 인덱스 수
• 공간: O(m) — 단어 배열 저장 (최대 51개)