[백준] 1797 균형잡힌 줄서기

1797번: 균형잡힌 줄서기

풀이 아이디어

일렬로 세웠을 때 성별의 수가 같은 가장 긴 그룹을 구하는 문제이다.

 

데이터의 범위가 적으면서 이 문제와 결이 비슷한 문제가 많은데

데이터의 범위가 적을 경우

한 방향 누적합을 통해 시작 지점과 끝 부분의 누적합을 빼서 성별의 균형을 유지하는 식으로 브루트포스를 진행한다면

O(n^2)으로 해결할 수 있다.

 

그러나 해당 문제는 n이 100만임으로 브루트포스를 진행하면 시간오버가 나게 된다.

 

이 문제를 푸는데 핵심은

문제에서 요구하는 것이 가장 긴 연속적인 선분이라는 것과

map을 통한 계산이다.

 

가장 긴 연속적인 선분이라는 것은 

전체에서 조건에 부합하는 양쪽 선분을 제외한 것과 동치라는 것이다.

위와 같이 생각한다면

 

우리가 구하려는 것은 전체에서

 

성별의 균형을 이루도록 하는 좌측 연속 선분과 우측 연속 선분을 제외하면 된다.

이때 우리가 구하려는 것은 가장 긴 선분임으로 

끝부분이 0 1 0 1 0 인 경우

 0 1 0과 0 1 0 1 0은 성별 균형 조건이 동일한 값이고

더 짧은 선분인 0 1 0 을 쓰는게 옳다.

 

즉 양측 연속 선분을 누적합으로 계산하면서

각 누적합 선분의 성별 조건에 대해서 최초로 나타나는 선분만 사용하도록 하면 된다.

 

양측 연속 선분을 다 구하고 난다면

이를 map으로 저장해서

 

좌측 연속 선분을 순회하며 (최대 n개) 

전체 성별 조건 - 좌측 연속 선분을 키값으로 갖는 우측 연속 선분이 존재하는가를 판단해

존재한다면 벨류값을 바탕으로 선분의 길이를 구하면 된다.

 

map을 사용했기 때문에 처음 언급한  브루트 포스보다 빠르게 접근할 수 있다.

 

시간 복잡도는

양쪽 누적합 2N

맵 삽입 시간 N logN

선분 탐색 시간 N * logN임으로

 

O(NlogN)이다

 

 

시행착오

lgcpc에서 비슷한 유형의 문제를 봤었고, 문제에 대해 익숙했기 때문에

무난하게 풀 수 있었다.

 

최적화 하기

선분을 계산하는데 있어서

가장 짧은 선분을 계산했을 때 그게 승락된다면 그 외의 값은 무시해도 된다.

 

그러나 가장 마지막 부분에 조건을 수락하는 값이 존재할 수 있기 때문에

 

map의 정렬은 아무런 쓸모가 없어지게 된다.

 

따라서 공간복잡도를 더 잡아 먹지만,

unordered_map을 사용한다면 삽입 속도나 탐색 속도를 줄여서 시간 복잡도를 더 줄일 수 있다.

 

 

아래가 map / 위가 unordered_map 이다.