[백준 BOJ] 4158번 CD (C++/cpp)

문제 설명

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

4158번: CD

 

접근 방법 - 두 포인터의 기본 문제

백준의 4158번 문제는 두 포인터의 기본적인 원리를 다루고 있는 문제이다.

해당 문제는, 상근이와 선영이가 가지고 있는 CD에 있어 중복되는 CD의 개수를 구하여 출력해야 하는 문제이다.

이때 두 포인터란, 진짜 포인터의 개념을 쓰는 것이 아니라, 2개 이상의 변수를 배열이나 벡터의 인덱스로 사용하는 원리를 통한 알고리즘을 의미한다. 사실 필자피셜 읍읍

두 포인터의 원리를 이 문제와 아주 유사하게 응용한 문제에 대한 풀이를 아래에 기재해 놓으니, 해당 알고리즘에 처음 접해본다면 아래의 링크도 함께 참고하면 좋을 것이다.

https://smary-it.tistory.com/225

[백준 BOJ] 11728번 배열 합치기 (C++/cpp)

입력값들이 이미 오름차순으로 정렬된 상태로 주어지기 때문에, 필자는 두 CD의 번호 크기를 비교하면서 인덱스를 이동하도록 코드를 작성하였다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서
(여러 테스트 케이스가 주어지기 때문에, 무한 반복문을 이용하였다.)

1) 상근이와 선영이가 각각 가지고 있는 CD의 총 개수(n, m)를 입력받는다.

(만일 여기서 0 0을 입력받았다면, 문제에 나와있는 대로 해당 반복문을 탈출하여 즉시 종료되도록 한다.)

 

2) 상근이와 선영이가 가지고 있는 CD의 번호를 각각 입력받을 벡터 sk, sy를 선언해 둔다.

 

3) 상근->선영 순서대로, 각각 가지고 있는 CD의 번호를 입력받고 이를 각 벡터에 추가한다.

 

4) 중복되는 CD의 개수를 저장할 변수 count를 0으로 초기화하여 선언한다.

또한, 두 포인터 알고리즘에 사용할 변수 index1, index2도 모두 0으로 초기화하여 선언한다.

(index1은 sk의 값에 접근할 때, index2는 sy의 값에 접근할 때 사용할 예정이다.)

 

5) index 변수들이 각각 n과 m을 넘기지 않을 때까지 실행할 반복문을 만들어, 아래의 원리대로 연산을 수행한다.

* index1과 index2에 대한 sk, sy의 크기를 비교하며, index1과 index2의 값을 변동하고 정답을 구한다.

(index1과 index2 모두 처음에는 0으로 시작하기 때문에, 각각 첫 번째 값부터 비교를 시작한다.)
- 현재 탐색 중인 sk의 값과 sy의 값이 같다면, 이는 CD 번호가 중복됨을 의미한다.
따라서 이 경우엔, count에 1을 더하고 index1에 1을 더하여 다음 값을 탐색한다. (index2 값에 1을 더해도 된다.)
- sk의 값이 sy의 값보다 크다면, 이는 sy의 이다음 값 중에서 현재 sk와 같은 값이 있을 수 있음을 의미한다.
따라서 이 경우엔, index2에 1을 더하고 다음 연산을 수행한다.
- sy의 값이 sk의 값보다 크다면, 이는 반대로 sk의 이다음 값 중에서 현재 sy와 같은 값이 있을 수 있음을 의미한다.
따라서 이 경우엔, index1에 1을 더하고 다음 연산을 수행한다.

 

6) 위 연산이 모두 완료되었다면, 최종적으로 저장된 count의 값을 출력한 뒤 다음 테스트 케이스를 수행한다.

 

7) 모든 테스트 케이스의 연산이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 4158번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	while (1) {
		int n, m;
		cin >> n >> m;
		if (n == 0 && m == 0) { break; }

		vector<int> sk;
		vector<int> sy;
		int num;
		for (int i = 0; i < n; i++) {
			cin >> num;
			sk.push_back(num);
		}
		for (int i = 0; i < m; i++) {
			cin >> num;
			sy.push_back(num);
		}

		int count = 0;
		int index1 = 0;
		int index2 = 0;
		while (index1 < n && index2 < m) {
			if (sk[index1] == sy[index2]) { count++; index1++; }
			else if (sk[index1] > sy[index2]) { index2++; }
			else { index1++; }
		}
		cout << count << endl;
	}
}

 

제출 결과

(2023.01.08 백준 4158번 문제 제출 결과)

사실 시간초과 뜨고 나서야 두 포인터 문제인 것을 알았다 카더라 읍읍