[boj][c++] 3273 두수의합

입출력 관련 이슈

어제였나 그제 큰 수의 배열을 선언하면 프로그램이 꺼지는데 왜 그럴까 하는 이야기를 쓴 기억이 있는데 그 이유를 찾았다.

너무 큰 배열을 사용할 때의 문제

해결방법은 전역변수 를 선언하는 것이다. 그런데 라피신 생활을 겪은 나에게 전역변수는 머리로는 이해가 가지만 마음으로는 그다지 손이 가지 않는... 그런 존재라 찝찝하다.

전역변수 선언만으로는 시간 초과 문제가 해결되지 않을 때 한번 더 해볼 것은 cstream과 c++stream의 동기화를 끊는 ios::sync_with_stdio(0) 를 사용하는 것이다. 어차피 c++만 쓰는 나는 cstream인 printf, scanf는 사용하지 않기 때문에 위의 코드를 추가하고 cin, cout만 사용하면 된다. cin.tie(0) 이건 버퍼 관련 코드인데 온라인 저지 사이트에는 콘솔창이 꼬이는 것을 방지할 필요가 없기 때문에 해당 명령어를 써서 과정을 생략해준다. 그럼 더 빠른 출력이 가능하다. 백준전용 치트키인 느낌!

다만 이런 입출력 상의 문제보단 근본적으로 코드가 문제인 경우가 많기 때문에 참고용으로만 알아두자. 다른 사람들이 백준 풀이 올린 거 볼때마다 보이는 명령어라 궁금해서 찾아봤다.

---

3273 두 수의 합

처음에는 이중for문 사용해서 풀었다. 시간 초과해서 틀렸다. 백준 내 질문 검색으로 찾아보니 투포인터 이용해서 풀라고 했다. 투포인터?라고 하면 quick sort만 생각나는데, 인덱스 양끝에 포인트를 둬서 구하는거다. 이름 그대로 빠른 정렬이라 복잡도 측면에서 좋은 알고리즘이었는데 시간초과 이슈가 있었기 때문에 여기서 영감을 얻었다. 결과는 맞았습니다~!ㅎㅎ

[ 수정 전]

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

int main()
{
	int n, m, x, cnt;
	int arr[100001];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		arr[i] = m;
	}
	sort(arr, arr + n);
	cin >> x;
	cnt = 0;
	if (n > 1)
	{
		for (int i = 0; i < n - 1; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (arr[i] + arr[j] == x)
					cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

[수정 후]

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

int arr[100001];

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
	int n, x, cnt, left, right;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr + n);
	cin >> x;
	cnt = 0;
	left = 0;
	right = n - 1;
	while (left < right)
	{
		if (arr[left] + arr[right] == x)
		{
			cnt++;
			right--;
		}
		else if (arr[left] + arr[right] > x)
			right--;
		else
			left++;
	}
	cout << cnt << "\n";
	return 0;
}