[BAEKJOON/Python] no.1940 주몽 | 정렬

 

문제

---

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

1940번: 주몽

 

 

1차 풀이

---

material_count = int(input())
need_num = int(input())
material_num = list(map(int, input().split()))
material_num.sort() 

result = 0

small_num_idx = 0
big_num_idx = material_count - 1

while(True):
    if small_num_idx >= big_num_idx:
        break

    small_num = need_num - material_num[big_num_idx] 

    if small_num == material_num[small_num_idx]:
        result += 1
        small_num_idx += 1
        big_num_idx -= 1
    elif small_num < material_num[small_num_idx]:
        big_num_idx -= 1
    else:
        small_num_idx += 1

print(result)

👉🏻전체코드! 일단 투 포인터를 사용해 가장 큰 수와 가장 작은 수들을 차례로 더해주며 갑옷을 만들었다.

• 각 재료의 고유 번호를 담은 material_num 리스트를 정렬해준다. 정렬을 해주어야 투 포인터를 이용하기 쉽다.
• 작은 숫자를 가리킬 인덱스는 small_num_idx는 0부터 시작하고 큰 숫자 인덱스인 big_num_idx는 리스트의 마지막부터 시작한다.
• while문을 돌며 small_num_idx가 big_num_idx보다 커지면 break한다.
  • 재료의 합인 need_num에서 큰 수(material_num에서 big_num_idx번째 숫자)를 빼서 필요한 숫자를 small_num에 저장한다.
  • small_num이 작은 수(material_num에서 small_num_idx번째 숫자)와 같으면 result에 1을 더하고 small_num_idx도 1을 키워주고 big_num_idx는 1 줄여준다.
  • small_num이 작은 수(material_num에서 small_num_idx번째 숫자)보다 작으면 맞는 짝이 없는 것이기 때문에 big_num_idx를 1 줄여준다. 그렇지 않으면 small_num_idx를 1 올려준다.