[그리디/백준] 11497번: 통나무 건너뛰기

-문제: https://www.acmicpc.net/problem/11497

 

-정답풀이: 

시작과 끝 통나무도 연결되어있으니까 이 둘의 차이도 최소가 되어야 한다고 생각해 주어진 값을 오름차순으로 정렬한 다음 

0번 인덱스는 0번에, 1번 인덱스는 n-1에 넣으면 될 것 같다고 생각했다. 

정렬한 상태에서 왼쪽 두개를 꺼내면 되므로, data.pop을 사용했다. 

n이 짝수면 n//2개로 충분한데, n이 홀수면 data안에 원소 하나가 남으므로 그거는 중심에 넣어준다 

 

위와 같은 과정으로 만든 result 리스트 각 원소의 차이 중 최댓값을 출력하면된다. 

0과 n-1인덱스 값의 차이는 이미 최소이므로 비교하지 않아도 된다 

t=int(input())

for _ in range(t):
    n=int(input())
    data=list(map(int,input().split()))
    result=[0]*n
    data.sort()
    for i in range(n//2):
        a=data.pop(0)
        b=data.pop(0)
        result[i]=a
        result[n-1-i]=b
    if len(data):
        result[n//2]=data.pop(0)
    answer=0
    for i in range(1,n):
        answer=max(answer,abs(result[i]-result[i-1]))
    print(answer)

 

-2022.02 풀이 

증가하는 부분 수열, 감소하는 부분수열을 합친 문제다 

t=int(input())

for _ in range(t):
    n=int(input())
    s=sorted(list(map(int,input().split())))
    odd=[]
    even=[]
    for i in range(n):
        if i%2 ==0:
            even.append(s[i])
    for i in range(n-1,-1,-1):
        if i%2==1:
            odd.append(s[i])    
    result=even+odd
    ans=0
    for i in range(1,n):
        ans=max(ans,abs(result[i]-result[i-1]))
    print(ans)