1253. [Python] 좋다

1. 문제

 

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

1253번: 좋다

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 256MB
• 투 포인터
• 이분탐색

 

3. 파이썬 코드

 

N = int(input())
# 이분 탐색
num_list = list(map(int,input().split()))
# 정렬
num_list.sort()
cnt = 0

for i in range(N):
    # 시작
    start = 0
    # 끝
    end = N-1
    # 이분 탐색 진행
    while start < end:
        # 시작 인덱스와 끝 인덱스 합이 i 인덱스와 같은 경우
        if num_list[start] + num_list[end] == num_list[i]:
            # 서로 다른 두 수이기 때문에 i 면 안됨
            if start != i and end == i:
                # end 값이 i 랑 같으면 end -1
                end -=1
            elif start == i and end != i:
                # start 값이 i 랑 같으면 start +1
                start += 1
            # 외의 경우 서로 다른 두수이므로 cnt 증가 후 탈출
            else:
                cnt += 1
                break
        # 값의 합이 큰 경우 end -1
        elif num_list[start] + num_list[end] > num_list[i]:
            end -= 1
        # 값의 합이 작은 경우 start +1
        elif num_list[start] + num_list[end] < num_list[i]:
            start += 1

print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 이분 탐색과 투 포인터를 활용한 문제로 이분 탐색이라기 보다는 투 포인터에 가까운 문제라고 생각한다.
• 기존의 이분 탐색을 진행하되 1 ~ N-1 인덱스까지 반복문을 진행하며 i 번째 값이 이분탐색으로 지정한 시작과 끝 인덱스 num_list 값의 합과 큰지 작은지 판단하는 문제이다.
• 특이한 점은 내가 원하는 값을 찾았을 경우 한번 더 조건을 걸어줘야 한다.
• "서로 다른 두 수" 이기 때문에 i 번 인덱스 위치에 start, end 값이 위치하면 안된다.
• start 값이 i 번 인덱스 위치인 경우 start 를 +1 해주고 end 값이 i 번 인덱스인 경우 end 값을 -1 해줘야 한다.
• 외의 경우는 투 포인터를 진행하면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 투 포인터
• 이분탐색