1797번: 균형잡힌 줄서기
첫째 줄에는 한 줄로 선 팬들의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 그 다음 N개의 줄에는 남녀의 성별을 나타내는 수(남자는 0, 여자는 1)와 이들이 서있는 x좌표가 공백으로 구분되어 주어진다. x
www.acmicpc.net
누적합과 해시맵을 함께 써서 풀 수 있는 문제입니다.
남여의 성별 코드가 ( 0 ,1 ) 로 존재하는데 이를 ( -1, 1 ) 로 치환하면, 즉 남자의 성별코드를 -1 로 치환하면 누적합을 통해 남여의 수가 같은 구간을 쉽게 구할 수 있습니다. 당연히 한 줄로 서있기 때문에 x 값을 기준으로 정렬해주어야 합니다.
| 인덱스 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 성별 |
남(-1) |
여(1) |
남(-1) |
여(1) |
여(1) |
여(1) |
남(-1) |
여(1) |
남(-1) |
| 누적합 |
-1 |
0 |
-1 |
0 |
1 |
2 |
1 |
2 |
1 |
의 줄을 가정하겠습니다.
1)
우선 누적합이 0 인 인덱스는 해당 인덱스까지의 남, 여 의 수가 동일합니다. -1 과 1 의 수가 같기 때문입니다.
2)
누적합이 같은 인덱스 사이의 구간은 남, 여의 수가 동일합니다. 예를 들어 인덱스 9 와 5 의 경우 5+1 부터 9 까지 남여의 수가 같습니다. 뒤의 인덱스에서의 -1 과 1 의 차이만큼 앞의 인덱스에서 빼주기 때문입니다.
이제 순회를 하며 현재 인덱스와 누적합이 같고 현재 인덱스보다 작은 인덱스를 찾으며 최대 길이를 갱신해주면 됩니다.
하지만 사람의 수가 1 ~ 1000000 사이기 때문에 O(N^2) 의 탐색의 경우 시간초과가 발생할 확률이 높습니다.
즉 이중 반복문보다 효율적인 방법을 찾아야합니다.
우리는 누적합이 같은 인덱스들중 가장 큰 인덱스의 값에서 가장 작은 인덱스의 값을 빼주면 된다고 알고 있습니다. 물론 x 값을 기준으로 정렬되어있기 때문입니다.
그렇다면 단순히 누적합이 같은 목록만 알면 순회를 다시 하지 않아도 됩니다.
그렇기에 누적합을 만들 때 해시맵에 같은 누적값을 가진 인덱스들을 정리해준다면 시간을 줄일 수 있습니다.
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
// x 를 기준으로 정렬하기 위한 함수
bool sort_by_x(array<long long int, 2>& arr_1, array<long long int, 2>& arr_2) {
return arr_1[1] < arr_2[1];
}
int main(void) {
// 줄
array<array<long long int, 2>, 1000001> line_arr{};
// 입력
int N;
cin >> N;
for (int i = 0; i < N; i++) {
array<long long int, 2> temp_arr;
cin >> temp_arr[0] >> temp_arr[1];
// 남자면 성별 인식 수를 -1로 변환
if (temp_arr[0] == 0) temp_arr[0] = -1;
line_arr[i + 1] = temp_arr;
}
// x 좌표를 기준으로 정렬
sort(line_arr.begin() + 1, line_arr.begin() + N + 1, sort_by_x);
// 누적합 맵
map<int, vector<int>> prefix_map;
prefix_map.insert(pair<int, vector<int>>(0, { 0 }));
// 남여 인식수를 누적합
// 뒤 누적합 - 앞 누적합 = 0 이면 해당 구간은 남여 수 일치
for (int i = 0; i < N; i++) {
line_arr[i + 1][0] += line_arr[i][0];
// 맵에 기록
// 이미 맵에 존재하면
if (prefix_map.find(line_arr[i + 1][0]) != prefix_map.end()) {
prefix_map[line_arr[i + 1][0]].push_back(i + 1);
}
// 존재하지 않으면
else {
prefix_map.insert(pair<int, vector<int>>(line_arr[i + 1][0], { i + 1 }));
}
}
// 최대 길이
long long int max_len{};
// 맵을 순회
for (auto iter = prefix_map.begin(); iter != prefix_map.end(); iter++) {
// 맵에 속한 벡터
auto iter_vec = iter->second;
// 맵에 인덱스가 두 개 이상이면
if (iter_vec.size() >= 2) {
// 맨 뒤와 맨 처음의 차이와 최댓값 비교
max_len = max(max_len, line_arr[iter_vec.back()][1] - line_arr[iter_vec.front()+1][1]);
}
}
cout << max_len;
}