[알고리즘/투 포인터] 1940번 : 주몽 - python

링크 : https://www.acmicpc.net/problem/1940

1940번: 주몽

 

---

• 문제
• 소요시간: 4분 14초

---

• 설계하기(접근방법) 

1. 입력받기

고유번호 개수

타겟 숫자

고유번호 리스트를 입력받는다

 

2. 구현하기

고유하다는 문제의 조건에서 해시함수

즉 딕셔너리를 떠올릴 수 있다

 

15000개의 데이터를 전부 하나씩 찾는다면

시간초과에 걸릴 것이니

 

딕셔너리에 15000개의 데이터를 넣고

 

타겟 넘버인 m 에 고유번호 숫자를 뺀 값

ex) m - 7 = 2

2 가 딕셔너리에 있는지 검사한다

 

있다면 cnt += 1을 해준다

 

3. 출력하기

중복되어 카운팅되었을테니

cnt // 2를 해주어 출력한다

 

---

• 코드(출력)

n = int(input())
m = int(input())

ingredient = {}
cnt = 0
num = list(map(int, input().split()))

for i in num:
    ingredient[i] = 1

for i in num:
    if (m - i) in ingredient:
        cnt += 1

print(cnt//2)

---

• 얻어갈 부분

1. 알고보니 투포인터 문제였다