대엉코딩

www.acmicpc.net/problem/1655

1. 풀이방법

 - 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한

                        값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)

 - 우선순위 큐를 이용했습니다.

   (1단계)

      -가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후 

      - 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입

   (2단계)

      - 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야

         하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행

   (3단계)

      - 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)

      - 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지

         결정하면 됩니다.

2. 주의사항

 - 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.

 - 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.

3. 나의코드

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

int N;
int centervalue;

priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;

void InputToQueue(int num) {
	if (num <= centervalue) { pqless.push(num); }
	else { pqgreater.push(num); }
}
void ModifyQueue() {
	if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
		int modinum = pqless.top();
		pqless.pop();
		pqgreater.push(modinum);
	}
	else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
		int modinum = pqgreater.top();
		pqgreater.pop();
		pqless.push(modinum);
	}
}
void GetCenterValue() {
	if (pqless.size() >= pqgreater.size()) {
		centervalue = pqless.top();
	}
	else {
		centervalue = pqgreater.top();
	}
	cout << centervalue << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (i == 0) {
			pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
		}
		InputToQueue(tmp);
		ModifyQueue();
		GetCenterValue();
	}
	return 0;
}

www.acmicpc.net/problem/1715

1. 풀이방법

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

2. 주의사항

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

- 어 큐에 들어가므로 sort를 할 필요가 없다.

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

3. 나의코드

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}

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

큐를 이용한 문제입니다.

문제조건은 상세하게 나와있는 편입니다.

다만 입력조건 중 말이 헷갈리는 부분이 나와서 이는 필기노트에 제가 이해하기 쉬운 말로 바꾸어 놓았습니다.

그리고 queue는 순회가 안되므로( for문을 이용하여 배열처럼 쉽게 탐색이 안됨)

어떻게 할까 생각을 하다가 중요도를 따로 담은 vector를 소팅을 시키고

현재 중요도를 가리키는 변수 n을 선언하여 가장 높은 중요도를 가진 문서가 queue에서 pop()

되어 프린트가 되면 n을 1증가시켜 두번쨰 높은 중요도를 가리키게끔 하였습니다.

필기노트를 보시면 이해가 빠르리라 생각합니다.

다른분들은 어떻게 푸셨는지 모르겠네요. 한번 찾아봐야겠네요!.

<필기>

<코드>