[S1] 백준 23758번 중앙값 제거 C++ 정렬, 그리디 알고리즘

리뷰

 

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

중앙값이 0이 되는 최소 연산 횟수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 초기 수열 정보를 저장할 배열
• n : 수의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 수를 입력 받아 배열 arr를 초기화한다.
2. sort함수를 통해 배열 arr의 원소를 오름차순으로 정렬한다.
3. 변수 ans를 0으로 초기화 하고, 배열 arr의 (n-1)/2번째 인덱스부터 0번째 인덱스까지 역순회한다.
4. 기저 조건으로 만약 arr[i]가 1이라면 break처리한다.
5. arr[i]가 1이 될때까지 2로 나누고, 연산을 수행할때 마다 ans를 증가시킨다.
6. 기저 조건에 의해 while루프가 종료된 경우 ans를 전위 증가시킨 값을 출력하면 된다.

 

트러블 슈팅

1. 초기엔 2로 나눈 몫을 다시 pq에 삽입해주는 형태로 구현하였으나 시간 초과로 인해 WA를 받았다.
2. pq에 삽입 없이 현재 요소에 대한 처리만 진행하고 버리는 방식으로 구현해 AC를 받았다.

 

참고 사항

1. 중앙값은 낮아질 수 밖에 없기 때문에 수열 arr을 정렬한 후 (n-1)/2번째 인덱스부터 0번째 인덱스까지만 역순회한다.
2. cur이 1이건, 모든 요소를 1로 만들었건 마지막엔 연산 1회가 추가되어야 하므로 ans를 전위증가 시켰다.

 

정답 코드

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

const int N = 2e6;
int arr[N];
int n;

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

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);

	int ans = 0;
	for (int i = (n - 1) / 2; i >= 0; --i) {
		if (arr[i] == 1) break;
		while (arr[i] > 1) {
			++ans;
			arr[i] >>= 1;
		}
	}

	cout << ++ans;
}