[백준] 1253 (좋다)

1253

1253번: 좋다

👾접근

주어지는 수의 범위가 절댓값이 1,000,000,000 이하인 정수인 점 과 정수 중복도 가능하다는 점을 알고 있어야 한다..(이거 고려못하고 중복없는 양의 정수로 풀어서 헤맸다)

즉, 체크되는 수를 제외한 두 수의 합이 체크되는 수와 같기만 하면 된다. 

좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn) 이 되어야 함 => 정렬과 투포인터 사용해보기 

리스트를 정렬한 후 좋은 수 여부를 체크할 위치를 지정하고 
해당 인덱스를 제외하고 양쪽 끝 인덱스로 s 와  e 투 포인터를 지정해준다. 

투 포인터 이동 원칙 
- lst[s] + lst[e]  == check ; good += 1 ; break
- lst[s] + lst[e] > check : e -= 1
- lst[s] + lst[e] < check : s += 1

풀이 

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))

lst.sort()
good = 0 

for i in range(N):
    # 합 확인할 정수 지정
    check = lst[i]
    print()
    print(f'[ check : {check} , i : {i} ]')
    s = 0 #시작 포인터
    e = N-1 #종료 포인터
    while s < e : 
        if lst[s] + lst[e] == check : 
            print(f'sum:{lst[s] + lst[e]}  ({s},{e})', end= " → ")
            if s != i and e !=i:
                print(f'탈출 성공!!')
                good += 1
                break
            elif s == i : # 시작 포인터가 check 인 경우 예외처리
                print(f'탈출 실패 (s == i) : s ++')
                s+= 1
            elif e == i : # 종료 포인터가 check 인 경우 예외처리
                print(f'탈출 실패 (e == i) : e --')
                e -= 1    
        elif lst[s] + lst[e] < check : 
            print(f'sum:{lst[s] + lst[e]}  ({s},{e})  s ++')
            s+=1
        else: 
            print(f'sum:{lst[s] + lst[e]}  ({s},{e}) e --')
            e -= 1
print(good)

## 입출력 예

4 
[0, 1, 2, 3]

[ check : 0 , i : 0 ]
sum:3  (0,3) e --
sum:2  (0,2) e --
sum:1  (0,1) e --

[ check : 1 , i : 1 ]
sum:3  (0,3) e --
sum:2  (0,2) e --
sum:1  (0,1) → 탈출 실패 (e == i) : e --

[ check : 2 , i : 2 ]
sum:3  (0,3) e --
sum:2  (0,2) → 탈출 실패 (e == i) : e --
sum:1  (0,1)  s ++

[ check : 3 , i : 3 ]
sum:3  (0,3) → 탈출 실패 (e == i) : e --
sum:2  (0,2)  s ++
sum:3  (1,2) → 탈출 성공!!

이 문제는 반례를 봐야지만 문제 해결법이 보이는 거 같다... 
누군가 올려놓은 반례들.. 

2

0 0

out : 0

3

0 3 3

out : 2

2

0 1

out : 0

3

0 0 0

out : 3

4

0 1 2 3

out : 1

3

0 -5 5

out : 1