[백준 28449번] 파이썬 - 누가 이길까

백준 28449 - 누가 이길까

시간 제한 1초, 메모리 제한 1024MB

# 조건

• HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다.
• HI팀엔 N명 ARC팀엔 M명이 속해있다.
• 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 N * M개의 대결로 이루어진다.
• 모든 참가자는 코딩실력을 가지고 있다. 대결을 하면 더 높은 코딩실력을 가진 참가자가 승리하고, 두 참가자의 코딩실력이 같다면 무승부가 된다.
• 하얔이는 이 대회의 결과를 빨리 알고싶어졌다. 하얔이를 위해 대회의 결과를 예측해보자!

입력

• 첫째 줄에 HI팀의 인원 수 N, ARC팀의 인원 수 M이 공백으로 구분되어 정수로 주어진다. (1<=N, M<=100,000)
• 둘째 줄에 HI팀의 참가자의 코딩 실력을 나타내는 길이 N 수열 a가 공백으로 구분되어 정수로 주어진다. (1<=Ai<=100,000)
• 셋째 줄에 ARC팀의 참가자의 코딩 실력을 나타내는 길이 M 수열 b가 공백으로 구분되어 정수로 주어진다. (1<=Ai<=100,000)

출력

• 첫째 줄에 HI팀의 참가자의 승리 횟수, ARC팀 참가자의 승리 횟수, 무승부 횟수를 공으로 구분하여 출력하라.

# 접근 방법

• 브루트 포스로 확인한다면 O(N * M)이 되어 시간 초과를 받게 된다.
• 따라서, 정렬을 한 후 이분 탐색을 이용하여 풀어 줄 수 있다.
• 우선 입력받는 코딩 실력을 딕셔너리에 점수 별로 기입해준다.
• HI팀을 순회하면서 현재 점수를 기준으로 이분 탐색을 해준다.
  • 현재 점수가 들어갈 수 있는 곳을 찾아서 -> 크거나 같은 점수라면 right를 mid로 변경하며 가장 왼쪽을 찾아가게 하면 된다.
  • 현재 점수의 탐색이 끝난 후 right 인덱스를 + 해주고, 같은 점수가 딕셔너리에 존재한다면 비기는 경우도 + 해준다.
  • 이후 N * M - HI 팀이 이기는 수 - 비기는 수를 빼주면 arc 팀이 이기는 수가 나온다.
• 파이썬에서는 위와 같은 이분 탐색을 left, right, mid가 아닌 bisect 라이브러리를 이용하면 손쉽게 구할 수 있다.
• from bisect import bisect_left 를 해주고 이분탐색을 사용할 자리에 bisect_left(찾을 배열, 찾을 값)을 넣어준다면, 현재 코딩 실력이 들어갈 인덱스가 나온다.
  • 1 2 3 4 5에서 3이 들어갈 자리를 찾는다면 인덱스 2가 나온다.
• 또한 같은 값의 카운트를 세기 위하여 찾을 값 + 1을 하여 한 번 더 실행해준다.

import sys
input = sys.stdin.readline
from bisect import bisect_left

N, M = map(int, input().split())
hi = [*map(int, input().split())]
hi.sort()
arc = [*map(int, input().split())]
arc.sort()
result = [0, 0, 0]
for i in range(N):
    val = hi[i]
    idx = bisect_left(arc, val)
    idx2 = bisect_left(arc, val+1)
    result[2] += idx2 - idx
    result[1] += M - idx2
    result[0] += idx


print(*result)