[백준] 1940 (주몽)

1940

1940번: 주몽

🐱‍🏍접근

입력받은 자연수 리스트를 오름차순으로 정렬한 후 양끝에서부터 포인터를 지정하여 두 수의 합을 구하는 방식으로 구현

시작 인덱스(s)는 리스트의 0번 인덱스에서부터  종료 인덱스(e)는 리스트의 마지막 (N-1)번 인덱스에서부터 시작

투 포인터 이동원칙
- lst[s] + lst[e]  > M : e -= 1
- lst[s] + lst[e] < M : s += 1
- lst[s] + lst[e] == M : cnt +=1; s += 1; e-=1  //// 두 수의 합이 M이 될 경우 각 포인터를 한칸 씩 당겨주기 

풀이

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
lst = list(map(int,input().split()))
lst.sort() # 리스트 정렬

# 사용 변수들 초기화 
cnt  = 0  # 합이  M인 경우의 수 카운트
s = 0  # 시작 인덱스 지정
e = N-1 # 마지막 인덱스 지정

while s < e :
    if lst[s] + lst[e] == M : 
        print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M}과 같음')        
        cnt += 1
        s += 1
        e -= 1
    elif lst[s] + lst[e] < M :
        print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M} 보다 작음')        
        s += 1
    else:
        print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M} 보다 큼')        
        e -=1
print(cnt)

## 입출력 예시
6
9
2 7 4 1 5 3
s:0(1) e:5(7) => 합이 9 보다 작음
s:1(2) e:5(7) => 합이 9과 같음
s:2(3) e:4(5) => 합이 9 보다 작음
s:3(4) e:4(5) => 합이 9과 같음
2