7985

 

queue<pair<int, int>> qq[2];

static void clear_q(void)
{
	while (!qq[0].empty())
		qq[0].pop();
	while (!qq[1].empty())
		qq[1].pop();
}

static void solution(void)
{
	int K, n = 1, turn = 0;
	int * list;

	cin >> K;
	for (int i = 0; i < K; i++)
		n <<= 1;
	list = new int[n];

	for (int i = 1; i < n; i++)
		cin >> list[i];
	qq[turn].push(pair<int, int>(1, n - 1)); //초기 값

	for (int level = 1; level <= K; level++)
	{
		while (!qq[turn].empty())
		{
			pair<int, int> p = qq[turn].front();
			int mid = (p.first + p.second) / 2;

			qq[turn].pop();
			cout << list[mid] << " ";

			qq[1 - turn].push(pair<int, int>(p.first, mid - 1));
			qq[1 - turn].push(pair<int, int>(mid + 1, p.second));
		}
		turn = 1 - turn;
		cout << endl;
	}

	delete[]list;
	clear_q();
}

수열의 중앙에 위치한 값들을 먼저 출력하게 하면 된다.

an = {a} b {c}, 수열을 중앙에 존재하는 값과 이를 중심으로 좌우에 또 다른 수열로 분리하여 생각 할 수 있다.

이제 다음 과 같이 생각 할 수 있다.

         b

    {a}     {c}

즉, 각 수열에서 중앙값을 통해 좌우 두개의 새로운 노드를 만들 수 있는 것이다.

그래서 qq[turn] 에서 하나를 pop 하면 qq[1-turn]에 두개의 새로운 정보가 큐잉 되는 것이다.

이를 각 레벨 마다 큐가 empty 할 때 까지 반복하는 것이다.