[파이썬/Python] Softeer Lv.1 연탄 배달의 시작

숨·2024년 6월 28일

코테

알고리즘 문제 풀이

목록 보기

8/105

📌 문제 : Softeer Lv.1 연탄 배달의 시작

📌 문제 탐색하기

n : 마을의 수 (2 ≤ n ≤ 1,000)
locations: 각 마을의 위치 (1 ≤ locations ≤ 1,000,000)

✅ 입력 조건
1. 마을의 수 n 입력
2. n개의 마을 위치를 공백으로 입력
✅ 출력 조건
1. 가장 가까운 마을 간 거리를 가진 조합 개수 출력

마을의 수 n을 입력받고, n개의 마을 위치를 공백 기준으로 분리하여 리스트에 저장한다.

마을 간 거리의 초기값을 지정한다.

마을 위치 리스트를 for문으로 돌면서 마을 간 거리를 갱신하면서 최소 거리에 해당하는 마을 조합을 발견하면 count를 올려주는 방식으로 구현한다.

가능한 시간복잡도

for문으로 n번 반복 → $O(n)$

최종 시간복잡도
$O(n)$ 로 2 ≤ n ≤ 1,000 조건에서 제한 시간 내에 연산이 가능하다.

알고리즘 선택

for문을 돌며 비교 연산

📌 코드 설계하기

마을의 수 n 입력
n개의 마을 위치 입력 (오름차순 가정 가능)
마을들 사이의 거리 계산해 가장 가까운 거리 저장하고 계산하면서 갱신

📌 시도 회차 수정 사항

1회차

마을 간 거리의 초기값을 n으로 해서 마을 간 최소 거리가 n보다 큰 경우의 반례에 잘못된 답을 출력하게 되었다. 초기값을 입력된 마을 간 거리 중 최대값으로 지정하여 올바른 답을 얻을 수 있었다.

# 수정 전
min_distance = n
# 수정 후
min_distance = locations[-1] - locations[0]

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. 마을의 수 n 입력
n = int(input())

# 2. n개의 마을 위치 입력 (오름차순 가정 가능)
locations = list(map(int, input().split()))

# 3. 마을들 사이의 거리 계산해 가장 가까운 거리 저장하고 계산하면서 갱신
min_distance = locations[-1] - locations[0]
count = 0

for i in range(1, n):
    temp = locations[i] - locations[i-1]

    if temp == min_distance:
        count += 1    
        
    elif temp < min_distance:
        min_distance = temp
        count = 1

# 4. 산타가 처음 방문할 가능성 있는 서로 다른 두 마을 조합의 수 출력
print(count)