[백준 2831번] 댄스 파티

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/2831

2831번: 댄스 파티

 

백준 2831번 문제 댄스 파티

약 3개월 전에 도전했다가 틀리고 미뤄뒀던 (...) 문제입니다.

당시에는 막 조합 생각하고 그랬던 것 같은데... 지금 풀어보니 5분만에 금방 풀리네요 ㅎㅎ

 

주어진 문제를 보면, 남자와 여자의 키가 각각 주어집니다.

이 때 키가 양수로 주어진다면 해당 사람은 본인보다 키가 큰 이성과 춤을 추고 싶은 사람이고, 키가 음수로 주어진다면 해당 사람은 본인보다 키가 작은 이성과 춤을 추고 싶은 사람입니다.

따라서 계산을 편리하게 하기 위해, 남녀, 양수/음수 총 4개의 리스트를 만듭니다.

male_pos, female_pos의 경우에는 값을 그대로 넣고, male_neg, female_neg에는 비교를 쉽게 하기 위해 값을 절댓값을 취하여 넣어줍니다.

 

그 다음, 4개의 리스트를 모두 정렬해 줍니다.

정렬 기준은 모두 오름차순 혹은 모두 내림차순으로 해야 합니다. 저는 내림차순으로 진행하였습니다.

 

pos는 자신보다 키가 큰 이성과 춤을 추고 싶은 사람, neg는 자신보다 키가 작은 이성과 춤을 추고 싶은 사람입니다.

male_pos, female_neg과 female_pos, male_neg 두 쌍에 대해 각각 아래와 같은 과정을 반복합니다.

 

1. 두 값 i, j를 0으로 초기화 합니다.
2. while(i < pos.size && j < neg.size) 동안 다음을 반복합니다.
   1. pos[i]와 neg[j]를 비교합니다. pos[i] < neg[j]인 경우, 서로 춤을 추고 싶은 사람을 만난 것입니다. 따라서 정답 값을 1 올리고, i와 j의 값을 1 올립니다.
   2. pos[i] < neg[j]가 아닌 경우, i와 j는 각각 다른 사람을 찾아봐야 합니다. i는 키가 더 큰 사람을 원하고, j는 키가 더 작은 사람을 원합니다. 리스트가 오름차순으로 정렬되어 있으므로, i에게 j보다 더 키가 큰 사람은 이미 짝이 지어졌거나 지나온 사람입니다. 반면, j는 i의 다음 순서의 사람이 i보다 키가 작으므로, j를 i+1과 비교해 보면 됩니다. 따라서 i값만 1 증가시킵니다.

loop가 종료되면, 가능한 최대의 남녀 쌍의 개수를 얻을 수 있습니다.

n은 최대 100000이므로, 총 20만번의 비교 이내에 답을 얻을 수 있습니다 (O(N) 시간 복잡도).

 

투-포인터 방식으로 어렵지 않게 풀 수 있는 문제였습니다.

이 문제를 왜 3개월 전에는 그렇게 고민하고 헤맸는지...

 

채점 결과