[백준] 3273 (feat. 집합 set)
https://www.acmicpc.net/problem/3273
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
num = int(input())
lst = list(map(int, input().split()))
sum = int(input())
count = 0
reside = []
for i in lst:
reside.append(sum - i)
intersection = list(set(lst) & set(reside))
print(int(len(intersection)/2))
처음에는 그냥 2중 for문으로 돌려서 했는데 역시나 시간초과가 나왔다.
어떤 방법으로 할까 고민하다가 집합이 생각나서 집합으로 해결.
나의 경우는, 두 개의 집합을 만들어서 교집합하여 답을 구하는 방식으로 진행했다.
집합에도 참 많은 메소드들이 있는 것 같다.
필요할 때마다 좀 찾아보면서 메소드들을 익혀야 할 것 같다. (어차피 지금 다 정리해도 다 까먹음ㅋㅋ)
(집합 메소드: https://wikidocs.net/16044)
집합에도 여러 방법이 있더라.
List에서 if _ in array => 이거의 경우, 시간복잡도가 O(n)이지만
Set에서는 if _ in set => 이거의 경우, 시간복잡도가 O(1)이다.
이런 것을 보면, set을 통해서 확인하는 방법으로 시간복잡도 문제를 해결할 수 있을 듯 싶다.
진짜 깔끔하게 푸신 분
(https://www.acmicpc.net/source/18014614)
어떤 다른 분은, 이분탐색?을 사용하셨던데 이것도 좋은 방법인 것 같다.
일단 정렬을 하고 맨왼쪽과 오른쪽을 하나씩 줄여가면서 x에 부합하는 값을 찾아가는 법.
'개발자 > 알고리즘' 카테고리의 다른 글
| [백준] 13300번 (feat. 2차원 배열) (0) | 2022.01.15 |
|---|---|
| [백준] 10808 (feat. 파이썬 문자의 아스키코드) (0) | 2022.01.15 |
| [백준] 1406번 (feat. reverse와 reversed의 차이점) (0) | 2022.01.12 |
| [백준] 1874번 R (0) | 2022.01.12 |
| [백준] 10828번 (feat. input()과 sys.stdin.readline()의 차이) (0) | 2022.01.12 |