BOJ 4459 - Always Follow the Rules in Zombieland

문제

BOJ 4459 - Always Follow the Rules in Zombieland

좀비랜드에는 번호가 매겨진 규칙들이 존재한다. n개의 규칙이 순서대로 주어지며, 각 규칙은 한 줄의 텍스트다. 이후 m번의 쿼리가 주어지며, 각 쿼리는 특정 번호의 규칙을 요청한다. 해당 번호의 규칙이 존재하면 내용을 출력하고, 없으면 No such rule을 출력한다.

입력

첫째 줄에 규칙 수 n이 주어진다. 이후 n줄에 걸쳐 규칙 텍스트가 주어진다. 그 다음 줄에 쿼리 수 m이 주어지고, m개의 규칙 번호가 한 줄에 하나씩 주어진다.

출력

각 쿼리에 대해 Rule t: {내용} 형식으로 출력한다. 규칙이 없으면 Rule t: No such rule을 출력한다.

예제

풀이

규칙 번호를 키로, 규칙 텍스트를 값으로 하는 map에 저장한 뒤 쿼리를 처리한다.

1. 규칙 수 n을 읽고, getline으로 n개의 규칙을 순서대로 map에 저장한다 (키: 1부터 시작).
2. 쿼리 수 m을 읽는다.
3. 각 쿼리 번호 t에 대해 map에서 탐색한다.
4. 존재하면 Rule t: {텍스트}, 없으면 Rule t: No such rule을 출력한다.

핵심 아이디어: 공백 포함 줄 입력이므로 getline을 사용하며, cin >> n 이후 개행 문자를 소비하기 위해 cin.ignore()를 호출해야 한다. map::find()로 O(log n) 탐색을 수행한다.

코드

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n = 0;
 
  cin >> n;
  string str = "";
  map<int, string> mp;
  cin.ignore();
  for (int i = 0; i < n; i++)
  {
    getline(cin, str);
    mp.insert({i + 1, str});
  }
  int m = 0;
  int t = 0;
  cin >> m;
  while (m--)
  {
    cin >> t;
    cout << "Rule ";
    if (mp.find(t) != mp.end())
      cout << t << ": " << mp[t] << '\n';
    else
      cout << t << ": " << "No such rule" << '\n';
  }
 
  return 0;
}

복잡도

• 시간: O(N + M log N) — 규칙 저장 O(N log N), 쿼리 M번 각 O(log N)
• 공간: O(N) — N개의 규칙 문자열 저장