백준 7453번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
12초	1024MB	골드 2

---

풀이

 이 문제는 단순무식한 문제이지만, 그래도 배울만한 점이 꽤 있는 문제이다. 시간제한이 12초라는 듣도보도 못한 엄청난 수치에 그래도 배열 길이가 4천밖에 안되기 때문에 완탐을 하는게 아니고선 어지간해서 통과될거라 생각했다.

 

문제를 보자마자 떠올린 풀이는, a배열과 b배열, c배열과 d배열의 각 원소의 합을 저장한 원소를 ab, cd배열이라고 하자. ab배열과 cd배열에는 중복되는 원소가 존재할 수도 있고 아닐수도 있다. 그렇기에 unordered_map에 원소와, 해당 원소가 등장하는 횟수를 기록한다. unordered_map은 해시이기에 평균적으로 탐색에 O(1)이다. O(logN)의 속도를 가지는 레드블랙트리 기반의 map보다 효율적으로 탐색할 수 있기에, 데이터의 갯수가 매우 많은 해당 문제에선 unordered_map이 더 적합하다고 생각했다. key를 원소의 값, value를 key원소의 등장 횟수로 저장한다. ab와 cd의 원소 개수를 모두 작성했다면 ab에 존재하는 임의의 원소 A에 -1을 곱한 -A값이 cd에 있는지 탐색하여, ab[A]의 값과 cd[-A]의 값을 곱해주면 0을 만드는 조합의 개수를 셀 수 있을 것이라 믿었다.

WA코드-TLE, MLE

// TLE
#include<bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
using namespace std;

int n;
map<int, int> ab, cd;

void input(){
    cin >> n;
    vector<int>a(n),b(n),c(n),d(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ab[a[i]+b[j]]++;
            cd[c[i]+d[j]]++;
        }
    }
}

void sol(){
    uint64_t res=0;  
    for(auto& [target, cnt] : ab){
        if(cd.find(-target) != cd.end()){
            res += 1ULL * cnt * cd[-target];
        }
    }
    cout << res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

// MLE
#include<bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
using namespace std;

int n;
unordered_map<int, int> ab, cd;

void input(){
	cin >> n;
	vector<int>a(n),b(n),c(n),d(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if (ab.find(a[i]+b[j]) != ab.end()) {
				ab[a[i]+b[j]]++;
			}
			else {
				ab.insert({a[i]+b[j], 1});
			}
			if (cd.find(a[i]+b[j]) != cd.end()) {
				cd[c[i]+d[j]]++;
			}
			else {
				cd.insert({c[i]+d[j], 1});
			}
		}
	}
}

void sol(){
	uint64_t res=0;  
	for(auto& [target, cnt] : ab){
		if (cd.find(-target) != cd.end()) {
			res += 1ULL * cnt * cd[-target];
		}
	}
	cout << res;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

그렇게 WA를 받았다. 상남자식으로 ab[a[i]+b[j]]++; cd[c[i]+d[j]]++; 이런식으로 바로 key값을 통해 접근했다가 또 틀렸다. 물론 이건 해시충돌이 일어나거나, 객체를 계속 생성하는 방식이기 때문에 TLE를 받고나서 WA를 인정했고, 코드를 개선하여 find와 insert를 통해 잘 접근했는데도 MLE를 받았다. 이는 ab와 cd를 동시에 저장해선 안된다는 뜻이 된다. 이를 해결해보고자 cd를 생성할 필요 없이 ab만 생성한 후, cd는 반복문을 통해 원소를 만들고 이 원소에 -1을 곱한 원소가 ab에 있는지 탐색하는 방향으로 바꿨다.

WA코드-TLE

#include<bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
using namespace std;

int n;
unordered_map<int, int> ab;
vector<int> a, b, c, d;

void input(){
	cin >> n;
	a.resize(n), b.resize(n), c.resize(n), d.resize(n);

	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if (ab.find(a[i] + b[j]) != ab.end()) {
				ab[a[i] + b[j]]++;
			}
			else {
				ab.insert({a[i] + b[j], 1});
			}
		}
	}
}

void sol(){
	long long res = 0;
	int target;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			target = -(c[i] + d[j]);
			if (ab.find(target) != ab.end()) {
				res += ab[target];
			}
		}
	}
	cout << res;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

 그래서 이번엔 TLE를 받았다. 이해할 수 없었다. 분명 해시는 시간복잡도가 거의 O(1)에 가깝기 때문에 시간초과를 받을 것이란 생각을 못했다. 저장방식 자체가 문제라는 뜻이 된다. 이후 며칠동안 고민했다가, 지인의 힌트를 듣고 머리속에서 깨달음을 얻었다. 내가 힌트를 얻으려고 물어볼때마다 나에게 역으로 질문하는 것이 있다.

