[코딩테스트] 백준 11497번: 통나무 건너뛰기

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

 

풀이 안보고 스스로 푼 문제. 이해한 문제 풀이는 다음과 같다

0번째 인덱스와 (n-1)인덱스도 인접한 것이므로 이 둘의 차이도 최소가 되게 놓아야한다는 것을 깨달았다

나머지 1번부터 n-2 인덱스사이에도 각 차이가 최소가 되게 작성해야하는 것을 생각했다.

그러다 깨달은 방법이 주어진 값을 작은 것부터 정렬한후, 짝수 인덱스는 왼쪽에, 홀수 인덱스는 큰 값부터 순서대로 나열해서 오른쪽에 놔두면 각 차이가 최소가 되게 놓을 수 있다는 것을 알게되었다.

 

예를 들면 예제에서 2번째 배열을 보면 [2,4,5,7,9]인데, 인덱스가 홀수인 값들만 순서대로 정렬하면 [2,5,9] 이고, 인덱스가 짝수인 값들은 큰것부터 나열하면 [7,4]이다.

위 배열을 합하면 [2,5,9,7,4]로 난이도가 4로 최소가 된다. 

그래서 먼저 인덱스가 홀수인 것들을 odd 리스트에 순서대로 넣고, 인덱스가 짝수인 것들은 even 리스트에 역순서로 넣는다

그것들의 합인 result 리스트를 만든다음, 0번 인덱스부터 각 차이 중 max값을 찾고 출력해주면 된다 

 

-정답풀이(내 풀이ㅎ):

 

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)