백준 1797 <균형잡힌 줄서기> C++

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

1797번: 균형잡힌 줄서기

---

누적합과 해시맵을 함께 써서 풀 수 있는 문제입니다.

 

남여의 성별 코드가 ( 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;

}