[백준/Swift] 1253 : 좋다 문제 풀이와 2개의 반례

 

 

• BOJ_1253.swift

• 1253 : 좋다/ 문제 소개                            
• 풀이 과정
• 코드 구현

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

1253번: 좋다

1253 : 좋다 / 문제 소개

 

N개의 수 중에서 어떤 수가 다른 수 두개 의 합으로 나타낼 수 있다면 그 수를 좋다~라고 한다.

N이 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하는 문제!!

풀이 과정

 

10

1 2 3 4 5 6 7 8 9 10 // list에 저장

이 input으로 주어졌을 때 아!? 투 포인터?!를 떠올렸고 

N개의 수 중에서 좋다 갯수를 파악하는 것임으로 완전 탐색으로 숫자들의 탐색 떠올렸습니다.

 

left = 0, right = n - 1 로 잡고 만약 list[left] + list[right] == 특정 index 일 경우 답을 체크해 나갔습니다.

---

하지만 이 과정에서 생각하지 못한 경우들이 있었습니다.

2

0 0

ans = 0 wrong = 2

 

3

0 0 3

ans = 0

---

2

0 0의 경우

list[0] = 0을 만들기 위해서는 다른 두개의 수가 필요한데 남은 수는 right 한개밖에없는데 left== index 0인 list[0]을 가리키고 있음으로 만들수있다고 체크하는 바람에 틀렸습니다.

그래서 list의 원소를 탐색하는 index == left or right일 경우에는 sum을 할 수 없게 되는 경우입니다. 그것을 조건으로 달아야 합니다.

코드 구현

 

import Foundation
func BOJ_1253()
{
    let n = Int(readLine()!)!
    let list = readLine()!.split(separator:" ").map{Int(String($0))!}.sorted()
    var ans = 0

    for i in 0..<n
    {
        var left = 0, right = n - 1 , sum = 0
        while left < right
        {
            sum = list[left] + list[right]
            if sum > list[i]
            {
                right -= 1
            }
            else if sum < list[i]
            {
                left += 1
            }else if sum == list[i]
            {
                if i != left && i != right
                {
                    ans += 1
                    break
                }
                else if i == right
                {
                    right -= 1
                }
                else
                {
                    left += 1
                }
            }
        }
    }
    print(ans)
}
BOJ_1253()

 

visit my github