[백준/Swift] 2470 : 두 용액 문제 뿌수기!!

 

 

• BOJ_2470.swift

• 2470 : 두 용액/ 문제 소개
• 풀이 과정
• 코드 구현

https://www.acmicpc.net/problem/2470

2470번: 두 용액

2470 : 두 용액 / 문제 소개

 

간단하게 문제를 소개하자면

연구소에는 많은 산성 용액과 알칼리성 용액을 보유하고 있는데

용액별로 특성값이 존재합니다. 

산성 용액 특성값의 경우 1 ~ 1,000,000,000

알칼리성 용액 특성값의 경우 -1,000,000,000 ~ -1

로 존재합니다.

산성 용액 + 산성 용액, 알칼리성 용액 + 알칼리성 용액, 산성 용액 + 알칼리성 용액  

이렇게 두 용액을 혼합했을 때 혼합된 용액의 특성값은 각 용액의 특성값의 합으로 결정되는데 특성값이 0에 가장 가까운 용액을 만들어야 합니다.

풀이 과정

 

최근에 빗물이라는 문제를 풀면서 투 포인터의 개념에  대해 알게 되었고 연습하기 위해 이 문제를 풀게되었습니다.(알고리즘 만든 분들 대단해요 진짜 어쩜 이런 개념을..)

 

투 포인터란 말 그대로 두개의 포인터를 의미합니다.

조건에 따라 포인터를 움직이면서 문제를 해결해 나갑니다.

---

두 포인터 left, right의 위치를 list의 처음부터 두고 right를 증가, 혹은  left를 증가 시키려고 하니 답이 안나오더군요.. 그래서 문제에서 주어진 용액 리스트를 작은 값부터 소팅을 했습니다.

그리고 left는 용액 리스트의 index 0, right는 용액 리스트의 index.count - 1 로 정하고 양 끝에 위치한 두 포인터를 가운데로 모이도록 할 수록 더 쉬운 답을 찾을 수 있겠다는 생각을 했습니다.

이때 조건을 설정해야 했는데. 조건 경우를 3가지로 정했습니다.

 

var sum = list[left]+list[right] // 두 용액의 합을 저장하는 변수를 선언했을 때!!

• sum > 0 인 경우

Left를 ++ 시키면 더 좋은 결과를 얻을수 있을 것입니다.

• sum < 0 인 경우

이 경우에는 right를 -- 시키면 그림처럼 값이 작을 때 최적의 합을 찾을 경우를 탐색할 수 있습니다.

 

그리고 답 과 해당 left,right인덱스도 저장했는데 이때 sum이 <0 이어도 "0에 근접한 값"을 찾는 것이기에 abs(sum) 절대값함수를 통해 ans가 크면 sum을 ans에 저장하는 방식으로 정답을 체크해 나갔습니다.

• sum == 0인 경우

이 경우는 무조건 답이므로 바로 해당 left 인덱스의 값, right인덱스의 값을 출력후 메인 함수를 종료했습니다.

---

초기 sum의 값은 가장 최악의 경우 -1 , 1,000,000,000 또는 반대 로 생각하고 sum = 1,000,000,001로 잡았는데

46퍼센트에서 틀렸습니다.

문제를 다시 읽어보니 각각의 용액은 모두!! 1,000,000,000 이 될수도 있다는 조건을 보지 못했습니다. (46%에서 틀렸습니다)

그래서 초기 sum을 2,000,000,000으로 하니 바로 답을 맞을 수 있었습니다.

코드 구현

 

import Foundation
/*
 문제 풀 때 초기 sum값 주의.
 */
func BOJ_2470()
{
    let n = Int(readLine()!)!
    var list = readLine()!.split(separator:" ").map{Int(String($0))!}
    list.sort(by: <)
    
    // 투 포인터
    var left = 0 , right = list.count - 1
    var sum  = 2000000001
    
    //(sum과 left, right 인덱스 저장)
    var ans  : (sum:Int,l:Int,r:Int) = (sum,left,right)
    while left<right
    {
        sum = list[left]+list[right]
        if sum > 0
        {
            if ans.sum > sum
            {
                ans = (sum,left,right)
            }
            right -= 1
        }
        else if sum < 0
        {
            if ans.sum > abs(sum)
            {
                ans = (abs(sum),left,right)
            }
            left += 1
        }
        else
        {
            print("\(list[left]) \(list[right])")
            return
        }
    }
    print("\(list[ans.l]) \(list[ans.r])")
}
BOJ_2470()

 

visit my github