백준 1253번: 좋다 (G4) - Swift 풀이

 

문제 설명

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

• N개의 수 중, 어떤 수를 다른 수 두 개의 합으로 나타낼 수 있으면 그 수는 좋다. 이때 좋은 수가 몇 개인지 출력하는 문제.
  •  ex) 1,2,3,4,5,6,7,8,9,10 중 좋은 수는 3,4,5,6,7,8,9,10이다. 3 = 1 + 2, 4 = 1 + 3, ...
• 수의 위치가 다르면 값이 같아도 다른 수로 본다.

입력: 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력: 개수를 첫 번째 줄에 출력한다.

 

풀이 과정

투 포인터 알고리즘을 사용했다.

투 포인터 알고리즘이란 주로 정렬된 배열의 연속적인 구간에서 합이나 원소를 찾아낼 때 유용한 알고리즘으로, 두 포인터가 간격을 좁혀가거나 넓혀가면서 탐색하는 방법이다.

 

두 원소의 값을 확인하는 데에 완전탐색을 사용한다면 O(N^2)의 시간복잡도를 가지지만,

투 포인터를 사용한다면 O(N)만큼의 시간복잡도가 발생해서 보다 빠르게 해결할 수 있다.

let N = Int(readLine()!)!

var Ai: [Int] = []
Ai = readLine()!.split(separator: " ").map { Int($0)! }

// 정렬
Ai.sort()

var answer = 0

// Ai 배열 순회
for n in 0..<N {
    let target = Ai[n]
    
    var left = 0
    var right = N-1
    
    // left와 right가 교차되기 전까지 반복
    while left < right {
    	// left나 right에 위치한 수가 자기자신이라면
        if right == n {
            // 포인터 위치는 이동하되 continue를 통해 answer를 세지 않고 넘어간다
            right -= 1
            continue
        } else if left == n {
            left += 1
            continue
        }
        
        // left와 right가 가리키고 있는 값을 더한다
        let sum = Ai[left] + Ai[right]
        // target과의 대소비교
        if sum > target {
            // sum이 더 크면 right가 왼쪽으로 한 칸 이동
            right -= 1
        } else if sum == target {
            // 같다면 카운트
            answer += 1
            break
        } else {
            // sum이 더 작으면 left가 오른쪽으로 한 칸 이동
            left += 1
        }
    }
}

print(answer)

 

우선 배열을 정렬해서 배열의 왼쪽 부분에는 작은 값, 오른쪽엔 큰 값이 위치하게 한다.

그 후, left와 right 변수로 배열의 처음과 끝에 포인터를 두고 두 포인터의 간격을 좁히며 두 포인터가 가리키는 값들의 합을 확인했다.

이 합이 Ai[n]과 같으면 answer의 카운트를 1 증가시킨다.

 

단, left와 right를 설정할 때 n을 고려하지 않았으므로 1) Ai[n]과 Ai[left] 또는 2) Ai[n]과 Ai[right]가 같은 경우(= 같은 위치를 가리키고 있는 상태)가 생긴다. 이때는 합과 Ai[n]이 같더라도 answer가 카운트 되면 안 된다.

while문 상단에서 이 경우를 확인하여 left 또는 right의 위치는 이동시키되, continue를 통해 패스하도록 작성했다. 이 점을 놓쳐서 계속 틀림...

 

Python이랑 Swift 왔다갔다 하려니 문법이 엄청 헷갈려요ㅜ
모든 기업이 코테 언어를 통일해 주거나 제한을 걸지 않아 준다면 얼마나 좋을까!