[BOJ] 28449 누가 이길까

 

백준 28449 누가 이길까

 

 

 

여기서 키워드인것은 인원수가 각각 100,000이므로, 아무리 봐도 O(log N)에서 해결해야한다는 것을 알 수 있다.

 

아이디어로 사용한 것은

 

hi / arc 팀을 점수로 정렬한 뒤, 점수별 인원을 defaultdict에 저장해서 나중에 불러오는 형식으로 알고리즘을 짰습니다.

 

점수로 정렬한 이유는, 이진탐색을 하기 위함입니다.

 

i) 기본적인 셋팅

 

먼저, hi, arc에 주어진 list를 아래와 같이 둡니다.

 

hi = [1,3,7,1,7], arc = [2,2,6,10,6]

#28449 누가 이길까
import sys
from collections import defaultdict

N,M = map(int,input().split())
total = N * M
hi = list(map(int,input().split()))
arc = list(map(int,input().split()))

hi_dict = defaultdict(int)
arc_dict = defaultdict(int)

for i in range (0,N):
    hi_dict[hi[i]] += 1
for i in range (0,M):
    arc_dict[arc[i]] += 1

#hi, arc로 덮어 씌우기
hi = list(hi_dict.keys())
arc = list(arc_dict.keys())

#크기로 조절하기
hi.sort()
arc.sort()

 

위 과정을 통해 얻어진 hi_dict, arc_dict은 다음과 같습니다.

hi_dict = dict(1 : 2, 3 : 1, 7 : 1), arc_dict = dict(2 : 2, 6 : 2, 10 :1)

hi, arc는 아래와 같습니다.

hi = [1,3,7] , arc = [2, 6, 10] 꼴이 되겠습니다.

 

 

 

누적합을 통해 arc팀의 인원을 더해줍니다.

#arc팀의 인원 순서대로 카운팅하기
N,M = len(hi),len(arc)
arc_people = [0]
for i in range (0,M):
    x = arc_people[i] + arc_dict[arc[i]]
    arc_people.append(x)

 

그렇다면 arc_people의 리스트는 

arc_people = [0,2,4,5] 가 되겠군요 !

 

 

문제에서 활용할 이진 탐색은 이하와 같습니다.

#위치 찾는 인덱스 변환
def binary_search(x,A):
    start,end = 0,len(A)-1
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == x:
            return mid 
        elif A[mid] < x:
            if A[mid] <= x < A[mid + 1]:
                return mid
            else:
                start = mid
        else:
            if A[mid -1] <= x < A[mid]:
                return mid - 1
            else:
                end = mid

 

아이디어는 이하와 같습니다.

 

hi[i]가 arc[j]에서 몇번째 인덱스에 있을까? 라는 것입니다

 

즉, arc[j] <= hi[i] < arc[j+1] 꼴이 되는 j는 무엇인가? 라는 알고리즘이 되겠습니다.

 

물론, 일부 경우를 제거해야합니다.

 

예를 들어, hi[i]  <= arc[0] 이거나, hi[i] >= arc[-1]라면 위의 이진탐색 알고리즘을 사용하지 못하겠습니다.

 

이 경우는, 따로 케이스를 구분해서 계산해주도록 합니다.

#이진탐색 알고리즘 적용
win,draw = 0,0
for i in range (0,N):
    if hi[i] < arc[0]:
        #아무것도 못함
        continue
    elif hi[i] == arc[0]:
        #비기는 것만 가능
        draw += hi_dict[hi[i]] * (arc_people[1] - arc_people[0])
    elif hi[i] == arc[-1]:
        #마지막 인덱스를 제외하고 전부 승리, 마지막 인덱스에서는 비김
        draw += hi_dict[hi[i]] * (arc_people[-1] - arc_people[-2])
        win += hi_dict[hi[i]] * arc_people[-2]
    elif hi[i] > arc[-1]:
        #모든 인원들을 이길 수 있다는 뜻
        win += hi_dict[hi[i]] * arc_people[-1]
    else:
        #hi 값이 arc내에서 부등식 꼴로 나타낼 수 있다는 것
        x = binary_search(hi[i],arc)
        if arc[x] < hi[i]:
            win += hi_dict[hi[i]] * arc_people[x+1]
        else:
            win += hi_dict[hi[i]] * arc_people[x]
            draw += hi_dict[hi[i]] * (arc_people[x+1] - arc_people[x])

