2831. 댄스 파티 (Python)

2831번: 댄스 파티

 

풀이

 남성 리스트에서 음수 값을 가진 사람과 여성 리스트에서 양수 값을 가진 사람끼리 비교하고 남성 리스트에서 양수 값을 가진 사람과 여성 리스트에서 음수 값을 가진 사람끼리 비교한다.

 

 두 개의 포인터를 사용하여 하나는 음수 값을 가진 리스트의 맨 앞쪽을 가리키게 하고 하나는 양수 값을 가진 리스트의 맨 뒤쪽을 가리키게 한다(두 리스트는 정렬된 상태여야 한다). 그 후 각 포인터가 가리키는 값을 더한다. 이때 나오는 값에 따라서 다음의 작업을 한다.

 

1. 합이 음수인 경우
   -> 이는 음수쪽의 절댓값이 크다는 것이므로 음수 값을 가진 사람은 자신보다 키가 작은 이성을, 양수 값을 가진 사람은 자신보다 키가 큰 이성을 찾았음을 의미한다. 둘을 파트너로 지정하고 이제 음수 리스트의 포인터를 1 증가시키고 양수 리스트의 포인터를 1 감소시켜 다음 쌍을 찾는다.
   
   
2. 합이 0이나 양수인 경우
   -> 이는 두 사람의 키가 같거나 양수쪽의 절댓값이 크다는 것이므로 두 사람 모두 서로의 선호 유형을 찾지 못했음을 의미한다. 이 경우에는 양수 리스트의 포인터만 1 감소시켜 다음 쌍을 찾는다.
    두 리스트는 정렬되어 있는 상태이기 떄문에 음수 리스트는 포인터를 이동시킬수록 음수의 절댓값이 작아진다. 이미 양수쪽 리스트의 절댓값이 같거나 큰 상황이기 때문에 양수 리스트의 포인터를 이동시켜서 양수쪽의 절댓값만 작아지게 하여 음수쪽의 절댓값이 큰 경우를 만들어 줘야 한다.

 

코드

from bisect import bisect_left


# smaller : 음수 값을 가진 사람 리스트 (성별 무관)
# bigger : 양수 값을 가진 사람 리스트 (성별 무관)
def solve(smaller, bigger):
    global res
    smallIdx = 0  # small의 시작점
    biggerIdx = len(bigger) - 1  # bigger의 끝 부분

    while smallIdx < len(smaller) and biggerIdx >= 0:
        # 두 합이 음수일 경우, 서로가 자신이 선호하는 이성 유형을 만났음을 의미한다.
        # 두 포인터를 이동시켜 다음 쌍을 찾도록 한다.
        if smaller[smallIdx] + bigger[biggerIdx] < 0:
            res += 1
            smallIdx += 1
            biggerIdx -= 1
        else:  # 합이 0 이상일 경우, bigger의 포인터만 이동시켜 다음 쌍을 찾는다.
            biggerIdx -= 1


if __name__ == '__main__':
    N = int(input())
    men = sorted(list(map(int, input().split())))
    women = sorted(list(map(int, input().split())))
    res = 0

    manPlusIndex = bisect_left(men, 0)  # 남자 리스트에서 양수가 시작되는 인덱스
    womanPlusIndex = bisect_left(women, 0)  # 여자 리스트에서 양수가 시작되는 인덱스

    solve(men[:manPlusIndex], women[womanPlusIndex:])  # 남자의 음수, 여자의 양수
    solve(women[:womanPlusIndex], men[manPlusIndex:])  # 여자의 음수, 남자의 양수

    print(res)