[백준 BOJ] 6550번 부분 문자열 (C++/cpp)

문제 설명

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

6550번: 부분 문자열

 

접근 방법 - 큐를 이용한 문자열 연산 문제

백준의 6550번 문제는 문자열 연산에 있어 큐를 이용하여 해결할 수 있는 문제이다.

해당 문제는, 각 케이스마다 입력되는 2개의 문자열에 대하여 부분 문자열인지 아닌지를 출력해야 하는 문제이다.

사실 이 문제는 그리디 알고리즘으로 해결해야 하는 문제인데, 이에 대한 해결법을 원한다면 그대로 뒤로 가기를 눌러주길 바란다.

(사실 본인이 그리디 알고리즘을 이용한 건지 아닌지도 모르겠다.)

필자의 경우에는, 큐를 이용하여 알파벳 하나하나를 순차적으로 탐색하도록 하였다.

굳이 큐를 사용할 필요는 없는 문제였지만, 당시 필자가 큐를 위주로 공부하고 있던 때였어서 한번 사용해보았다.

이때, 케이스의 수가 입력으로 따로 주어지지 않기 때문에 아래 구문을 참고하면서 문제를 해결하길 바란다.

if (cin.eof() == 1) { break; }

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

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

 

코드의 실행 순서

(무한 반복문을 통해 아래의 연산을 순차적으로 수행한다.)

1) 2개의 문자열(a, b)을 순차적으로 입력받는다.

만일 입력값의 끝에 도달하였다면, 무한 반복문을 탈출하도록 한다.

 

2) 연산을 위한 char형 큐(s)를 선언한다.

 

3) a 문자열에 대하여, 각 알파벳들을 s에 순차적으로 push한다.

 

4) b 문자열의 길이만큼 반복문을 실행하여 아래의 연산을 수행한다.

- 만일 s의 front()값이 b에 대한 현재 탐색값과 동일하다면, s에 대하여 pop 연산을 취한다.

- 만일 s에 존재하는 값이 더 이상 없다면, 부분 문자열 탐색이 완료되었다는 것을 뜻한다. 따라서 이 경우엔, "Yes"를 출력한 뒤 해당 반복문을 탈출한다.

- 만일, b 문자열의 끝까지 탐색하였음에도 s에 존재하는 값이 있다면, 부분 문자열 탐색이 완료되지 못하였음을 뜻한다. 따라서 이 경우엔, "No"를 출력한 뒤 해당 반복문을 종료한다.

 

5) 각 케이스에 대한 출력이 모두 끝났다면, 실행 종료한다.

반응형

 

성공한 코드

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

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

	while (1) {
		string a, b;
		cin >> a >> b;
		if (cin.eof() == 1) { break; }

		queue<char> s;
		for (int i = 0; i < a.length(); i++) {
			s.push(a[i]);
		}

		for (int i = 0; i < b.length(); i++) {
			if (s.front() == b[i]) { s.pop(); }
			if (s.empty()) {
				cout << "Yes" << endl;
				break;
			}
			if (!s.empty() && i == b.length() - 1) {
				cout << "No" << endl;
			}
		}
	}
}

 

제출 결과

(2022.06.14 백준 6550번 문제 제출 결과)