11497번:통나무 건너뛰기

18 Aug 2022 in PS on Ps

문제

코드

h_list=[]
epoch=int(input(""))
for i in range(epoch):
  N=int(input(""))
  h_list=list(map(int,input().split()))

  h_list.sort()
  first=[]
  second=[]
  cnt=0
  for i in h_list:
    if cnt%2==0:
      first.append(i)
    else:
      second.append(i)
    cnt+=1
  second=list(reversed(second))
  h_list=first+second
  max1=h_list[0]-h_list[1]
  for j in range(N):

    if j+1==N:
      result=h_list[j]-h_list[0]
    else:
      result=h_list[j]-h_list[j+1]
    if abs(result)>abs(max1):
      max1=abs(result)
  print(abs(max1))

풀이

greedy알고리즘으로 인접한 통나무와의 높이 차이가 최소가 되는 형식으로 정렬
배열에서 첫번째와 마지막을 기점으로 생각하여 최솟값 2개를 배치
양쪽 줄세우기 느낌으로 차례대로 높이가 작은 통나무를 배치
후기
깔끔하게 푼거 같아서 기분이 좋다.