[백준/C++] 1132번. 합

문제

1132번: 합

---

1. 첫 번째 풀이

사고 과정

보자마자 상당히 그리디한데? 라고 생각했고, 생각 그대로 코드로 옮겼다.

 

우선 각 알파벳은 한 자리의 숫자에 대응된다. 그러니, 가장 비중이 큰 값부터 9, 8, 7... 하며 주는 게 올바른 답을 도출할 것이다.

 

그럼 비중 계산은 어떻게 하는가? 입력으로 들어온 문자열(하나)에 대해, 해당하는 알파벳에 자릿수(1, 10, 100 등)를 저장한다.

 

ABC, BCA를 예로 들면

ABC에서 A = 100, B = 10, C = 1을 저장한다.

BCA에서 B = 100, C = 10, A = 1을 저장한다.

이를 가중치라고 부르자. 문자열이 새로 들어올 때마다 가중치는 더해져야 하므로, 초기 값은 0, 연산은 +=로 하면 된다.

 

1. 문자열 분해, 알파벳에 맞게 가중치를 더한다.
2. 가중치를 내림차순 정렬하고, 앞에서부터 9, 8, 7... 을 곱해 합한다.

 

문자를 기억할 필요가 없다. 그러니 map을 쓸 필요도 없고, A ~ J를 인덱스 0 ~ 10에 대응하기 위해 char - 'A'를 사용한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int n;
	std::cin >> n;

	// 알파벳 기억할 필요 없네?
	std::vector<long long> weight(10, 0);

	while (n--) {
		std::string str;
		std::cin >> str;

		// 가중치 계산 및 저장
		long long exp = 1;
        
		for (int i = str.size() - 1; i >= 0; i--) {
			weight[str[i] - 'A'] += exp;
			exp *= 10;
		}
	}

	// weight를 기준으로 내림차순 정렬
	std::sort(weight.begin(), weight.end(), std::greater<int>());

	long long answer = 0;
	int wei = 9;
	for (auto& i : weight) {
		answer += i * wei--;
	}

	std::cout << answer;
}

 

12자리 수까지 사용하니 최댓값이 90, 그래서 long long을 사용했다.

 

결과

그러나 3번 예제를 통과하지 못해, 아래 풀이로 넘어갔다.

 

2

ABCDEFGHIJ

J

 

답: 9876543202

내 코드: 9876543210

---

2. 두 번째 풀이

사고 과정

문제를 잘 살펴보니, 가장 앞에 나온 알파벳은 0이 될 수 없다는 조건이 붙어 있었다.

 

이에 따라 가장 앞에 나온 수들을 체크하고, 0이 될 수 없는 수는 가중치가 가장 작더라도 0이 되지 않게 조절해야 했다.

 

 

예를 들어 이런 상황이라면, 0이 될 수 있는 A와 H 중 가중치가 더 작은 값을 0으로 줘야 했다.

그러니 가중치의 내림차순으로 정렬했다면, 맨 끝에서부터 시작해 0이 될 수 있는 값을 탐색, 나머지 값들을 한 칸 앞으로 땡기고 이 값을 맨 끝으로 보내야 한다.

 

이 부분 알고리즘을 짜는데 꽤 오랜 고민을 했다. 처음엔 알파벳을 함께 저장하는 방식으로 선회하려 했는데, 시간을 들여 고민해보니 여전히 알파벳을 저장할 필요는 없음을 깨달았다.

 

결국 하나의 알파벳이 0이 된다면, 나머지 알파벳은 모든 조건을 통과하므로, 대상 알파벳의 가중치를 0으로 변경 후 내림차순 정렬하면, 완벽하게 위에서 생각한 대로 동작한다.

 

왜 가중치를 0으로 바꾸는가? 가중치가 실제 얼마였든, 0을 곱하면 결국 0이다. 그러니 이왕 끝으로 보낼 거, 가중치를 확실하게 0으로 만들고 정렬하면 맨 끝으로 간다.

 

