[BOJ:1253] 좋다 #파이썬 #백준

	백준 문제풀이		python
			No. 1253 좋다, 좋은 수 구하기

 

 

#파이썬 #백준 #문제풀이 #1253 좋다, 좋은 수 구하기

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

1253번: 좋다

 

예제 입력

10
1 2 3 4 5 6 7 8 9 10

 

예제 출력

8

 

힌트

3,4,5,6,7,8,9,10은 좋다.

 

이번 글에서는 투 포인터로 구현하는데 중점을 둔다.

 

 

---

// 알고리즘

가장 중요한 목적이 무엇인지?

두 개의 합으로 나타낼 수 있다는 게 무엇인지 알아본다.

N개의 수가 주어지고,  A+B = C일 것이다.

애초에 배열을 만들때, 쌍으로 만들어 버리면 안되는지?

 

10
1 2 3 4 5 6 7 8 9 10

라는 배열이 들어왔을 때, 어떤 수는, 서로 더해서 원하는 수의 크기를 넘지 못할 것이다. 그니까 항상 작다.

따라서 sort로 진행하고, 어차피 좋은 수를 만들 수 있는 것은 한정적이다. 한 번만 만족하면, 좋은 수를 만족한다.

따라서 좋은 수를 만족하면 더 이상 계산하지 않고 pass하면 된다.

 

애초에 그렇다면...! hash를 사용하면 바로바로 수를 찾을 수 있지 않을까?

 

배열에 배열을 저장해버리자. 숫자의 개수를 저장해버리는 것이다.

 

 

 

 

 

 

왜 이런 방법을 선택했는지?

 

---

// 계획하기

	함수명	설명
1.
2.
3.

 

---

// 구현하기

-> How?

어떻게 구현?

투포인터를 이용하여 반복문 하나로 해결한다.

->Why?

왜 이런 방법을?

 

시간복잡도를 고려해서 log N 의 속도가 필요하다.

---

// 수정하기

import sys
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))

remainder = [0]*(max(numbers)+1)
temp = 0
cnt = 0

for i in numbers:
    remainder[i] += 1

print(remainder)

for i in numbers:
    for j in range(i+1,len(numbers)):
        if remainder[i - numbers[j]]!=0:
            cnt+=1
            break

print(cnt)

메모리 초과 오류

아무래도 hash함수를 사용해서  1,000,000,000라는 어마무시한 배열 크기 때문인거 같다.

 

일단 배열 크기를 보았을때, nlogn도 부적합하다. 따라서 n의 시간복잡도를 가지는 방법이 필요하다.

시작 인덱스와 종료 인덱스를 사용해 문제를 접근한다.

 

이를 투포인터 접근이라고 한다.

 

 

 

 

 

---

// 완성코드

#1940
import sys
input = sys.stdin.readline
N = int(input())
lists = list(map(int,input().split()))

lists.sort()
cnt = 0

for K in range(N):
    S = 0
    E = N - 1
    while S < E:
        if lists[S] + lists[E] == lists[K]:
            if S != K and E !=K:
                cnt += 1
                break
            elif  S == K:
                S += 1
            elif E == K:
                E -= 1
        elif lists[S] + lists[E] <lists[K]:
            S += 1
        else:
            E -= 1


print(cnt)