[홀로 하는 코딩 공부] 용액 (Python)

 

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/2467 

2467번: 용액

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에 이 문제를 보자마자 용액의 특성 값을 담고 있는 배열의 모든 원소들에 절대값을 적용한채로 오름차순으로 정렬한 다음, 앞 뒤로 더해서 제일 작은 값을 찾아가면 된다고 생각했다. 그러면 총 세 단계가 된다.

 STEP1. 배열의 모든 원소들에 절대값을 적용한다.(원소에 음수도 포함되어 있기 때문이다)

 STEP2. 오름차순으로 정렬한다.

 STEP3. 첫 번째 인덱스부터 앞뒤로 더해서 제일 작은 값을 찾는다.

▶ 하지만 정답 비율이 낮은 거답게 그렇게 간단하고 쉬운 문제가 아니다. 문제의 조건 중에 " N은 2 이상 100,000 이하의 정수이다. " 라고 적혀있다. 즉, 위 처럼 푼다면 효율성 점수를 많이 깎아먹는 것이다. 고로, 다른 방법을 생각해야 한다.

...

▶ [-99, -2, -1, 4, 98]을 절대값을 적용한채로 오름차순 정렬하면 [-99, 98, 4, -2, -1]가 된다. 여기서 오름차순 정렬을 각각의 인덱스에 해당하는 값을 타겟으로 정해서 하나씩 배열에서 본인의 위치를 찾는 방법인 LIS 방법을 적용하면 되겠다라는 생각이 들었다.

▶ LIS 방법을 적용한 코드는 아래와 같으며, 코드 설명을 잠시 하려 한다. 

• mem_arr에는 용액의 특성값을 나타내는 배열의 원소가 절대값이 적용된채로(절대값이 아니어도 부호만 모두 통일되면 됨) 오름차순 정렬이 완료된 배열이다.
• answer에서 첫번째 배열에는 "특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값"을 저장하고, 두번째 배열에는 두 용액의 특성값 차를 저장할 것이다. 즉, answer값은 로직을 통해 계속 업데이트 될 것이다. 그러므로 초기 값은 모든 값들을 다 포함하는 값들이 되야한다. 배열의 원소는 모두 -1,000,000,000 이상 1,000,000,000 이하 라는 조건이 있다. 그러므로 두 용액의 특성값 차는 나올 수 없는 값인 " 1,000,000,000+1"의 두배가 된다.
• 처음에 mem_arr의 제일 끝 값하고 cur_n에 -1을 곱해준 값을 비교한다. mem_arr의 제일 끝 값은 mem_arr내에서 제일 작은 값이다. 그리고 cur_n에 -1을 곱해줘야 하는 이유가 있다.
  • 여기서 키포인트는 배열 자체는 이미 오름차순으로 정렬된채로 주어진다. 그러므로 부호가 통일 된채로 비교가 진행되어야하기 때문이다.
  • 필자는 절대값이 적용된 값들을 내림차순으로 정렬하기로 결정하였다. 오름차순 정렬되어있는 -99, -2가 mem_arr에는 -99, -2로 정렬되어야한다. 두 값에 절대값을 취하게 되면 -2, -99로 정렬되게 된다. 
• binary_search 함수는 주어진 값이 들어갈 위치의 인덱스를 리턴한다. 여기서 binary_search에도 cur_n에 -1을 곱해준 값이 들어가게된다. binary_search는 이름처럼 단순 이분탐색을 로직으로 구현한 함수이다.
• left_n은 cur_n이 배열에 들어갈 위치의 왼쪽 값이고, right_n은 cur_n이 배열에 들어갈 위치의 오른쪽 값이다. 여기서 left_n하고 right_n을 정의한 이유는, 두 값중 어느것이 cur_n하고 결합되었을 때, 0하고 가까운 값을 만들어내는 지 모르기때문에 대소비교를 하기 위함이다. 0하고 가까운 값을 만들어내는 값이 next_n에 들어가게된다. 그 다음은 마지막으로 직전까지 최선의 답이라고 생각했던 answer에 있는 값하고 비교하여 더 최적의 답이 도출된다면 answer를 업데이트하는 과정을 거치게 된다. 

import sys
input = sys.stdin.readline

n = int(input())
n_list = list(map(int, input().split()))

MIN_VALUE = -1000000001
MAX_VALUE = 1000000001
mem_arr = [n_list[0]]
answer = [[MIN_VALUE, n_list[0]], MAX_VALUE*2]

def binary_search(arr, tgt):
    left, right = 0, len(arr)-1

    while left < right:
        mid = (left+right) // 2
        if arr[mid] < tgt:
            left = mid + 1
        else:
            right = mid

    return right

for cur_n in n_list[1:]:
    if mem_arr[-1] < (cur_n*-1):
        dif = mem_arr[-1]+cur_n
        if abs(answer[1]) > abs(dif):
            answer = [[mem_arr[-1], cur_n], dif]
        mem_arr.append(cur_n)
    else:
        idx = binary_search(mem_arr, (cur_n*-1))
        next_n = 0
        left_n = mem_arr[idx-1]
        right_n = mem_arr[idx]
        if abs(left_n+cur_n) < abs(right_n+cur_n):
            dif = left_n + cur_n
            next_n = left_n
        else:
            dif = right_n + cur_n
            next_n = right_n
        if abs(answer[1]) > abs(dif):
            answer = [[next_n, cur_n], dif]
print(*answer[0])

 

 

 

 

▶ LIS에서 조금 더 변형된 문제이기에 LIS를 알고있다면 풀릴 수 있는 문제 인 것 같다. 

▶ 혼자 풀었지만 시간이 꽤 소요되었던 것 같다. 시간 단축을 위해 LIS에 더 익숙해져야 할 것 같다. 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.