초이의 끄적끄적

프로그래머스 - 정렬

# K번째수 (Level 1)

def solution(array, commands):
    answer = []
    for i,j,k in commands:
        answer.append(list(sorted(array[i-1:j]))[k-1])
    return answer

# 가장 큰 수 (Level 2)

• 문자열로 정렬해서 합친다
• numbers의 원소는 1,000이하 ->세자리까지 확인한다 ->  x*3
• Point. 문자열 비교연산 -> 사전과 같은 방식
  • ex) 첫번째 인덱스인 666[0]인 6과 101010[0]인 1과 222[0]인 2를 ascii숫자로 바꿔서 비교합니다. 물론 같으면, 다음 인덱스도 비교합니다. 비교한 결과 [6, 2, 10]의 순으로 정렬됩니다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

# H-Index (Level 2)

• Point. enumerate를 사용해서 반복문의 index번호 가져오기
• H-지수 구하는 방법(참고)

def solution(citations):
    answer = 0
    for i, p in enumerate(sorted(citations,reverse=True)):
        if i+1 <= p:
            answer+=1
    return answer

# 11066 파일 합치기 (골드3)

• 고난이도 문제 핵심 DP식 구하기

def process():
    N, A = int(input()), [0]+list(map(int, input().split()))
    # S[i]는 1번부터 i번까지의 누적합
    S = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        S[i] = S[i-1] + A[i]

    # DP[i][j] : i에서 j까지 합하는데 필요한 최소 비용
    # DP[i][k] + DP[k+1][j] + sum(A[i]~A[j])
    DP = [[0 for i in range(N+1)] for _ in range(N+1)]
    for i in range(2, N+1): # 부분파일의 길이
        for j in range(1, N+2-i): # 시작점
            DP[j][j+i-1] = min([DP[j][j+k] + DP[j+k+1][j+i-1]
                                for k in range(i-1)]) + (S[j+i-1] - S[j-1])
    print(DP[1][N])


for _ in range(int(input())):
    process()