KOITP 정렬된 배열 (투포인터 알고리즘) 문제

 

 

 

전형적인 투포인터 알고리즘 문제이다

 

 

중요한건 ;ㅅ;

문제를 읽고 투포인터 알고리즘 문제라는 것을

깨달아야 한다는 것이다 ^_^,,,,,,

따흑,,,

 

 

 

이것도 처음엔 문제 이해가 안갔다 @_@

왜이렇게 문제 이해가 어려운것인지,,,,,흑,,,,

 

 

결국 이문제도 간단하게 설명하자면

정렬된 길이 n의 A배열과 길이 m의 B배열이 입력으로 주어졌을 때
A[i]+B[j]=X를 만족하는 (i, j)쌍의 개수를 구하는 문제
이다.

 

 

 

이문제는 어떻게 투포인터 알고리즘으로 구현했냐하면

 

가장 중요한건

작은 (왼쪽~) 은 i로 정의

큰값부터 줄어드는 (오른쪽 ) 은 j로 정의

한다는 것이다!

 

 

 

 

 

A

i	->
7	8	9

 

B

	<-	j
3	5	7

 

 

 

이렇게 투포인터를 만들어주고

각각 끝점 값을 더해줘서

값이 크면~ j를 옮기고

작으면 i를 한칸 옮겨준다.

 

 

 

 

 

 

투포인터 알고리즘을

이해하기 좋은 문제인거 같다

 

다행히 이문제는

쌤의 설명이 바로~ 이해가 갔다

 

그럼이만

뿅!