[G2] 백준 2871번 아름다운 단어 C++ 그리디 알고리즘, 우선순위 큐, 구현

리뷰

 

그리디한 방법을 설계하여 알아서 문제를 푸는 구현문제인듯 하다.

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

 

전역 변수

• n : 주어진 문자열의 길이
• v : 현재 상황에서 문자열이 존재하는지 체크하기 위한 배열 크기는 최대 문자열 크기인 10만으로 초기화 한다.
• s, t1, t2 : 입력되는 초기 문자열 s, 상근이의 문자열 t1, 희원이의 문자열 t2
• Prio : 원하는 단어를 얻기 위한 우선순위 큐용 구조체
• pq : 희열이가 사용할 우선순위 큐, 문자 기준 오름차순, 같다면 인덱스 기준 내림차순 정렬을 하였다.

 

함수

없음

 

 

문제풀이

1. n과 s값을 입력받은 뒤 0부터 n - 1까지 순회해준다.
2. v배열을 모두 1로 변경해 주고 pq에는 문자와 해당 문자의 인덱스를 추가해 준다.
3. 상근이가 문자열을 가져갈 위치인 last_index를 n - 1로 초기화 해준다.
4. n만큼 while문을 개행해 준다. 만약 n이 홀수면 희원이, 짝수면 상근이의 차례이다.
5. 희원이의 차례일땐 pq가 비지 않았다면 우선순위를 통해 그리디한 문자를 계속 찾아준다.
6. 만약 아직 존재하는 문자열을 만났다면 해당 문자의 인덱스를 0으로 변경해 주고 희열이에 문자열에 추가해 준다.
7. 만약 상근이의 차례일땐 last_index가 0이상일 경우 계속 반복해 준다.
8. 이전에 탐색했던 위치부터 계속 탐색해 주며 문자가 존재한다면 해당 문자를 추가하고 인덱스를 줄여준다.
9. 매 턴마다 n값을 줄여줘서 while문을 빠져나올 수 있게 만들어 준다.
10. n은 짝수이므로 상근이와 희원이의 문자열의 길이는 똑같다, 만약 희원이의 문자열 더 우위를 점한다면 이긴것이다.
11. 희원이가 이겼으면 DA를 출력, 지거나 비겼으면 NE를 출력하고 이후에 희원이의 문자열을 출력한다.

 

참고 사항

운이 좋게도 설계단계에서 꽤나 그리디한 아이디어가 떠올라 어렵지 않게 문제를 풀었다.

 

아이디어

• 상근이는 문자열의 뒤에서부터 차례차례 문자를 가져가는 것을 문제에서 명시되어 있다.
• 그렇다면 희원이는 문자를 존재하는 문자열에서 오름차순으로 가져가야 좋다.
• 만약 상근이와 희원이가 동일한 문자열을 계속 가져가는 케이스가 있다면?
• 상근이가 가져갈 문자를 겐세이를 넣어서 먼저 가져가야겠다.
• 그렇다면 결국 문자를 오름차순으로 하고 동일하다면 인덱스가 내림차순인 pq를 사용해야 겠다.
• 그럼 둘의 탐색 방법이 다른데 동기화는 어떻게 해줘야 하는가?
• 문자열의 최대 길이는 10만이므로 배열을 통해 존재 여부를 체크할 수 있을 것 같다.
• 결론적으로 상근이는 뒤에서, 희열이는 그리디하게 문자를 가져가며 가져간 문자는 체크를 해주는 식으로 풀자

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

int n, v[100000];
string s, t1, t2;

struct Prio {
	char c;
	int index;
	bool operator<(const Prio& other) const {
		if (c == other.c) return index < other.index;
		return c > other.c;
	}
};

priority_queue<Prio> pq;

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

	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		v[i] = 1;
		pq.push({ s[i], i });
	}

	int last_index = n - 1;
	while (n) {
		if (n % 2) {
			while (!pq.empty()) {
				Prio prio = pq.top(); pq.pop();
				if (!v[prio.index]) continue;
				v[prio.index] = 0;
				t2 += prio.c;
				break;
			}
		}
		else {
			while (last_index >= 0) {
				if (v[last_index]) {
					v[last_index] = 0;
					t1 += s[last_index--];
					break;
				}
				last_index--;
			}
		}
		n--;
	}
	int win = 0;
	if (t1 > t2) win = 1;
	if (win) cout << "DA\n";
	else cout << "NE\n";
	cout << t2;
}