수학과의 개발자 도전기

-문제: www.acmicpc.net/problem/15904

쉬운 문제인 줄 알고 풀었는데 계속 틀려서 뭐가 문제인지 몰랐던 문제다. 

-틀린풀이: 

주어진 문장에서 대문자인 것들만 뽑았을 때 그 값이 UCPC일 때 love를 출력하는 방식으로 생각했는데 

계속 틀린다고해서 무엇이 문제인지 몰라서 구글링을 했다 

-정답풀이:

주어진 문장에서 U,C,P,C가 있는지 순서대로 탐색하고, 있다면 해당 인덱스의 다음 인덱스부터 진행하면된다 

인덱스 슬라이싱을 이용하면 되는 문제라고 한다 

s=input()
check_list=['U','C','P','C']
i=0
for a in check_list:
    if a in s:
        i+=1
        s=s[s.index(a)+1:]
    else:
        print('I hate UCPC')
        break
if i==4:
    print('I love UCPC')

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

n개의 구간을 k개의 영역으로 나누면 된다고 생각했고, 각 위치의 차이를 이용하는 것이라고 생각했는데 

그 다음 구현을 어떻게 할지 몰랐던 문제다

-정답풀이:

기지국이 세션수보다 같거나 크면 모든 지점에 기지국 설치하면 되므로 0을 출력한다

먼저 세션 위치를 다 받아서 작은 것부터 정렬한다

sys.exit()를 빼고 돌렸더니 틀렸다. 

0이 출력되고 끝나야하므로 exit()를 선언해줘야 하는 것 같다

인접한 세션끼리의 거리차를 distance 리스트에 넣는다

거리차를 내림차순으로 정렬한 뒤 거리가 가장 긴 것부터 k-1개를 제거하고 남은 길이의 합을 구하면 된다

import sys
n=int(input())
k=int(input())
s=sorted(list(map(int,input().split())))

if k>=n:
    print(0)
    sys.exit()
    
distance=[]
for i in range(1,n):
    distance.append(s[i]-s[i-1])
    
distance.sort(reverse=True)
for _ in range(k-1):
    distance.pop(0)
print(sum(distance))

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

예제 2번이 19라서 헤맸던 문제. 사실 아직도 모르겠음

heapq를 이용해서 하면 되는 문제라서 어렵지 않았던 문제다

반정도 스스로 푼 문제 

-정답풀이:

import heapq
n,m=map(int,input().split())
s=list(map(int,input().split()))
s.sort()

for _ in range(m):
    a=heapq.heappop(s)
    b=heapq.heappop(s)
    c=a+b
    heapq.heappush(s,c)
    heapq.heappush(s,c)
print(sum(s))

-문제: 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)