[C++] 백준 3273 두 수의 합

오늘도 도서관에 왔다.

그런데 점심 먹고 이것저것 하다 보니 벌써 1시 45분이다 ㅎㅎ.

얼른 문제를 풀어야지...

 

문제

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

3273번: 두 수의 합

오늘의 문제이다.

 

음... 이 문제는 배열에 입력을 받고 그 배열을 오름차순으로 정렬해 주어야겠다.

그리고 앞이랑 뒤에 포인터로 가리켜서 비교해 보면 될 것 같다는 생각이 들어 이런 코드가 있나 찾아보니

https://ansohxxn.github.io/algorithm/twopointer/

이렇게 투 포인터 알고리즘이라는 것이 있었다.

투 포인터 기법이란, 두 개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘이라고 한다.

 

이 문제에서는 포인터 두 개가 양끝에서 반대로 진행하는 것을 사용하면 될 것 같다.

왼쪽의 포인터는 오른쪽 포인터가 가리키는 수와 합쳤을 때 13이 되거나 오른쪽 포인터가 왼쪽 포인터와 부딪쳤을 때 오른쪽으로 한 칸 움직여준다.

오른쪽의 포인터는 왼쪽 포인터가 가리키는 수와 합쳤을 때 13이 아니거나 왼쪽 포인터와 부딪치지 않았을 때 왼쪽으로 한 칸 움직여준다.

 

그럼 코드를 작성해 보자~

 

...

 

//시간 초과된 코드

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

int a[100000];

int main() {
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cin >> x;

	sort(a, a + n);

	int start = 0;
	int end = n - 1;
	int sum, result = 0;
	while (start != n - 2) {
		sum = a[start] + a[end];
		if (sum == x) {
			result++;
			start++;
		}
		else {
			end--;
		}
		if (start >= end) {
			start++;
			end = n - 1;
		}
	}

	cout << result << "\n";

	return 0;
}

...

 

... 그럼 그렇지

예제 입력으로 실행해 봤는데 알맞게 출력되어서 한 번에 맞출 것이라는 기대를 해버렸다...

 

혹시나 어제 배운 것처럼 main 시작 부분에 ios::sync_with_stdio(false); cin.tie(0); 를 쓰거나 cin, cout 대신 scanf, printf를 써보기도 했는데 결과는...

 

처참...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

왜죠...??ㅠㅠ

 

 

 

도저히 모르겠어서 다른 풀이를 찾아보기로 했다...

오...??

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

int a[100000];

int main() {
	int n, x;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	scanf("%d", &x);

	sort(a, a + n);

	int start = 0;
	int end = n - 1;
	int sum, result = 0;
	while (start < end) {
		sum = a[start] + a[end];
		if (sum == x) {
			result++;
			start++;
			end--;
		}
		else if(sum > x){
			end--;
		}
		else {
			start++;
		}
	}

	printf("%d", result);

	return 0;
}

 

뭐지???

https://velog.io/@aurora_97/%EB%B0%B1%EC%A4%80-3273%EB%B2%88-%EB%91%90-%EC%88%98%EC%9D%98-%ED%95%A9-Swift

이 분은 다른 언어이기는 한데 초반에는 나랑 비슷하게 푸셔서 while문 부분을 따라서 내 코드를 수정하니까 맞았다...??

 

sum 값이 x보다 크면 수가 작아져야 하기 때문에 end--

sum 값이 x보다 작다면 수가 커져야 하기 때문에 start++

sum 값과 x 값이 같으면 해당 수들은 다른 수들과 다시 비교할 필요가 없기 때문에 end--, start++, result++

 

아!!! 맞네... 내가 문제를 잘못 풀었네 ㅎㅎ.

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

int a[100000];

int main() {
	int n, x;
	cin>>n;
	for (int i = 0; i < n; i++) {
		cin>>a[i];
	}
	cin>>x;

	sort(a, a + n);

	int start = 0;
	int end = n - 1;
	int sum, result = 0;
	while (start < end) {
		sum = a[start] + a[end];
		if (sum == x) {
			result++;
			start++;
			end--;
		}
		else if(sum > x){
			end--;
		}
		else {
			start++;
		}
	}

    cout<<result<<"\n";

	return 0;
}

물론 cin, cout으로 써도 시간초과는 나지 않는다. 괜히 이상한 곳만 고치고 있었다 ㅎㅎ.

 

그리고 정렬 후 투포인터를 이용하는 법이 아닌 다른 방법으로 푸는 방법이 있다고 한다.

원소 체크를 해서 배열의 원소 a에 대해서 x-a가 배열에 있는지 체크하는 방법이라고 하는데...

#include <iostream>
using namespace std;

int num[100001];
int cnt[2000001];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,tmp,x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		num[i]=tmp;
		cnt[tmp] = 1;
	}
	cin >> x;
	int sum = 0;
	for (int i = 0; i < n; i++) {
    	// x-num[i]가 음수면 런타임에러나므로 조심
		if (x-num[i]>=0 && cnt[x - num[i]] != 0 && x-num[i]>num[i]) {//i<j조건도 넣어준다.
			sum += 1;
		}
	}
	cout << sum;
	return 0;
}
출처: https://haerang94.tistory.com/443

아.... 아...? 아!! 알겠다. 무슨 소리인지 모르겠어서 한참 쳐다봤네..ㅎㅎ

 

그니까 num [i]와 합쳤을 때 x가 되는 수가 있는지 알아보기 위해

x-num [i]이 0 이상이고, 입력을 받은 적이 있고, 중복으로 count가 되지 않아야 하니까 해당 num[i] 보다는 커야 하는 조건이 들어간 것이다.

 

오호 이렇게도 풀 수 있구나...

다음번에는 풀이를 잘 생각해야겠다.