[G5] 백준 9024번 두 수의 합 C++ 투 포인터, 정렬

리뷰

 

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

서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수의 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : 수열의 크기를 저장할 변수
• k : 목표가 될 정수를 저장할 변수
• s : 수열 정보를 저장할 배열

 

함수

없음

 

 

문제풀이

1. t값을 입력 받고, t번의 테스트케이스를 수행한다.
2. 매 테스트케이스마다 n, k값을 입력 받아준다.
3. n개의 수를 입력 받아 배열 s를 초기화한다.
4. sort함수를 통해 s배열을 오름차순으로 정렬한다.
5. 변수 b를 매우 큰 값, cnt를 0으로 초기화한다.
6. 변수 l을 0, r을 n-1로 초기화한다.
7. l이 r미만일 경우를 조건으로 하는 while루프를 수행한다.
8. 변수 sum을 s[l]+s[r]로 초기화 한다.
9. 변수 diff를 k-sum의 절대값으로 저장한다.
10. b가 diff보다 클 경우 b를 diff로 변경하고, cnt를 1로 초기화한다.
11. b와 diff가 동일할 경우 cnt를 증가시킨다.
12. sum이 k보다 작을 경우 l을 증가시키고, k보다 클 경우 r을 감소시킨다. 동일할 경우 모두 적용한다.
13. 매 테스트 케이스 마다 cnt를 출력하고 개행문자를 삽입한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 수열 S의 원소는 서로 다른 정수임이 보장된다.
2. 테스트케이스의 크기가 생각보다 큰 것 같다. 빠른 입출력을 사용하는게 권장되어 보인다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6;
int t, n, k;
int s[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n >> k;
		for (int i = 0; i < n; ++i) cin >> s[i];
		sort(s, s + n);

		int b = 2e9, cnt = 0;
		int l = 0, r = n - 1;
		while (l < r) {
			int sum = s[l] + s[r];
			int diff = abs(k - sum);

			if (b > diff) {
				b = diff;
				cnt = 1;
			}
			else if (b == diff) ++cnt;
			
			if (sum < k) ++l;
			else if (sum > k) --r;
			else {
				--r;
				++l;
			}
		}
		cout << cnt << "\n";
	}
	
}