"왜 이렇게 작성해?"
"이 코드의 의도가 뭐야?"

 

 항상 나에게 역으로 질문하고, 내가 대답을 이끌어내도록 하는 것이다. 요는 내가 작성하는 코드가 왜 작성되었는지 그 의도를 항상 명확히 파악하라는 것이다. 이를 통해 내가 스스로 깨달아가기도 하고, 깨닿지 못한다면, 내 의도를 듣고나서(정확히는 내가 문제에서 요구하는 대로 그 의도를 명확하게 작성했는지를 확인하고 나서) 그 의도를 표현하려면 어떠한 방식이 더 효율적일지 고민시키는 정도다. 정 깨닿지 못한다면 그때가선 더 알려주기도 한다.

 

 이번 문제에서 질문은 "unordered_map을 왜 썼는가?" 에서 시작한다. 의도는 원소의 등장횟수를 저장해두기 위해서였다. 하지만 해시테이블은 최악의 경우 O(N)이고, 해당 문제는 ab의 최대크기가 n^2이기 때문이 O(n^2)이 되며(그러니까 원소 갯수만큼의 선형 복잡도) TLE가 난다는 것이다. unordered_map이 됐던 map이 됐던 둘다 저격데이터를 만들기 매우 쉽고, 나는 그 저격데이터에 헤드샷을 맞은 격이다. 그래서 내 의도를 더 명확히 해주었다. 이에 대해 논의한 질문 글들이 존재한다. 바로 읽진 말고, 그래도 시도를 좀 더 해보고 읽어보자.

• https://www.acmicpc.net/board/view/115684
• https://www.acmicpc.net/board/view/62051
• https://www.acmicpc.net/board/view/76438

 

어쨌든 내가 알고 싶은건 원소의 등장횟수를 알고 싶은 것이고, 이는 탐색만 한다는 뜻이다. 세그먼트 트리 문제처럼 배열의 정보가 바뀔 것도 아니고, ab는 한번 저장이 끝나면 배열의 정보가 정적이기에 바뀌지 않는다. 문제에서 바꾸지 않기 때문이다. 그렇기에 map을 쓸 이유가 없다는 뜻이 된다. 아이디어가 떠올랐다.

 

 ab를 단순히 배열로 저장한다. 이후 ab배열을 정렬하면 중복된 원소는 중복된 원소끼리 뭉쳐있을 것이다. 이후 c배열과 d배열로 만들 수 있는 값에 -1을 곱한 값을 upper_bound와 lower_bound를 통해 갯수를 세주면 된다. upper_bound는 어떤 값보다 큰 값이 제일 처음으로 나오는 위치이고, lower_bound는 어떤 값보다 같거나 큰 값이 제일 처음으로 나오는 위치를 반환하기 때문이다.

AC코드

#include<bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
using namespace std;

int n;
vector<int> ab, a, b, c, d;

void input(){
	cin >> n;
	a.resize(n), b.resize(n), c.resize(n), d.resize(n), ab.resize(n*n);

	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			ab[i * n + j] = a[i] + b[j];
		}
	}
	sort(ALL(ab));
}

void sol(){
	long long res = 0;
	int target;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			target = -(c[i] + d[j]);
			res += (int)(upper_bound(ALL(ab), target) - lower_bound(ALL(ab), target));
		}
	}
	cout << res;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

파이썬에서는 dict를 이용해 해시로 AC를 받을 수 있는것을 알았다. 그래서 지인에게 하소연하니까 놀랍게도 C++에서도 해시를 이용해 풀 수 있다는 것이다. 이를 소개하면서 흑마법이라고 표현했다. 요는 커스텀 해시 테이블을 만드는 것이다. 다음은 몇가지 예제와 소개글이다.

 

https://codeforces.com/blog/entry/62393 : unordered_map, unordered_set을 저격하기 쉬운 이유와 저격을 피하는 방법을 소개한다.

// https://www.acmicpc.net/source/share/c0893de521044723959f2efd3dd4b362
// 위에 링크를 달아둔 https://www.acmicpc.net/board/view/76438 에서 답변자 WeissBlume님이 공유한 코드이다.

#pragma GCC optimize("Ofast")
#include<cstdio>
#include<chrono>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
using namespace std;
using ii = pair<int, int>;
int read(int x = 0) { return scanf("%d", &x), x; }

int n = read();
int d[4][4000];

struct HH {
	[[gnu::const]] static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	[[gnu::const]] size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x ^ FIXED_RANDOM);
	}
};

__gnu_pbds::gp_hash_table<int,int,HH> e;

int main()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++)
			scanf("%d", &d[j][i]);
	}

	for (int j = 0; j < 4; j++) sort(d[j], d[j] + n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			++e[-d[0][i]-d[1][j]];
	}


	long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			if (auto k = e.find(d[2][i]+d[3][j]); k != e.end())
				ans += k->second;
	}

	return !printf("%ld\n", ans);

}

 

해시 테이블에 대한 공부가 되고 좋았다. 그리고 시간을 많이 준데에는 이유가 있다는 것도 알았다.