[BOJ/Python]2831_댄스 파티

문제 출처:https://www.acmicpc.net/problem/2831

2831번: 댄스 파티

 

문제

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일은 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 남자의 키가 밀리미터 단위로 주어진다. 키는 절댓값이 1500보다 크거나 같고, 2500보다 작거나 같은 정수이다. 사람의 키는 주어지는 값의 절댓값이다. 키가 양수인 경우에는 자신보다 키가 큰 여자와 춤을 추기를 원하는 남자이고, 음수인 경우에는 키가 작은 사람과 춤을 추기를 원하는 남자이다.

셋째 줄에는 여자의 키가 밀리미터 단위로 주어진다. 키의 범위나 의미 역시 남자와 동일하다. 

출력

첫째 줄에 상근이가 만들어 줄 수 있는 쌍의 최댓값을 출력한다.

예제 입력 1 

1
-1800
1800

예제 출력 1

0

예제 입력 2

1
1700
-1800

예제 출력 2

1

예제 입력 3

2
-1800 -2200
1900 1700

예제 출력 3

2

 

---

풀이

 

우선 문제의 조건은 다음과 같다.

• 남자와 여자는 서로를 선택한다.
• 음수인 경우 -> 양수이면서 자신보다 절댓값이 작은 수를 선택한다.
• 양수인 경우 -> 음수이면서 자신보다 절댓값이 큰 수를 선택한다.

결국 남자와 여자는 서로 반대 부호의 수를 선택해야 하므로, 남자의 리스트를 음수와 양수로 나누고 여자의 리스트 또한 음수와 양수로 나누어 서로 다른 부호에 대하여 선택을 진행한다.

그렇다면 여기서 다음과 같은 음수 리스트와 양수 리스트에서 짝을 구하는 경우를 살펴보자. 리스트는 오름차순으로 정렬하였고, 음수 리스트와 양수 리스트의 원소의 개수는 다를 수 있다.

 

 

 

• 투 포인터를 이용한다. 음수 리스트의 경우 0번 index가 절댓값이 가장 큰 수이고, 양수 리스트의 경우 그 반대가 된다.
• 음수 리스트의 경우 포인터의 index를 점점 증가시키고, 양수 리스트의 경우 포인터의 index를 점점 감소시키며 탐색한다.

 

• 녹색 포인터가 가리키는 음수의 절댓값과 주황색 포인터가 가리키는 양수의 값을 비교한다.
• 이 경우 음수의 절댓값이 더 크기때문에, 두 수는 조건에 만족하여 쌍이 될 수 있다.

 

 

• 조건에 만족하여 쌍을 찾았다면, 녹색 포인터는 양의 방향으로 한 칸 이동하고, 주황색 포인터는 음의 방향으로 한 칸 이동한다.
• 마찬가지로 두 수의 절댓값을 비교한다.
• 여기서 음수의 절댓값이 양수의 값보다 작거나 같으므로 두 수는 쌍이 될 수 없다.
• 여기서 녹색 포인터를 오른쪽으로 옮기더라도 주황색 포인터가 가리키는 수와 쌍이 될 수 있는 수는 존재하지 않는다. 
• 따라서 주황색 포인터를 한 칸 왼쪽으로 옮긴다.

 

 

• 두 수의 절댓값의 크기를 비교한다.

 

 

• 음수의 절댓값이 양수의 값보다 더 크므로 쌍이 된다.

 

• 조건에 맞는 쌍을 찾았으므로 포인터를 한칸씩 이동시킨다.

 

 

• 마찬가지로 음수의 절댓값이 양수의 값보다 크므로 쌍을 찾고 한 칸씩 이동시킨다.

 

• 마지막으로 절댓값에 크기를 비교하고 쌍을 찾았다.
• 주황색 포인터가 더이상 이동할 곳이 없으므로 탐색을 종료한다.
• 이 경우, 총 4쌍을 찾았다.

 

이 과정을 (남자의 음수 리스트 - 여자의 양수 리스트), (여자의 음수 리스트 - 남자의 양수 리스트)에 대하여 각각 실시하고, 나온 결괏값을 더하면 된다.

코드는 다음과 같다.

 

import sys
 
def find_partner(neg_list,pos_list):
    if len(neg_list)==0 or len(pos_list)==0:
        return 0
        
    left = 0
    right = len(pos_list)-1
    count = 0
 
    while left<len(neg_list) and right>-1:
        while abs(neg_list[left]) <= pos_list[right]:
            right-=1
            if right==-1:
                break
 
        if right!=-1:
            count+=1
            left+=1
            right-=1
           
    return count
 
n = int(sys.stdin.readline())
men = list(map(int,sys.stdin.readline().split()))
women = list(map(int,sys.stdin.readline().split()))
 
men.sort()
women.sort()
 
neg_men=[]
pos_men=[]
 
neg_women=[]
pos_women=[]
 
for i in men:
    if i<0:
        neg_men.append(i)
    else:
        pos_men.append(i)
 
for i in women:
    if i<0:
        neg_women.append(i)
    else:
        pos_women.append(i)
        
 
print(find_partner(neg_men,pos_women) + find_partner(neg_women,pos_men))