BAEKJOON ONLINE JUDGE - 1253. 좋다

BOJ-1253. 좋다

1. 알고리즘 분류

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵
• 투 포인터

2. 사용언어

• Python

3. 풀이(1차)

1) 접근

• 범위가 1 ≤ N ≤ 2,000 로 비교적 작으나 한 경우에 대해 모든 경우의 수를 찾을 경우 시간 초과 예상
• 투 포인터로 접근

2) 설계

• 투 포인터를 사용하기 위해 먼저 리스트를 정렬한다.
• 목표 인덱스를 설정하고 그 전에 있는 값들의 조합을 통해 ‘좋은 수’를 찾는다.
• 찾으면 반복문을 종료시키고 결과값과 목표 인덱스를 1 증가시킨다.
• 반복문 시작때 결과값을 다른 곳에 저장해두고 반복문 끝에 결과값과 비교했을 때 다르다면 반복문을 종료시킨다.
• 오답

3) 코드

n = int(input())
arr = sorted(list(map(int,input().split())))
visited=[0]*n
end=2
good=0
while end<n:
    for s in range(end):
        tmp=good
        idx=s+1
        while idx<end:
            value = arr[s]+arr[idx]
            if value==arr[end] and not visited[end]:
                visited[end]=1
                good+=1
                idx=end
                break
            else:
                idx+=1
        if tmp!=good:
            break
    end+=1
print(good)

4. 풀이(2차)

1) 개선

• |Ai| ≤ 1,000,000,000, Ai는 정수 범위로 인해 리스트 안에 0 이 존재할 수 있음
• 그래서 좋은 수를 찾을 때 자기 자신을 넣어서 사용하는 경우가 발생할 수 있음
• ex) 0 + target

2) 설계

• start와 end 가 타겟값의 인덱스와 다른지를 확인하는 코드 추가

3) 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int,input().split())))
good = 0
for i in range(n):
    target = arr[i]
    start=0
    end=n-1
    while start<end:
        if arr[start]+arr[end]==target:
            if start!=i and end!=i:
                good+=1
                break
            elif start==i:
                start+=1
            else:
                end-=1
        elif arr[start]+arr[end]<target:
            start+=1
        else:
            end-=1
print(good)