[G4] 백준 1339번 단어 수학 C++ 그리디 알고리즘, 우선순위 큐, 해시맵, 문자열

리뷰

 

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

그리디 알고리즘 치곤 여러가지 알고리즘과 자료구조를 혼합하여 푼 문제

 

 

전역 변수

• n : 주어지는 문자열의 개수
• values : 각 문자가 어떤 숫자로 파싱될지를 결정하기 위한 배열
• dic : 각 문자의 가중치를 저장하기 위한 해시맵
• words : 각 문자의 원본을 저장하기 위한 문자열 타입 배열
• Prio : PQ에서 우선순위 순으로 정렬하기 위한 구조체

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 n번의 반복문을 실행하여 각각 문자열을 문자열 변수 s에 저장해 준다.
2. words배열에 s를 기록해 주고, s를 반전시켜 각 문자를 키로 값을 10^i 만큼 더해준다.
3. Prio타입 우선순위 큐 pq를 초기화 해주고, dic를 순회하며 pq에 dic의 key와 value를 push해준다.
4. 문자 변수 top을 '9'로 초기화 해준다.
5. pq가 빌때까지 반복문을 수행하며 pq에서 요소를 꺼내 values의 꺼낸 요소의 문자의 값을 top으로 저장해 준 뒤 후위 감소 연산을 진행해 준다.
6. 정수형 변수 result를 0으로 초기화 해준다.
7. words배열을 순회하며 각 문자열의 문자를 순회하며 해당 문자를 숫자로 된 문자열로 변환해 준다.
8. stoi메서드를 통해 숫자로된 문자열을 정수로 변해준 뒤 result에 더해준다.
9. result에 저장된 값을 출력해 준다.

 

참고 사항

백트래킹으로 완탐을 돌리니 알파벳의 종류가 10개일 때 실행 시간이 좀 오래 걸려서 갈아 엎었다. (제출은 안해봄)

 

 

정답 코드

#include<iostream>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

int n;
int values[100];
unordered_map<char, int> dic;
string words[10];
struct Prio {
	char c;
	int val;
	bool operator<(const Prio& other) const {
		return val < other.val;
	}
};

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		words[i] = s;
		reverse(s.begin(), s.end());
		for (int j = 0; j < s.size(); ++j) dic[s[j]] += pow(10, j);
	}

	priority_queue<Prio> pq;
	for (const auto& d : dic) pq.push({ d.first, d.second });

	char top = '9';
	while (!pq.empty()) {
		Prio prio = pq.top(); pq.pop();
		values[prio.c] = top--;
	}

	int result = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < words[i].size(); ++j) words[i][j] = values[words[i][j]];
		result += stoi(words[i]);
	}

	cout << result;
}