[BOJ/백준 11582][C++] 치킨 TOP N

문제

https://www.acmicpc.net/problem/11582

 

문제 내용

하나의 배열을 정렬하는데, 이때 중간단계를 출력하는 문제이다.

참고로 여기서 쓰인 정렬의 방식은 합병 정렬이다. (합병 정렬에 대한 설명은 더보기에 있다.)

합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방식이다.

합병 정렬 예시

 

합병 정렬은 분할 정복이라는 기법에 바탕을 두고 있다.

분할 정복 기법은 문제를 작은 2개의 문제로 분할하고, 각각을 해결한 뒤에, 결과를 모아서 원래의 문제를 해결하는 방식이다.

 

문제 풀이

문제에서 설명한 방식대로 정렬을 진행한다. (sort 함수 이용)
이때, k명이 정렬을 하게 되는 단계가 오면, 그 단계까지 정렬된 결과를 출력한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n, tmp, k;
	cin >> n;
	vector<int>v;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}
	cin >> k;
	
    	//문제 해결
	int num = n / 2;
	while (num >=1) {
		
		int ssize = n / num; //한번에 몇 칸씩 넘어가야 하는지
		for (int i = 0; i < n-1; i=i+ssize) { 
			sort(v.begin() + i, v.begin() + i + ssize);
		}

		if (num == k) {
			//출력
			for (int i = 0; i < n; i++) cout << v[i] << ' ';
			cout << '\n';
			break;
		}

		num = num / 2;
	}
}

 

문제 코드 설명

1) 입력

치킨집 개수를 n, 치킨집 맛의 수치는 벡터 v에 저장하고, 현재 정렬을 진행 중인 회원들의 수를 k에 입력받는다.

 

2) 문제 해결

변수 num은 단계별로 정렬을 진행하는 사람의 수이다.
따라서 num과 k가 같아지면, 그 단계까지 정렬된 결과를 출력한다.

반복문을 돌면서 num의 값을 조정해야 하는데, 치킨집 개수가 8개였다면 num은 4 -> 2-> 1 순으로 바뀌어야 하므로, num=num/2라는 코드를 마지막에 넣어주어야 한다.

가장 중요한 정렬은 sort함수를 이용하여 해결했다.
치킨집 개수가 8개이고 num이 4라면, 배열을 4개로 나누어서 정렬을 진행하기 때문에 한 번에 2개의 원소가 정렬된다.
num이 2라면, 배열을 2개로 나누어서 정렬을 진행하므로 한번에 4개의 원소가 정렬되어야 한다.

한 번에 정렬 되어야 하는 원소의 개수를 ssize라는 변수로 두어, sort함수에서 범위를 지정하여 정렬을 하였다.