[백준/C++] 1026번. 보물

문제

1026번: 보물

---

1. 첫 번째 풀이(마지막 풀이)

사고 과정

- 같은 위치끼리 곱하고 모두 더한다.

- A의 가장 큰 수를 B의 가장 작은 수에, 두 번째로 큰 수는 두 번째로 작은 수 위치에 배치하면 될 것 같다.

- 그렇다면 다음 문제는 어떻게 위치시키느냐.

- 제일 먼저 떠오르는 방법은 (B의 값, 인덱스)를 하나로 묶고 값 크기순으로 정렬하는 것. B의 값이 같을 때 인덱스 순서가 유지될 필요는 없다.

- 재배열한 A를 출력하는 게 아닌, S의 최솟값을 출력하므로, 단순하게 B를 오름차순, A를 내림차순 정렬한 후 곱하면 될 것 같다.

 

1. vector<pair<int, int>> 생성, B의 값과 인덱스 번호를 함께 저장

2. 값에 맞춰 정렬

3. A를 크기 순 정렬(내림차순)

4. 크기가 N인 새 벡터 생성, A의 요소를 순차적으로 대입

 

코드

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

int main() {
	int N, b, count = 0;
	std::cin >> N;

	std::vector<int> A(N, 0);
	std::vector<int> B(N, 0);

	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
	}

	for (int i = 0; i < N; i++) {
		std::cin >> B[i];
	}

	std::sort(A.begin(), A.end(), std::greater<int>());
	std::sort(B.begin(), B.end(), std::less<int>());

	for (int i = 0; i < N; i++) {
		count += A[i] * B[i];
	}

	std::cout << count;

	return 0;
}

 

결과

간단하게 성공했다.

---

개선

사고 과정

- 더 효율적이고, 간단한 방법은 뭐가 있을까?

- 우선 입력을 받는 부분은 수정할 게 없다.

- 입력받은 데이터를 곧바로 사용하는 것이 아닌, 가공이 필요하므로 배열에 담아두는 것 또한 필요하다. 하지만 꼭 두 줄로 쓸 필욘 없어 보인다.

- for문을 하나로 통합할 생각도 해보았지만, A가 모두 입력된 후 B가 입력되기에 조건문이 필요해 보였다. 이 부분은 그대로 두는 게 가독성이 좋아 보인다.

- sort를 보니, 배열이 하나만 있어도 충분해 보였다. 배열의 크기를 2N으로 늘리고, 절반으로 나눠 각각 정렬하는 방식으로 수정해 보았다.

 

코드

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

int main() {
	int N, count = 0;
	std::cin >> N;

	std::vector<int> A(2 * N, 0);

	for (int i = 0; i < 2 * N; i++) {
		std::cin >> A[i];
	}

	std::sort(A.begin(), A.begin() + N, std::greater<int>());
	std::sort(A.begin() + N, A.end(), std::less<int>());

	for (int i = 0; i < N; i++) {
		count += A[i] * A[i + N];
	}

	std::cout << count;

	return 0;
}

 

결과

코드 길이가 줄어들었으며, 메모리와 시간은 변하지 않았다.

---

가장 효율적인 코드

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

firstin0907님이 작성하신 코드로, 944KB의 메모리를 사용했다.

 

내 코드와 비교

- 나는 vector를 사용한 반면, 이 분은 두 배열 arra, arrb를 정의하셨고, 크기를 102로 고정하였다. 

- 나는 cin, cout을 사용해 입출력을 구현했고, 이 분은 printf, scanf를 사용해 구현하셨다. 언어는 C++로 필터링했지만, 대체로 C와 다르지 않다.

- 나는 algorithm 헤더 파일의 sort를 사용했고, 이 분은 qsort를 사용하셨다.

- C++의 sort 함수는 정렬할 데이터의 개수에 따라 퀵 소트(quick sort)와 삽입정렬(insertion sort)을 함께 사용하는 것으로 안다. 시간에 큰 차이가 없는 만큼 같은 로직으로 동작한 듯하다.

 

실험 1

vector 대신 배열을 사용하면 메모리를 더 아낄 수 있을까?

 

코드

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

int main() {
	int N, count = 0;
	std::cin >> N;

	int A[202];

	for (int i = 0; i < 2 * N; i++) {
		std::cin >> A[i];
	}

	std::sort(A, A + N, std::greater<int>());
	std::sort(A + N, A + (2 * N), std::less<int>());

	for (int i = 0; i < N; i++) {
		count += A[i] * A[i + N];
	}

	std::cout << count;

	return 0;
}

 

결과

배열로 바꾼다해서 메모리가 줄어들진 않았다.

 

실험 2

입출력으로 scanf, printf를 사용하면 메모리를 줄일 수 있을까?

 

코드

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

int main() {
	int N, count = 0;
	scanf("%d", &N);

	std::vector<int> A(2 * N, 0);

	for (int i = 0; i < 2 * N; i++) {
		scanf("%d", &A[i]);
	}

	std::sort(A.begin(), A.begin() + N, std::greater<int>());
	std::sort(A.begin() + N, A.end(), std::less<int>());

	for (int i = 0; i < N; i++) {
		count += A[i] * A[i + N];
	}

	printf("%d", count);

	return 0;
}

 

결과

마찬가지로 변화는 없었다. 중간에 컴파일 에러가 난 것은 비주얼 스튜디오로 코딩하다 보니, scanf_s로 작성해서 생긴 에러였다.

---

강평

문제 난이도 자체는 높지 않아 금방 풀 수 있었다. 처음엔 A를 재배열한 후 출력하는 걸 생각했는데, 문제를 잘 살펴보니 S의 최솟값만 출력하면 되는 문제였다. 명세를 더 꼼꼼히 봐야겠다.

리팩토링을 거치며 코드의 길이는 꽤 줄어들었지만, 가독성은 처음 작성한 풀이가 더 좋은 것 같다. 둘 중 하나를 선택하라면 난 처음 풀이를 선택할 것 같다.