[백준/Swift] 2230 : 수 고르기 문제 뿌수기!!

 

 

• BOJ_2230.swift

• 2230 : 수 고르기/ 문제 소개
• 풀이 과정
• 코드 구현

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

2230번: 수 고르기

2230 : 수 고르기 / 문제 소개

 

N개의 정수로 이루어진 수열이 있다. 두 수를 고를 수 있는데 같은 수를 고를 수 있다.

두 수간 차이가 M이상이면서 제일 작은 경우를 구하시오.

풀이 과정

 

문제를 읽고 투 포인터를 통해 "두 수"를 선택하고 차이를 제일 작은 경우를 선정했다.

물론 수열을 작->큰 순으로 sort를 했다.

 

여기서 내 고민은 "투 포인터(left,right)의 위치를 어디에 둘 것인가?" 였다.

음 

수열을 list라고 했을 때

투 포인터의 첫 선택은 left = 0(수열의 가장 왼쪽index) right=list.count-1(수열의 가장 오른쪽 index)로 두는 선택이었다.

var sum = list[right] - list[left] 으로 하고

sum이 주어진 M(두 수간 차이)보다 큰 경우는 right -= 1 , 작은 경우는 left += 1로 설정했다.

하지만 반례가 나타났다

5 6

1

2

3

4

11

 

이 경우에 left = 0, right = 4일때 sum ==12이므로 right -= 1 을 하게되면

아무리 해도 6이상의 차이 만들 수 없었다. right를 다시 +=1 해야 하는 상황이 왔는데... 초기에 left = 0, right = list.count - 1 로 두는 방법이 옳지 못한 방식임을 알게 되었다.

---

left = 0, right = 0으로 두었을 때는 이 문제를 해결 할 수 있었다.

코드 구현

 

import Foundation

func BOJ_2230()
{
    let NM   = readLine()!.split(separator:" ").map{Int(String($0))!}
    let n    = NM[0], m = NM[1]
    var list = [Int]()
    var ans  = 2000000001
    for _ in 0..<n
    {
        list.append(Int(readLine()!)!)
    }
    list.sort()
    var left = 0 , right = 0
    while left < n && right < n
    {
        let diff = list[right]-list[left]
        if diff < m
        {
            right += 1
        }
        else if diff >= m
        {
            left += 1
            ans = min(diff,ans)
        }
    }
    print(ans)
}

 

visit my github