출처 : https://www.acmicpc.net/problem/15970
문제를 풀기에 앞서 문제부터 분석을 해볼까요?
일단 문제를 보게되면, 주어진 시간이 2초이기 때문에 대략 2억 회의 연산까지만 허용이 되는 것을 유추할 수 있습니다. 점의 개수가 5000개로 제한이 되어있기 때문에, N^2의 복잡도는 충분히 소화가 가능한 문제임을 유추가 가능합니다.
따라서, 복잡도는 크게 신경을 쓰지 않고 이중 반복문을 사용해도 괜찮다는 결론이 나왔습니다.
이 문제를 어떻게 풀까요?
일단 이 문제를 풀기 위해서는 다음의 고민이 필요합니다 :
- 좌표를 입력받아서, 어떤 방식으로 저장을 해야할까?
- 좌표를 저장한 후에, 같은 색깔을 가진 점들 사이에서 화살표의 길이는 어떻게 뽑아내야 하는가?
이에 대한 고민의 결과로, 저는 이렇게 풀기로 결정했습니다 :
- 좌표 정보를 딕셔너리 형태로 저장을 해서, key는 색깔로 하고, value의 경우 좌표들을 저장하는 리스트 형태로 지정하기로 하였습니다.
- 딕셔너리 형태로 변수를 저장한 후에는, 딕셔너리를 key에 해당하는 리스트를 뽑아와서 리스트를 sort한다.
- sort된 리스트에서, 기준 좌표에서 양 좌표를 비교해서 최솟값을 sum에 더한다.
일단 위의 과정을 거쳐서 풀어낸 코드부터 제시하겠습니다!
코드를 확인해볼까요?
import sys
input = sys.stdin.readline
N = int(input())
point_dict = {}
sum = 0
# 좌표 입력 받기
for _ in range(N):
input_data = list(map(int, input().split()))
if input_data[1] not in point_dict.keys():
point_dict[input_data[1]] = [input_data[0]]
else:
point_dict[input_data[1]].append(input_data[0])
# 색깔 기준으로 좌표를 정렬한 다음에, 화살표 길이를 구해서 sum에 더하는 구조
for key in point_dict.keys():
target_list = sorted(point_dict[key])
first, last = 0, len(target_list) - 1
for i in range(len(target_list)):
if i == first:
sum += (target_list[1] - target_list[first])
elif i == last:
sum += (target_list[last] - target_list[last - 1])
else:
cand1 = target_list[i] - target_list[i - 1]
cand2 = target_list[i + 1] - target_list[i]
sum += min(cand1, cand2)
print(sum)코드를 분석하겠습니다
일단 딕셔너리에 좌표 정보들을 저장하는 코드를 분석해보겠습니다
for _ in range(N):
input_data = list(map(int, input().split()))
if input_data[1] not in point_dict.keys():
point_dict[input_data[1]] = [input_data[0]]
else:
point_dict[input_data[1]].append(input_data[0])input_data에는 좌표, 색깔 순서로 값이 저장되어있습니다.
input_data의 1번 인덱스에는 key에 해당하는 색깔이 존재하기 때문에, 1번 인덱스를 Key로 하여서 0번 인덱스를 list에 추가시키는 과정이 필요합니다.
그런데 기존에 존재하지 않던 색깔이 입력이 되는 경우에는, value에는 아무것도 할당이 되어있지 않은 상태이기 때문에 list를 새로 만들어서 input_data[0]을 최초 리스트에 할당하는 방식을 채택하였습니다.
만일 기존에 존재하던 key인 경우에는, 그저 list에 좌표를 append하는 방식으로 진행하면 됩니다.
🎬 입력
7
6 1
7 2
9 1
10 2
0 1
3 1
4 1🎬 point_dict에 담긴 정보
{1: [6, 9, 0, 3, 4], 2: [7, 10]}그 다음으로, 화살표의 길이를 구해서 sum에 반영하는 코드를 분석하겠습니다.
for key in point_dict.keys():
target_list = sorted(point_dict[key])
first, last = 0, len(target_list) - 1
for i in range(len(target_list)):
if i == first:
sum += (target_list[1] - target_list[first])
elif i == last:
sum += (target_list[last] - target_list[last - 1])
else:
cand1 = target_list[i] - target_list[i - 1]
cand2 = target_list[i + 1] - target_list[i]
sum += min(cand1, cand2)일단, key를 기준으로 list를 가져와서 sort를 진행한 뒤 target_list에 저장합니다.
그리고 생각을 해봐야하는 것이, 첫번째 좌표와 마지막 좌표의 경우 양 방향 비교가 불가능 하기 때문에, 첫번째 좌표의 경우는 바로 다음 좌표와의 길이를 sum에 반영하고, 마지막 좌표의 경우 바로 이전의 좌표와의 길이를 sum에 반영하면 됩니다.
그 외의 좌표의 경우에는, 양방향으로 길이를 비교해서, 두 길이를 서로 비교하여 그 중에 더 작은 값을 sum에 더하면 됩니다.
그 이후에, sum을 print하면 문제가 모두 해결이 됩니다!
채점 결과
원턴 킬 했다
