백준 23326번: 홍익 투어리스트 (C++)

ttps://www.acmicpc.net/problem/23326

이 문제를 접근 할 때 map STL을 통해서 key값을 구역으로 두고 value값을 명소 여부인 0,1을 저장하려고 하였다. 하지만 이렇게 접근하면 실제로 시계 방향으로 이동하거나 시계 방향으로 최소 몇 칸 움직여야 하는지 출력하는 과정에서 map내부의 값을 다 돌아야 하므로 시간 복잡도가 최대 O(500,000*100,000)으로 초과하게된다. 그렇지만.. 풀이 방법이 떠오르지 않아서 아래와 같은 풀이로 시간 초과가 발생하였다. 아래 풀이는 참고하지 말자....!

#include <bits/stdc++.h>
#include <set>
//#include <unordered_set>
using namespace std;

map<int, int> m;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;

	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		m[i] = a;
	}

	auto it = m.begin();


	for (int i = 0; i < q; i++)
	{
		bool flg = false;
		int cmd1;
		cin >> cmd1;
		if (cmd1 == 1)
		{
			int cmd2;
			cin >> cmd2;
			if (m[cmd2] == 0) m[cmd2] = 1;
			else m[cmd2] = 0;
		}
		else if (cmd1 == 2)
		{
			int cmd2;
			cin >> cmd2;
			for (int i = 0; i < cmd2; i++)
			{
				if (it == prev(m.end()))
				{
					it = m.begin();
				}
				else
				{
					it++;
				}
			}
		}
		else if (cmd1 == 3)
		{
			auto log = it;
			int count = 0;
			for (auto i = 0; i < n; i++)
			{
				if (log->second == 1)
				{
					cout << count << '\n';
					flg = true;
					break;
				}

				if (log == prev(m.end()))
				{
					log = m.begin();
				}
				else
				{
					log++;
				}
				count++;
			}
			if (flg == false)
			{
				cout << -1 << '\n';
			}
		}
	}

	cout << '\n';

}

아래는 바킹독님 풀이다.. 보기엔 어려워 보이지만 하나씩 값을 넣어보면 이해가 갈 것이다. 확실한건 수학적 센스로 푸는 문제라고 봐도 무방하다.

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/98c1742e07124ec0a3731f5e891a7651
#include 
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  set hu;  // 홍익대학교의 명소들 위치
  int N, Q, t, curr = 1;
  cin >> N >> Q;
  for (int i = 1; i <= N; i++) {
    cin >> t;
    if (t) hu.insert(i);
  }
  while (Q--) {
    cin >> t;
    switch (t) {
      case 1:
        cin >> t;
        if (hu.find(t) != hu.end())
          hu.erase(t);
        else
          hu.insert(t);
        break;
      case 2:
        cin >> t;
        curr = (curr + t - 1) % N + 1;
        break;
      case 3:
        if (hu.empty()) cout << -1 << '\n';
        else {
          auto it = hu.lower_bound(curr);
          if (it != hu.end())
            cout << *it - curr << '\n';
          else
            cout << N - curr + *hu.begin() << '\n';
        }
    }
  }
}