[백준/Swift] 3273 : 두 수의 합

 

 

• BOJ_3273.swift

• 3273 : 두 수의 합/ 문제 소개                                    
• 풀이 과정
• 코드 구현

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

3273번: 두 수의 합

 

3273 : 두 수의 합 / 문제 소개

 

서로다른!!! n개의 양의 정수로 이루어진 수열 중에서 ai + aj = x(문제에서 주어진 자연수 x)를 만족하는 (ai,aj)쌍의 수를 구하는게 문제이다.

풀이 과정

 

처음에 투 포인터 left, right 를 이용해서 주어진 수열의 index == 0부터 탐색해나갔다. (left, right로 두개의 index를 고르면 그 index의 value를 더한게 x인지를 파악하는 과정!!)

 

이때 left보다 right가 무조건 큼으로 left = righ + 1로 두면서 탐색을 진행해나갔다.

for left in 0..<n
    {
        var right = left + 1, sum = 0
        while sum<x && right < n
        {
            sum = list[left] + list[right]
            right += 1
        }
        if sum == x
        {
            cnt += 1
        }
    }

뭐가문제일까? 답은 맞는데.......

계속 시간초과가 났다.

곰곰이 생각을 했는데....

이렇게 완전 탐색으로 탐색해나가면 안되나? 생각하던 찰나..

이 코드의 시간 복잡도는 O(N^2)라는 것임을 깨닫았고 그래서 시간초과가 됬음을 알게되었다.

 

양쪽에서 만나는 방법

이 이모티콘 느낌으로다가 코드를 새로 구현했다.

 

이전에 위에서 구현한 left = 0, right = left + 1로 완전 탐색을 해나가는 방식이 아닌

O(N)으로 코드를 짤 수있는 방법이 생각났다.

우선 수열을 sort한 후에 left는 수열의 index = 0, right = 수열.count - 1을 통해 

수열[left] + 수열[right]가 x 보다 큰 경우 right을 줄이면서,

수열[left] + 수열[right]가 x와 같은 경우 count를 증가하고 right를 줄이면서,

수열[left] + 수열[right]가 x보다 작은 경우 left를 증가시키면서

left < right일 때까지 와일문을 돌림으로 시간초과를 해결했다.

코드 구현

 

import Foundation

func BOJ_3273()
{
    let n    = Int(readLine()!)!
    let list = readLine()!.split(separator:" ").map{Int(String($0))!}.sorted(by: <)
    let x    = Int(readLine()!)!
    var cnt = 0
    for left in 0..<n
    {
        var right = left + 1, sum = 0
        while sum<x && right < n
        {
            sum = list[left] + list[right]
            right += 1
        }
        if sum == x
        {
            cnt += 1
        }
    }
    print(cnt)
}
BOJ_3273()

 

visit my github