[Swift 알고리즘]백준 10819(차이를 최대로), 백준 16193(차이를 최대로 2) (그림있음)

 

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

10819번: 차이를 최대로

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

25323

16413

12669

65.395%

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 복사

6
20 1 15 8 4 10

예제 출력 1 복사

62

 

해결방법

처음 보자마자 모든 점들을 담은 x축 평면을 생각했다. 그 x축 평면에 평균값이 되는 점을 찍었다. 배열에 나열된 값과 평균값을 빼 다른 배열에 저장한다. 이 배열은 평균까지와의 거리다. 최대 거리의 직선을 긋는다는 생각을 해 보았을 때, ind가 n과 n+1는 평균을 지나는 (반대쪽에 있는 -> 평균과 뺀 값이 한쪽은 -(음수) 이고 한쪽은 +(양수))가 된다면 최댓값이 될 것이다.

 

그림으로 그리자면 다음과 같다.

 

이 값들은 임의로 받은 값들이고 정렬된 배열이다. 정렬된 배열을 통해 average라는 점을 추가하였다.

 

임의로 이렇게 높이를 주어서 표현한다고 해보자 그러면 우리가 구하고 싶은 값들은

 

distant값 들일 것이다. (distant값들은 높이를 제외하여 계산합니다. 설명을 위해 임의로 높이를 적었습니다.)

 

이걸 다시 분해하게 되면

 

아래와 같이 분해할 수 있다.

d1 = d(1 to average) + d(2 to average)이 된다. 마찬가지로 분해하게 된다면

 

이렇게 된다. 이걸 자세하게 본다면 1번과 6번의 경우 평균 까지의 거리를 한번만 사용하고 (첫점과 끝점), [2, 3, 4, 5]의 점들은 평균 까지의 거리를 2번 사용한다. 이것을 다시 최적화 한다면 평균까지의 거리가 제일 짧은 1번과 2번을 첫점과 끝점으로 배치하면 된다.

 

정렬된 arr은 [1, 6, 3, 4, 5, 2]이다.

이런식으로 배치하게 된다면 빨간색의 거리의 합은 최대가 된다.

 

 

만약 N이 홀수라면?

 

인풋 값들이 홀수 일 때 사진을 참고하면 쉽다.

InputArr = [ 1, 3, 4, 5, 6]

 

 

inputValue = [ -3 -4 -1 5 3] 라고 가정하자.

let mid = N / 2, inpuatValue[mid] 가 음수라면 다음과 같이 계산한다.

firstVal = inputValue[mid - 1]

lastVal = inputValue[mid]

resArr = [firstVal ? ? ? lastVal]

 

InputArr = [2, 3, 4, 5, 6]

 

 

inputValue = [-3 -4, 2, 1, 4]

let mid = N / 2, inpuatValue[mid] 가 양수라면 다음과 같이 계산한다.

firstVal = inputValue[mid]

lastVal = inputValue[mid + 1]

resArr = [firstVal ? ? ? lastVal]

 

 

func solaCee() {
    let inputN = Int(readLine()!)!
    let inputArr = readLine()!.split(separator: " ").map{Int($0)!}
    
    let averageVal = Double(inputArr.reduce(0, {$0 + $1})) / Double(inputArr.count)
    var targetArr:[[Double]] = Array(repeating: [], count: inputN) //[ind , 평균까지의 거리] 로 저장되는 targetArr
    var resArr = Array(repeating: 0, count: inputN) //값을 저장할 arr
    
    for i in 0..<inputN {
        targetArr[i] = [Double(i), (Double(inputArr[i]) - averageVal)] //[ind, 평균 - 현재 값]
    }
    targetArr.sort{$0[1] > $1[1]}
   
    let midInd:Int = inputN / 2 //중앙값을 통해서 계산...
    
    var flag = -1
    var fVal:[Double] = [] //처음에 저장할 값
    var eVal:[Double] = [] // 마지막에 저장할 값 -> 처음과 마지막 값은 평균까지의 거리가 한번만 쓰인다.
    if inputN % 2 == 1 { //들어오는 배열의 수가 홀수 일 때
        if targetArr[midInd][1] > 0 { //중앙값 양수
            //print("중앙값 양수")
            fVal = targetArr.remove(at: midInd - 1) // 양수
            //eVal = targetArr.remove(at: midInd - 1) // 양수
            eVal = targetArr.remove(at: midInd - 1) // 양수
            flag = 1
        }
        else { //중앙값 음수
            //print("중앙값 음수")
            fVal = targetArr.remove(at: midInd) // 음수
            //eVal = targetArr.remove(at: midInd + 1) // 음수
            eVal = targetArr.remove(at: midInd) // 음수
        }
    }
    else { //들어오는 배열의 수가 짝수 일 때
        fVal = targetArr.remove(at: midInd) // 음수
        //eVal = targetArr.remove(at: midInd - 1) // 양수
        eVal = targetArr.remove(at: midInd - 1) // 양수
    }
    //이거 최적화 가능한데 그냥 안했음. 이유는 코드가 더 가독성이 있어서
    resArr[0] = inputArr[Int(fVal[0])] //음수를 맨 앞에다
    resArr[inputN - 1] = inputArr[Int(eVal[0])] //양수를 맨 앞에
    var resInd = 1 //처음과 마지막 값은 resArr에 저장되어 있음.
    if flag == -1{ //음 양 음 양 ... 으로 진행할 때
        while targetArr.count >= 2 {
            let temp1 = targetArr.removeFirst() //양수
            let temp2 = targetArr.removeLast() // 음수
            resArr[resInd] = inputArr[Int(temp1[0])]
            resArr[resInd + 1] = inputArr[Int(temp2[0])]
            resInd += 2
        }
    }
    else if flag == 1{ //양 음 양 음... 으로 진행할 때
        while targetArr.count >= 2 {
            let temp1 = targetArr.removeLast() //음수
            let temp2 = targetArr.removeFirst() // 양수
            resArr[resInd] = inputArr[Int(temp1[0])]
            resArr[resInd + 1] = inputArr[Int(temp2[0])]
            resInd += 2
        }
    }
    if !targetArr.isEmpty { //만약 N이 홀수일 때는 값이 하나 남기 때문에 그 값을 resArr에 마지막 resInd에 넣는다. 이 인덱스는 N-2 이다.
        resArr[resInd] = inputArr[Int(targetArr[0][0])]
    }
    var sum = 0
    for i in 1..<resArr.count {
        sum += abs(resArr[i] - resArr[i - 1])
    }
    print(sum)
}
solaCee()

+

16193 시간초과 나와서 곰곰히 복기해봤는데 아무리 생각해도 n log n임 이론상 완벽한데 뭘 잘못한지 모르겠어서  chatGpt에게 물어봤다.

 

 

일단 미제사건이긴 한데, 아마 swift가 백준에서 느려서 그렇다는 말이 있으니까... 그럴수도... 코드를 더 최적화 해봐도 되겠다.