[백준(BOJ)] 22945 팀 빌딩 - 스위프트(Swift)

[Gold IV] 팀 빌딩 - 22945

문제 링크

성능 요약

메모리: 76296 KB, 시간: 44 ms

분류

두 포인터

문제 설명

개발자 N명이 팀 빌딩을 위해 한 줄로 서있다.

하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다.

개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다.

• (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)

예를 들어, 4명의 개발자가 존재할 때, 각 개발자의 능력치를 1 4 2 5라고 하자. 이때 능력치가 1인 개발자와 능력치가 5인 개발자가 한 팀을 이뤘다고 가정하자. 그러면 이 팀의 능력치는 2×min(1,5)= 2가 된다.

팀 빌딩에서 나올 수 있는 팀 중 능력치의 최대값을 구해보자.

입력

첫 번째 줄에 개발자의 수 N이 주어진다.

두 번째 줄에는 N의 개발자의 각 능력치 xi가 공백으로 구분되어 주어진다.

출력

팀의 능력치 최댓값을 출력한다.

 

풀이

개발자 사이에 존재하는 개발자의 수를 조정하기보단, min의 값을 최대한 크게 하는 전략을 통해 최대값을 저장하였습니다.

양 끝에서 시작하여 값들을 저장하고, 양 옆 중 작은 부분을 이동시켰습니다. 

그러다 양 끝 사이에 값이 없다면 종료시킵니다.

let N = Int(readLine()!)!
let dev = readLine()!.split(separator: " ").map { Int($0)! }
var (left, right, capacity) = (0, dev.count - 1, 0)

while left < right {
    
    capacity = max(capacity, (right - left - 1) * (min(dev[left], dev[right])))
    
    if dev[left] <= dev[right] { //왼쪽 능력치가 더 낮거나 같을 때
        left += 1
        } else {    // 오른쪽 능력치가 더 낮을 때
            right -= 1
    }
    
}

print(capacity)