그렇게 코딩하던 중, 고려할 사항 하나를 더 찾았다. 모든 알파벳이 쓰이지 않았다면 위 과정을 할 필요가 없다.

9부터 차례대로 대입하다가, 어차피 0을 대입할 일이 없다면 예외 처리를 안 해야 답이 제대로 나오기 때문.

 

이 예외들을 고려해 다시 코딩해보자.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

bool isAllCharUsed(std::vector<long long>& weight) {
	for (auto& i : weight) {
		if (i == 0) {
			return false;
		}
	}

	return true;
}

int main() {
	int n;
	std::cin >> n;

	// 알파벳 기억할 필요 없네?
	std::vector<long long> weight(10, 0);
	std::vector<bool> isNotZero(10, false);

	while (n--) {
		std::string str;
		std::cin >> str;

		// 가중치 계산 및 저장
		long long exp = 1;
		for (int i = str.size() - 1; i >= 0; i--) {
			weight[str[i] - 'A'] += exp;
			exp *= 10;
		}
		isNotZero[str[0] - 'A'] = true;
	}

	// 모든 알파벳이 쓰이지 않은 경우, 0을 고려할 필요 없다.
	if (isAllCharUsed(weight)) {
		// 0 고르기
		int min_index = -1;
		for (int i = 0; i < isNotZero.size(); i++) {
			if (isNotZero[i] == true) {
				continue;
			}

			// min_index 갱신
			if (min_index == -1 || weight[i] < weight[min_index]) {
				min_index = i;
			}
		}

		weight[min_index] = 0;	// 걔를 0으로 만든다.
	}

	// weight를 기준으로 내림차순 정렬
	std::sort(weight.begin(), weight.end(), std::greater<int>());

	long long answer = 0;
	int wei = 9;
	for (auto& i : weight) {
		answer += i * wei--;
	}

	std::cout << answer;
}

 

결과

 

그럼에도 결과는 틀렸습니다. 예제도 다 맞는데 시작부터 틀렸습니다가 떠서 화나서 4연속 넣어봤다. 3번째는 첫 번째 코드를 넣은 건데, 1프로까진 올라갔다. 별 의미는 없는 듯.

---

3. 마지막 풀이

사고 과정

그렇게 오랜 시간 질문 게시판을 뒤지며 반례를 넣어봤는데, 대부분 반례는 그냥 통과했다. 로직상 문제는 없으니까.

 

그러다 딱 하나, 반례를 찾고 디버깅하다가, 원인을 찾아냈다.

 

	// weight를 기준으로 내림차순 정렬
	std::sort(weight.begin(), weight.end(), std::greater<int>());

 

이 놈이 문제였다. 내 값은 long long인데, 비교 기준이 int라서.

 

이거 하나 때문에 참... 오래도 헤멨다. 그래도 발견한 게 어딘지

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

bool isAllCharUsed(std::vector<long long>& weight) {
	for (auto& i : weight) {
		if (i == 0) {
			return false;
		}
	}

	return true;
}

int main() {
	int n;
	std::cin >> n;

	// 알파벳 기억할 필요 없네?
	std::vector<long long> weight(10, 0);
	std::vector<bool> isNotZero(10, false);

	while (n--) {
		std::string str;
		std::cin >> str;

		// 가중치 계산 및 저장
		long long exp = 1;
		for (int i = str.size() - 1; i >= 0; i--) {
			weight[str[i] - 'A'] += exp;
			exp *= 10;
		}
		isNotZero[str[0] - 'A'] = true;
	}

	// 모든 알파벳이 쓰이지 않은 경우, 0을 고려할 필요 없다.
	if (isAllCharUsed(weight)) {
		// 0 고르기
		int min_index = -1;
		for (int i = 0; i < isNotZero.size(); i++) {
			if (isNotZero[i] == true) {
				continue;
			}

			// min_index 갱신
			if (min_index == -1 || weight[i] < weight[min_index]) {
				min_index = i;
			}
		}

		weight[min_index] = 0;	// 걔를 0으로 만든다.
	}

	// weight를 기준으로 내림차순 정렬
	std::sort(weight.begin(), weight.end(), std::greater<long long>());

	long long answer = 0;
	int wei = 9;
	for (auto& i : weight) {
		answer += i * wei--;
	}

	std::cout << answer;
}

 

