값 압축(value compression) 기본 문제로 연습
1. 문제
18869번: 멀티버스 Ⅱ
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍
www.acmicpc.net
2. 풀이
문제 이해하는것부터 쉽지 않았다
m개의 줄마다 리스트 A를 입력받아서 전체 리스트 universe에 저장해두고,
universe에서 i,j 2개를 선택해서, (i < j)
universe[i]와 universe[j]에 대하여... 다시 비교작업을 수행한다
모든 a < b <= n에 대하여, universe[i][a] < universe[i][b]이면, universe[j][a] < universe[j][b]를 만족해야하고..
universe[i][a] == universe[i][b]이면, universe[j][a] == universe[j][b]를 만족해야한다.
혹은 universe[i][a] > universe[i][b]이면, universe[j][a] > universe[j][b]를 만족해야한다.
--------------------------------------------------------------------------------------------------------------------------------
어떻게 하냐면... value compression을 수행하자
이때, value가 대응되는 인덱스를 알고 있어야 정렬을 해도 인덱스 값이 어디로 갔는지 알 수 있겠지
A = [1,3,2]이고 B = [12,50,31]일때,
B의 경우 12:0, 50:1, 31:2로 value:index로 대응시켜놓고, 정렬을 수행하면..
B = [12,31,50]인데 value:index로 대응시켜놓았기 때문에.. [0,2,1]로 value compression을 수행할 수 있다.
A도 마찬가지로 1:0, 3:1, 2:2로 대응시킨 뒤 정렬을 하면 [1,2,3]인데...
[0,2,1]로 value compression을 수행한다
그러면.. A = [0,2,1]이고 B = [0,2,1]인데... 오름차순 정렬된 상태이기 때문에.. A만 본다면..
A[0] < A[2] < A[1]이고 B만 본다면 B[0] < B[2] < B[1]이다.
index 0,1,2에서 2개씩 고르는 작업을 반복수행한다면...
A[0] < A[1]이면, B[0] < B[1]
A[0] < A[2]이면, B[0] < B[2]
A[2] < A[1]이면, B[2] < B[1]
모든 경우를 만족하므로... A,B는 균등한 우주이다
-------------------------------------------------------------------------------------------------------------------------------
위 방법을 그대로 구현해서..
다음과 같이 value compression을 수행할 수 있다
i번째 리스트를 받을때마다, compression[i] = {}으로 dict 초기화하고
리스트 순회해서 value:index로 대응시킨뒤
리스트 정렬하고, value들의 리스트를 index들의 리스트로 compression
그렇다면, index들이 대응되는 value 순으로 오름차순 정렬된 상태다.
from sys import stdin
m,n = map(int,stdin.readline().split())
universe = []
compression = {}
for i in range(m):
A = list(map(int,stdin.readline().split()))
#i번째 우주에 대한 compression map
compression[i] = {}
#value:index로 mapping
for j in range(n):
compression[i][A[j]] = j
#A를 정렬
A.sort()
#value를 index로 바꾸는 value compression 수행
for j in range(n):
A[j] = compression[i][A[j]]
universe.append(A)
m개의 우주 리스트 universe에서 서로 다른 2개 i < j를 만족하도록 i,j를 뽑는다.
두 리스트 A = universe[i], B = universe[j]라 해놓고, A,B 각각에서 모든 순서쌍을 확인한다
a < b <= n을 만족하는 두 index a,b에 대하여...
A[a] < A[b]이면 B[a] < B[b]인가?
A[a] == A[b]이면, B[a] == B[b]인가?
A[a] > A[b]이면, B[a] > B[b]인가?
모든 a < b에 대하여 단 1번이라도 위 3가지중 하나를 만족하지 않는다면... 균등하지 않으니 반복문 탈출
answer = 0
for i in range(m-1):
for j in range(i+1,m):
A = universe[i]
B = universe[j]
ok = True
for a in range(n-1):
for b in range(a+1,n):
if A[a] < A[b] and B[a] < B[b]:
continue
elif A[a] == A[b] and B[a] == B[b]:
continue
elif A[a] > A[b] and B[a] > B[b]:
continue
else:
ok = False
break
if ok == False:
break
if ok == True:
answer += 1
print(answer)
근데 이렇게 하면 시간초과가 나더라고..?
분명히 로직은 맞는것 같은데
근데 왜 문제인가? 생각을 해보니까..
이 부분 a<b를 뽑는 부분이 이중 for문일 필요가 있나?
for문 하나만 순회하면 될것 같은데? 이런 생각이 들더라고..
for a in range(n-1):
for b in range(a+1,n):
if A[a] < A[b] and B[a] < B[b]:
continue
elif A[a] == A[b] and B[a] == B[b]:
continue
elif A[a] > A[b] and B[a] > B[b]:
continue
else:
ok = False
break
if ok == False:
break
A = [0,2,1]이고 B = [0,2,1]일때...
a = 0이면 b = a+1 = 1이라 하고, A[0]=0 < A[1]=2이면, B[0] = 0 < B[1] = 2인지..
마찬가지로 a = 1이면 b = a+1 = 2로 한다면.., 즉 a를 정하고 b = a+1로 한다면, O(N)에 가능하다
answer = 0
for i in range(m-1):
for j in range(i+1,m):
A = universe[i]
B = universe[j]
ok = True
for a in range(n-1):
if A[a] < A[a+1] and B[a] < B[a+1]:
continue
elif A[a] == A[a+1] and B[a] == B[a+1]:
continue
elif A[a] > A[a+1] and B[a] > B[a+1]:
continue
else:
ok = False
break
if ok == True:
answer += 1
print(answer)
근데 여기서 지금 복기해보니까... A[a] < A[b]이면 B[a] < B[b]인지 이거 굳이 이럴 필요가 없는듯?
value compression 되어있고 A,B의 길이가 같으니까.. 방향성이 서로 같다면.. value도 같아야하잖아
그러니까 A[a] == B[a]이고 A[a+1] == B[a+1]만 검사하면 되겠는데??
from sys import stdin
m,n = map(int,stdin.readline().split())
universe = []
compression = {}
for i in range(m):
A = list(map(int,stdin.readline().split()))
compression[i] = {}
for j in range(n):
compression[i][A[j]] = j
A.sort()
for j in range(n):
A[j] = compression[i][A[j]]
universe.append(A)
answer = 0
for i in range(m-1):
for j in range(i+1,m):
A = universe[i]
B = universe[j]
ok = True
for a in range(n-1):
if A[a] == B[a] and A[a+1] == B[a+1]:
continue
else:
ok = False
break
if ok == True:
answer += 1
print(answer)
'알고리즘 > 압축 알고리즘' 카테고리의 다른 글
| 알고리즘 테크닉 - 좌표압축(grid compression) (0) | 2023.04.14 |
|---|