print(win,total -(win + draw),draw)

 

마지막 알고리즘으로 들어왔습니다.

 

hi[i]가 이기는게 몇번인지, 비기는게 몇번인지 카운팅 해줍니다. 지는 것은 전체 경우에는 앞의 두개를 빼주면 나옵니다.  (total - win - draw)

 

i) hi[i]가 "arc[0]보다 작은 경우"

 

hi[i]는 아무도 코딩으로 이길 수 없습니다. pass 합니다.

 

ii) hi[i]가 "arc[0]과 같은 경우"

 

hi[i]는 arc[0]과 비기는 방법 밖에 없습니다. 

 

draw만 추가가 되겠습니다.

 

iii) hi[i]가 "arc[-1] 보다 큰 경우"

 

hi[i]는 arc팀의 모든 인원들을 이길 수 있습니다.

 

win에만 추가가 되겠습니다.

 

iv) hi[i]가 "arc[-1]과 같은 경우"

 

hi[i]는 arc[-1] - arc[-2]명의 사람들에게는 비기지만, 그 외에 사람들에게는 전부 이깁니다.

 

win, draw 같이 올라갑니다.

 

v) 그 외

 

arc[j] <= hi[i] < arc[j +1]가 되는 j를 이분탐색을 통해 찾았습니다.

 

만약 arc[j] = hi[i]라면, win과 draw가 같이 올라가겠습니다

 

arc[j] < hi[i]라면, win에만 인원수를 추가해주면 되겠습니다.

 

 

전체 코드는 이하와 같습니다.

 

#28449 누가 이길까
import sys
from collections import defaultdict

N,M = map(int,input().split())
total = N * M
hi = list(map(int,input().split()))
arc = list(map(int,input().split()))

hi_dict = defaultdict(int)
arc_dict = defaultdict(int)

for i in range (0,N):
    hi_dict[hi[i]] += 1
for i in range (0,M):
    arc_dict[arc[i]] += 1

#hi, arc로 덮어 씌우기
hi = list(hi_dict.keys())
arc = list(arc_dict.keys())

#크기로 조절하기
hi.sort()
arc.sort()

#hi,arc팀의 인원 순서대로 카운팅하기
N,M = len(hi),len(arc)
arc_people = [0]
for i in range (0,M):
    x = arc_people[i] + arc_dict[arc[i]]
    arc_people.append(x)

#위치 찾는 인덱스 변환
def binary_search(x,A):
    start,end = 0,len(A)-1
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == x:
            return mid 
        elif A[mid] < x:
            if A[mid] <= x < A[mid + 1]:
                return mid
            else:
                start = mid
        else:
            if A[mid -1] <= x < A[mid]:
                return mid - 1
            else:
                end = mid

#이진탐색 알고리즘 적용
win,draw = 0,0
for i in range (0,N):
    if hi[i] < arc[0]:
        #아무것도 못함
        continue
    elif hi[i] == arc[0]:
        #비기는 것만 가능
        draw += hi_dict[hi[i]] * (arc_people[1] - arc_people[0])
    elif hi[i] == arc[-1]:
        #마지막 인덱스를 제외하고 전부 승리, 마지막 인덱스에서는 비김
        draw += hi_dict[hi[i]] * (arc_people[-1] - arc_people[-2])
        win += hi_dict[hi[i]] * arc_people[-2]
    elif hi[i] > arc[-1]:
        #모든 인원들을 이길 수 있다는 뜻
        win += hi_dict[hi[i]] * arc_people[-1]
    else:
        #hi 값이 arc내에서 부등식 꼴로 나타낼 수 있다는 것
        x = binary_search(hi[i],arc)
        if arc[x] < hi[i]:
            win += hi_dict[hi[i]] * arc_people[x+1]
        else:
            win += hi_dict[hi[i]] * arc_people[x]
            draw += hi_dict[hi[i]] * (arc_people[x+1] - arc_people[x])

print(win,total -(win + draw),draw)