섹션1. 자료구조(Data Structure). [투 포인터 실전 문제] 좋은 수 구하기(백준 1253)

 

1. 예제 출력에서 나온 8이 어떻게 나온건지 분석해보기

    -> 1,2 는 표현이 안됨.

    -> 3은 1과 2의 합

    -> 4는 1과 3의 합

    -> 5,6,7,8,9,10 모두 다른 두 수의 합으로 표현이 가능함.

    -> 그러므로 총 8개.(3,4,5,6,7,8,9,10)

--> 하지만 예제입력은 정렬되어있고 양의 정수이지만, 입력할때는 정렬되지 않을 수도 있고, 음의 정수가 나올 수 있음.

 

 

2. 문제 분석하기 

 

그럼 질문!

-> 이 문제를 보고, 어떻게 '투 포인터 정렬'이란걸 알지?

A. 사실 여러가지 종류의 문제를 풀어봐야 한다. 하지만 공부를 계속 하다보면 코딩테스트에 나오는 타입은 대개 정해져있다. 이런 문제는 이런 알고리즘은 쓰는구나 라고 정해지는 순간이 오게 된다.

예제 입력을 봤을 때, 일렬로 데이터 값이 입력이 되고 여기에 어떤 값이 다른 애들의 조합으로 판단이 된다하면 정렬 투포인트를 쓴다. (문제에서 핵심이 되는 건 "두 수" -> 투 포인터라고 유추 가능)

투 포인터는 두개를 가리킨다.

 

 

3. 손으로 풀어보기 

    ①. 수를 입력받아 배열에 저장한 후 정렬한다. (nlogn의 시간복잡도가 들고 딱 1번만 해주면 된다)

  ②. 투 포인터(i, j)를 양쪽 끝에 위치시킨다.

  ③. i(start)와 j(end)가 이동을 하면서 전체 배열을 탐색하는데 걸리는 시간은 O(N)

  ④. 투 포인트 원칙은 우리가 정하면 된다.

  ⑤. 현재 내가 좋은 수인지 판별하고 있는 숫자를 K라고 둔다.

  ⑥. 만약 i와 j의 값이 k보다 크면 j를 왼쪽으로, k보다 작으면 i를 오른쪽으로 옮긴다.

       º  정렬된 배열이기 때문에 j(end)를 왼쪽으로 옮기면 j의 값은 작아져 i+j한 값이 작아진다

       º  반대로 i(start)를 오른쪽으로 옮기면 i의 값이 커져서 i+j한 값이 커진다

  ⑦. i+j와 k의 값이 같으면 count++을 하고 프로세스를 종료한다.

  ⑧. 여기서 전제 조건은 i는 j보다 작다. 예외처리로 i 또는 j가 k가 되면 안된다(자기 자신이 들어가면 안됨)

 

 

4. 슈도코드 작성하기

 

정수형변수 N(입력할 숫자의 개수)

크기가 N인 벡터 생성

 

for(0부터 N까지)

{

   벡터에 N개의 값 입력받아 추가하기

}

sort(벡터의 값 정렬하기)

 

정수형 변수 result(좋은 수의 총 개수)

 

//좋은 수 구하는 알고리즘

for(인덱스 K(찾고자 하는 수를 가리키는 인덱스)을 0부터 N까지 반복해주기) //하나하나 다 찾아야함

{

    long형변수 find (좋은 수인지 판별하기 위한 변수. 즉, K인덱스의 값)

    정수형변수 i (첫번째 위치 인덱스)

    정수형변수 j (가장 마지막 위치 인덱스)

    while(i가 j보다 작을때)

    {

         if (인덱스i의 값과 인덱스 j의 값의 합이 인덱스 k의 값과 같으면) {

                   if (인덱스i 또는 인덱스j의 값이 인덱스 k와 같지 않으면){

                       Reslut 개수 올리기

                       break

                   }

                   else if (인덱스 i와 인덱스 k가 같으면){

                       i++

                   }

                   else if ( 인덱스 j와 인덱스 k가 같으면 ){

                       j--

                   }

            }

            else if ( 인덱스i의 값과 인덱스 j의 값의 합이 k보다 작으면){

             i ++

           }

           else{    //인덱스i의 값과 인덱스 j의 값의 합이 k보다  크면

              j--

           }

    }

  result 출력

}

 

 

5. 최종 코드

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

int main()
{
	//입출력을 빠르게 해준다
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N; //입력할 숫자 개수
	vector<int> A(N, 0); //벡터 생성

	for (int i = 0; i < N; i++) {
		cin >> A[i]; //push_back을 사용해도 되나 배열처럼 사용하고 싶어서 이렇게 벡터에 값 추가
	}

	sort(A.begin(), A.end()); //벡터 데이터 정렬

	int Result = 0;

	for (int k = 0; k < N; k++) {
		long find = A[k];//k가 가리키는 값이 좋은 수인지 확인
		int i = 0;
		int j = N - 1;

		while (i < j) {
			if (A[i] + A[j] == find) {
				if (i != k && j != k) {//예외처리(내 자신을 포함하면 안됨)
					Result++;
					break;
				}
				else if (i == k) {
					i++;
				}
				else if (j == k) {
					j--;
				}		
			}
			else if (A[i] + A[j] < find) {
				i++;
			}
			else { //(A[i] + A[j] > find)
				j--;
			}
		}
	}

	cout << Result << endl;
}

 

 

 

 

 

<출처>

https://inf.run/M65d

[무료] Do it! 알고리즘 코딩테스트 with C++ - 인프런 | 강의