★Coordinate Compression Upper-Intermediate - 3 Solved★

★ 18870 좌표 압축 ★

 

👨🏽‍🏫 좌표 압축 구현은 먼저 정렬로 새로운 배열을 만든 다음 → 중복 제거 → 그리고 index를 계산하는 3개의 step으로 진행

 

👨🏽‍🏫 마지막 세 번째 step을 시간단축을 위해 어떤 기법을 쓰는 지에 따라 상황별로 소요 시간을 다르게 계산할 수 있다.

 

① 이분탐색 bisect_left() 계산 풀이

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

N=int(input())
l=list(map(int,input().split()))
B=sorted(set(l))
ans=[]

for i in l:
    ans.append(bisect_left(B,i))
print(*ans)

 

→ step 1) 정렬로 B[] 생성: sorted() 사용

→ step 2) 중복 원소 제거: set() 사용

→ step 3) 이분탐색: bisect_left() 사용

 

② 사전 자료구조 사용 풀이

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
B=sorted(set(l))

res={B[i]: i for i in range(len(B))}
for j in l:
    print(res[j],end=" ")

 

→ step 1) 정렬로 B[] 생성: sorted() 사용

→ step 2) 중복 원소 제거: set() 사용

→ step 3) 사전 자료형 dictionary 사용

 

※ 해당 문제의 경우 만들어진 배열 B의 index가 곧 해당 수보다 작으며 크기가 다른 수들의 개수를 뜻한다. 따라서, 수와 B의 index를 각각 key-value 쌍으로 만든 res dictionary를 만들어, 빠르게 dictionary 접근 풀이도 가능

 

→ Big-O 비교

for i in l:
    ans.append(bisect_left(B,i))
    
    
#--------------------------------


res={B[i]: i for i in range(len(B))}
for j in l:
    print(res[j],end=" ")

 

→ for문 돌고 bisect_left()는 이진탐색으로 O(logn)만큼의 시간이 소요되므로 총 O(nlogn)

→ 역시 for문 돌고 dictionary indexing 접근은 O(1)만큼의 시간이 소요되므로 총 O(n)

---

★ 24035 Impartial Offerings ★

import sys
input=sys.stdin.readline
for k in range(1,int(input())+1):
    N=int(input())
    A=list(map(int,input().split()))
    B=sorted(set(A))
    
    d={B[i]: i+1 for i in range(len(B))}
    total=0
    for i in A:
        total+=(d[i])
    print(f'Case #{k}: {total}')

 

👨🏽‍🏫 문제 설명: 10 10 20 25 라면 작은 수부터 차례로 10 1개씩 / 20 2개씩 / 25 3개씩 = 1 + 1 + 2 + 3 결과 7

→ 제목 그대로 불공평(impartially)하게 작은 gift 를 적게 1,  그 다음 큰 gift 2, 그 다음 3 이런 식으로 총 더한 결과 출력

 

👨🏽‍🏫 따라서, 선물의 크기는 전혀 중요치 않고 선물의 대소 관계만 중요하므로 Coordinate Compression 기법 적용

 

👨🏽‍🏫 위 18870 문제와 마찬가지로 퍼져 있는 수를 수의 대소 관계에 따라 압축해 각 수 별 크기 순위를 dictionary에 저장

 

👨🏽‍🏫 dictionary 접근 O(1)에 의해 모든 dictionary value를 합한 결과 total 변수 출력

---

★ 9574 Goldilocks and the N Cows ★

 

import sys
input=sys.stdin.readline

N,X,Y,Z=map(int,input().split())
ABs=[]
up,down=Y-X,Y-Z
for _ in range(N):
    A,B=map(int,input().split())
    ABs.extend([(A,'I'),(B,'O')])

ABs.sort()
ABs=[i[1] for i in ABs]

ans,cul=0,0
for j in ABs:
    
    if j=='I':
        ans=max(ans,cul+up)
        cul+=up
    else:
        cul-=down

print(N*X+ans)

 

👨🏽‍🏫

→ A(i)와 B(i) 사이를 마시면 right 온도로 Y unit of milk를 마시고, A(i) 미만은 cold 온도 X unit, B(i) 초과는 hot 온도 Z unit. (즉 총 3구간 나눔)

= 이를 다르게 표현하면

'각 cow의 A(i)를 I, B(i)를 O라고 하면 I와 O 사이일 경우 up 더 마시고, O를 초과하면 down unit 줄어든다' (그림 참고)

→ 각 cow의 I와 O를 모두 나열하고 정하면, 위 예제의 경우 3 - 4 - 5 - 7 - 8 - 10 - 13 - 20.

→ 모두 I 보다 작은 수라면 N*X만큼의 최소 unit을 마시게 되고, 최소 unit에서 1씩 증가하면서 I와 O를 거치면 up 추가되거나, down 감소

→ 도중에 I와 O를 거친 수 중 최댓값이 구하고자 하는 답!

 

① 정렬 (값, I/O 정보)인 tuple sort() (sort()는 tuple의 첫번째 원소를 기준으로 정렬)

 

② 정렬된 ABs(이미 정렬했기에 값은 의미 없음 - Coordinate Compression 완료)에서 두 번째 원소 I / O에 따라 I라면 up 추가 - 이 때 ans update / O라면 down 감소

import sys
input=sys.stdin.readline

N,X,Y,Z=map(int,input().split())
ABs=[]
up,down=Y-X,Y-Z
for _ in range(N):
    A,B=map(int,input().split())
    ABs.extend([(A,'I'),(B,'O')])

ABs.sort()

ans,cul=0,0
for j in ABs:
    
    if j=='I':
        ans=max(ans,cul+up)
        cul+=up
    else:
        cul-=down

print(N*X+ans)

---