결과

 

드디어 성공했다.

---

개선

사고 과정

로직은 내 생각에 매우 깔끔했으니, 가독성을 고려할 차례다.

 

bool 타입 변수에 not을 붙이는 게 좋은 방법은 아니지만, canZero보단 isNotZero가 이번 문제에선 더 알맞아 보였다. 조건의 내용이 0이 아니어야 한다! 라서.

 

코드 흐름 자체를 뒤틀 건 없어보였고, 변수의 명명 규칙(변수는 스네이크, 함수는 카멜)을 지키고, 마지막 wei를 그냥 num으로 고쳐 적었다.

 

그리고 주석을 조금 더 달았다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

bool isAllCharUsed(std::vector<long long>& weight) {
	for (auto& i : weight) {
		if (i == 0) {
			return false;
		}
	}

	return true;
}

int main() {
	int n;
	std::cin >> n;

	std::vector<long long> weight(10, 0);
	std::vector<bool> is_not_zero(10, false);

	while (n--) {
		std::string str;
		std::cin >> str;

		// 가중치 계산 및 저장
		long long exp = 1;

		for (int i = str.size() - 1; i >= 0; i--) {
			weight[str[i] - 'A'] += exp;
			exp *= 10;
		}

		is_not_zero[str[0] - 'A'] = true;
	}

	// 모든 알파벳이 쓰인 경우, 첫 자리가 0이 아님을 고려한다.
	if (isAllCharUsed(weight)) {
		// 0을 줄 자리 고르기
		int min_index = -1;
		for (int i = 0; i < is_not_zero.size(); i++) {
			if (is_not_zero[i]) {
				continue;
			}

			// min_index를 최소 가중치로 갱신
			if (min_index == -1 || weight[i] < weight[min_index]) {
				min_index = i;
			}
		}

		weight[min_index] = 0;	// 가중치가 가장 작은, 0이 될 수 있는 애한테 0을 준다.
	}

	// weight를 기준으로 내림차순 정렬
	std::sort(weight.begin(), weight.end(), std::greater<long long>());

	long long answer = 0;
	int num = 9;

	// 가중치가 가장 큰 애부터, 가장 큰 숫자와 곱해 합한다.
	for (auto& i : weight) {
		answer += i * num--;
	}

	std::cout << answer;
}

 

결과

 

로직은 그대로라 정답도 그대로.

---

가장 효율적인 코드

https://www.acmicpc.net/source/2627906

kim1246님의 코드. 변수명이 한 글자인 거빼면 알아보기 쉬웠다.

 

내 코드와 비교

로직이나 심지어는 예외 처리까지 똑같았다. 정렬을 버블 정렬로(어차피 10개가 전부니) 직접 구현한 게 그나마 차이?

 

나는 min_index를 -1로 두고 이를 비교에 ||로 넣었는데, index는 임의로 최댓값을 적어두기 어렵기 때문이었다. 0으로 하자니 0의 가중치가 실제 번호의 가중치보다 작을 수도 있었고...

 

이 분은 min과 min_index를 따로 두어, min을 13자리 수(1,000,000,000,000)로 두어 비교했다. 그래서 조건문은 깔끔해졌고, 대신 변수가 하나 더 생겼다.

 

큰 차이가 없어 이 정도로 비교를 마쳐도 될 것 같다.

---

강평

문제는 만만했으나, 조건을 제대로 안 읽은 데서 1번, 자료형을 제대로 통일하지 못한 데서 1번. 총 2번의 실수 때문에 오랜 시간을 잡아먹혔다. int로 우선 쓰고 long long을 사용하며 발생한 문제였다. 다음부턴 값의 최댓값을 미리 짐작해 처음부터 int냐 long long이냐를 정해두고 시작해봐야 겠다.