[백준 python] 15970 화살표그리기

https://www.acmicpc.net/problem/15970

15970번: 화살표 그리기

예를 들어, 점들을 순서쌍 (위치, 색깔)로 표시할 때, a = (0,1), b = (1, 2), c = (3, 1), d = (4, 2), e = (5, 1)라고 하자.

아래 <그림 2>에서 이 점들을 표시한다. 여기서 흰색은 1, 검은색은 2에 해당된다.

<그림 2>

위의 조건으로 화살표를 그리면, 아래 <그림 3>과 같이 점 a의 화살표는 c로 연결된다. 점 b와 d의 화살표는 각각 d와 b로 연결된다. 또한 점 c와 e의 화살표는 각각 e와 c로 연결된다. 따라서 모든 화살표들의 길이 합은 3 + 3 + 2 + 3 + 2 = 13이다.

<그림 3>

점들의 위치와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어 진다. 다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.

출력

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

문제 해결

서브 태스크를 모두 통과해야 문제를 맞히는 것이기에 최악의 시간 복잡도를 보았을 때 O(N)으로 문제를 해결해야 함을 알 수 있다.

각각의 점들은 가장 가까운 같은 색깔로만 이동 가능하고 그 이동거리의 합을 res에 받아서 출력했다.

색깔에 따른 배열을 만들기 위해 dictionary를 사용했지만 조금 더 직관적으로 2차원 배열을  사용해도 됐던 문제였다.

 

딕셔너리 사용 시엔 1. 딕셔너리 값에 해당하는 객체를 생성 후 append를 해주도록 하는 방법과

2. collections모듈의 defaultdict을 사용해 key에 여러 값의 value값을 넣어주는 방법 중 하나를 선택하여

배열과 같은 방법으로 문제를 해결해준다.

 

##딕셔너리사용
n = int(input()) 
D = {}
for _ in range(n):
    a,b = map(int,input().split())
    if not b in D:
        D[b] = [a]
    else : D[b].append(a)
D = D.values()
res = 0
for i in D:
    i.sort()
    if len(i) <= 1:continue
    res += abs(i[0]-i[1])+abs(i[-1]-i[-2])
    for j in range(1,len(i)-1):
        res += min(abs(i[j]-i[j-1]),abs(i[j]-i[j+1]))
print(res)

##배열
n=int(input())
arr = [[]for _ in range(n)]
for _ in range(n):
    a,b = map(int,input().split())
    arr[b-1].append(a)
res = 0
for i in arr:
    i.sort()
    if len(i) <= 1:continue
    res += abs(i[0]-i[1])+abs(i[-1]-i[-2])
    for j in range(1,len(i)-1):
        res += min(abs(i[j]-i[j-1]),abs(i[j]-i[j+1]))
print(res)