Softeer 연습문제 연탄 배달의 시작

 

https://softeer.ai/practice/7626

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

---

• 문제 설명
  문제에서 산타는 거리가 가장 가까운 두 마을을 방문하기 때문에 두 수의 차가 가장 작은 수의 조합 개수를 출력하면 된다.

 

• 시간 초과 제출 코드
  

import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())
lst = list(map(int,input().split()))
combi = list(combinations(lst,2))

lst_sub = []
dict = {}
cnt = 0

for i in combi:
    dict[i] = i[1]-i[0]

for value in dict.values():
    if value == min(dict.values()):
        cnt+=1
    
print(cnt)

 

일단 조합을 이용해서 모든 두 수의 경우의 수를 뽑아내려고 했다. 근데 나중에 든 생각인데 어차피 인접한 두 수의 차만 구하면 되기 때문에 조합을 사용할 필요는 없었던 것 같다. 일단 조합으로 두 수의 조합을 뽑아 리스트를 만들고 딕셔너리를 이용해서 이 두 수의 조합을 Key, 두 수의 차를 Value로 만들었다. 그리고 조합의 Value값들을 돌면서 이 값들 중 최솟값과 같은 값들이 몇 개인지 세서 출력했다. 

위 코드로 테스트 케이스는 통과할 수 있었지만 시간초과로 인해 통과할 수 없었다. 아마 조합을 생성하는 과정에서 높은 시간 복잡도로 인해 시간초과가 발생한 것 같다.

 

• 최종 제출 코드

import sys

input = sys.stdin.readline

n = int(input())
lst = list(map(int,input().split()))

min_diff = float('inf')
cnt = 0

for i in range(n):
    for j in range(i+1,n):
        dif = abs(lst[i] - lst[j])
        if(dif < min_diff):
            min_diff = dif
            cnt = 1
        elif (dif == min_diff):
            cnt+=1
print(cnt)

 

이번에는 조합을 사용하는 대신 for문을 두번 써서 인접한 두 수의 차를 구했다. 초기에 float('inf')를 통해 무수히 큰 값을 설정하고 이 값을 인접한 두 수의 차와 비교하여 min_diff를 다시 set 하는 방식으로 진행했다. 만약 인접한 두 수의 차와 min_diff와 같으면 이 개수에 +1을 하여 최종 개수를 구해줬다.

---

• 마무리
  
  개인적으로 어떤 문제를 봤을 때 라이브러리를 써서 풀면 편할 것 같다는 생각이 드는데 이번 문제처럼 괜히 라이브러리를 썼다가 시간초과가 발생하는 문제가 생길 수도 있을 것 같다. 그 전에 기본적인 문법으로 충분히 풀릴 수 있는 문제가 더 많을 것이기 때문에 기본에 충실하는 것이 가장 중요한 것 같다.