[백준 2831번] 댄스 파티 (Python)

> 파이썬, 그리디 알고리즘, 정렬, 두 포인터

 

 

 

 

 

📖 문제 : 댄스 파티 (Python)

 

 

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

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

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

 

입력

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

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

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

 

 

출력

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

 

 

 

예제 입력 1 

1
-1800
1800

 

예제 출력 1 

0

 

 

 

내 코드

N = int(input())
men = list(map(int, input().split()))
women = list(map(int, input().split()))

visited_w = [0] * N

men.sort()
women.sort()

m_p = 0
w_p = N - 1

result = 0

while m_p < N and 0 <= w_p:

    if men[m_p] < 0 and 0 < women[w_p] and abs(men[m_p]) > abs(women[w_p]):
        result += 1
        m_p += 1
        w_p -= 1
    elif 0 < men[m_p] and women[w_p] < 0 and abs(men[m_p]) < abs(women[w_p]):
        result += 1
        m_p += 1
        w_p -= 1
    elif men[m_p] < 0 and 0 < women[w_p] and abs(men[m_p]) <= women[w_p]:
        w_p -= 1
    elif 0 < men[m_p]  and women[w_p] < 0 and men[m_p] >= abs(women[w_p]):
        w_p -= 1
    elif men[m_p] < 0 and women[w_p] < 0:
        m_p += 1
    elif 0 < men[m_p] and 0 < women[w_p]:
        w_p -= 1



print(result)

 

 

 

Point ! ⭐️ 

• 일단 이 문제는 알고리즘 분류에 '두 포인터' 라는 부분을 보고 힌트를 얻었습니다. 
  매번 여자와 남자 리스트를 for문으로 돌리며 탐색하는 것은 비효율적인 방법입니다. 
  
  그래서 여자와 남자 리스트를 정렬하여 
  남자는 가장 작은 수부터, 여자는 가장 큰 수부터 짝을 만들어줍니다. 
  
  이렇게 하는 이유는, 예를 들면
  남자 : -6 -4 -2 1 3 7
  여자 : -8 -3 -1 1 3 5
  
  일 경우, -값을 가진 사람은 '자신보다 작은 +인 상대' 를 만나고 싶어하고,
  +값을 가진 사람은 '자신보다 큰 -인 상대'를 만나야 서로 원하는 사람을 만날 수 있기 때문에,
  남자는 -6 값부터 여자는 5값부터 짝을 맺어가며 만들 수 있는 짝의 갯수가 가장 최댓값이 될 것입니다. 
  
  하지만 이럴 때의 모든 경우를 살펴봐주어야 합니다. 
  1) 자신보다 작은 +인 상대
  2) 자신보다 큰 -인 상대 의 경우를 제외한 모든 경우는 남자의 포인터를 옮기거나, 여자의 포인터를 하나씩 옮겨야하는 상황이 발생합니다. 
  3) 자신(-)과 상대(+) 이지만 자신(-)의 절댓값이 더 큰 경우 (-는 자기보다 작은 사람을 좋아함.)
  4) 자신(+)과 상대(-) 이지만 자신(+)의 절댓값이 더 작은 경우 (+는 자기보다 더 큰 사람을 좋아함.)
  5) 자신(-)과 상대(-) 
  6) 자신(+)과 상대(+)
  
  의 경우에도 포인터를 어디를 옮겨줘야하는지 정의해보며 문제를 풀면 될겁니다 :-)

 

 

 

 

 

 

백준

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

2831번: 댄스 파티