(C++)알고리즘 탐구 1. 유효한 팰린드롬 (풀이, 남의 코드 분석)

참고도서 : 파이썬 알고리즘 인터뷰 . 박상길 .  책만 . 2020
참고도서에서 언급하는 알고리즘 주제를 참고하여  C++로 풀어보는 것을 목표로 합니다. 

---

 

팰린드롬이란 앞뒤가 똑같은 단어나 문장으로 뒤집어도 같은 말이 되는 단어 또는 문장을 말합니다.

문제 : 주어진 문자열이 팰린드롬인지 확인해라, 대소문자를 구분하지 않는다. 알파벳만 판정하며, 다른 문자열은 판정하지 않는다.

10174번: 팰린드롬 (acmicpc.net).

10174번: 팰린드롬

이 문제와의 다른점이라면 책에서 원하는 알고리즘은 공백이나 기타 특수문자를 제거하길 원합니다. 

 

총 3가지의 풀이가 있다고 합니다.

 

 

우선 백준의 경우가 난이도가 낮으니 백준부터 풀어보도록 하겠습니다. 백준의 경우에는 띄어쓰기까지 구분을 하게하는 경우입니다.

 

---

내 방식대로 풀어보자.

---

일단 문자열의 앞글자와 뒷글자를 비교해서 같으면 pass하고, 아니면 fail을 출력하고록 할 수 있을 것입니다. 그러면 쉽게 풀 수 있을 것이라 생각합니다.

그러나 한 가지 요소가 발목을 잡습니다. 대소문자를 구별하지 않는다. 여러 모듈을 사용할 수 있겠지만 모듈을 사용하지 않고 적는 방법은 모든 대소문자를 소문자로 변환하는 과정을 거치고 펠린드롬인지 체크하는 과정을 진행을 하면 될 것 같습니다.

일단 알고리즘 설계를 진행합시다. 

 

다음의 양식을 암기하는 것을 추천드립니다.

#include <iostream>

int main() {
	int t; std::cin >> t;
	while (t--) {

	}
}

백준이나 여러 코딩테스트에서 여러번 입력을 받는 다는 것을 다음처럼 구성하면 편합니다. 

using namespace std;

다음의 내용을 추가해서 std::를 붙이지 않게 할 수 있습니다. C++은 코딩의 스타일이 서로 다를 수 있는 언어라고 생각됩니다. 저는 일단 사용하지 않는 방향으로 코드를 짜겠습니다.

 

그러면 내부에 들어갈 내용을 예상해봅시다. 우선은 대소문자를 소문자로 변환해주는 함수를 작성해봅시다.

#include <iostream>

int main() {
	int t; std::cin >> t;
	while (t--) {
		std::string sen; std::cin >> sen;
	}
}

여기까지는 펠린드롬 문장을 받아오는 과정이라고 생각하면됩니다.

그러나 여기서 한가지 치명적인 오류가 있습니다. 여기서 cin으로 받아오게되면 어떻게될까요?

만약에 Hello World를 입력했다고 생각합시다.

Hello World가 모두 입력되는게 아니라 Hello 한 번 World 한 번 총 두 번 입력되게 됩니다.

그러니 여기서는 다른 방식의 입력을 받아야합니다. 공백을 포함하는 입력은 C++에서는 getline 함수를 통해서 받을 수 있습니다.

그래서 위의 코드를 다음처럼 변경해야합니다.

#include <iostream>
#include <string>

int main() {
	int t; std::cin >> t;
	while (t--) {
		std::string sen; getline(std::cin, sen);
	}
}

그러면 공백을 포함한 문자를 입력받을 수 있게됩니다. 그러나 여기서 한 가지 문제가 발생합니다. 그런 cin과 getline을 함께 쓸때 함께 받을 때 생깁니다.

cin으로 입력을 받으면 개행문자를 버퍼에서 삭제하지 않습니다. 그래서 다음처럼 버퍼를 비워주는 과정을 추가해주어야합니다.

#include <iostream>
#include <string>

int main() {
	int t; std::cin >> t;
    std::cin.ignore();
	while (t--) {
		std::string sen; getline(std::cin, sen);
	}
}

그러면 이제 코드를 계속 짜도록 합시다.

 

 

그러면 여기서 펠린드롬 여부를 체크하는 함수를 하나 만들어봅시다. 

bool palindrome(std::string& sen) {

}

string의 참조값을 매개변수로 전해주고 그 참조값을 받아옵니다.

 

내부에 들어갈 내용을 고민해봅시다. 문자열을 받아오면 거기서 우리는 펠린드롬인지 여부를 결정하고 반환을 해야합니다.

문자열의 앞과 끝을 비교하기 때문에 중간까지만 문자가 동일하다면 문제가 없을 것입니다. 

bool palindrome(std::string& sen) {
	int start = 0; int end = sen.length();
	for (int i = 0; i < sen.length() / 2; i++) {

	}
}

다음처럼 작성을 할 수 있을 것입니다. 여기서 start 는 문자열의 맨글자를 나타낼 것이고, end는 문자열의 맨 끝점을 나타낼 것입니다. 이걸 중간까지만 비교해서 서로 같기만 하면 끝입니다.

우선은 대문자인지 소문자인지 판단을 시켜야할 것 입니다. 대문자라면 소문자로 변환을 시키는 코드를 작성합니다.

bool palindrome(std::string& sen) {
	int start = 0; int end = sen.length();
	for (int i = 0; i < sen.length() / 2; i++) {
		if (sen[start] >= 'A' and sen[start] >= 'Z') {
			sen[start] = sen[start] + ('A' - 'a');
		}
		if (sen[end] >= 'A' and sen[end] >= 'Z') {
			sen[end] = sen[end] + ('A' - 'a');
		}
	}
}

대문자를 모두 소문자로 변환시켰다면 비교가 가능합니다.

bool palindrome(std::string& sen) {
	int start = 0; int end = sen.length()-1;
	for (int i = 0; i < sen.length() / 2; i++) {
		if (sen[start] >= 'A' and sen[start] <= 'Z') {
			sen[start] = sen[start] + 32;
		}
		if (sen[end] >= 'A' and sen[end] <= 'Z') {
			sen[end] = sen[end] + 32;
		}

		if (sen[start] != sen[end])
			return false;
		start++;
		end--;
	}
	return true;
}

그러면 결국 이렇게 코드가 작성되고 끝이납니다. 한 번이라도 틀리면 false를 반환시킵니다.

중간까지 돌았을때 멀쩡하면 살립니다. 

 

이제 메인문을 완성하고 동작을 살펴봅시다.

int main() {
	int t; std::cin >> t;
	std::cin.ignore();
	while (t--) {
		std::string sen; getline(std::cin, sen);
		if (palindrome(sen) == false) {
			std::cout  << "No" << std::endl;
		}
		else {
			std::cout << "Yes" << std::endl;
		}
	}
}

백준의 예제를 입력넣어봅시다.

 

 

결과는 잘 나오고 문제를 맞추었습니다.

 

이 문제에서 생각해볼 수 있었던 점은 두 가지라고 생각합니다.

1. 공백을 포함하는 문자열을 받을 때는 꼭 getline을 사용하도록 합니다.

2. 함수에서 매개변수를 넘길때는 참조나 포인터를 사용하도록 합니다. 이것은 그에 대한 chatgpt의 답변입니다.

bool palindrome(std::string& sen) {
와
bool palindrome(std::string sen) {
의 차이점은 무엇인가요?

이 두 함수의 차이점은 palindrome 함수가 std::string& sen를 참조로 받느냐, 
값으로 받느냐의 차이입니다.

첫 번째 함수의 경우 std::string& sen을 참조로 받기 때문에, 
함수 내에서 문자열을 수정할 경우 호출자가 전달한 문자열 객체가 직접 수정됩니다. 
이러한 수정은 함수 호출 후에도 지속됩니다.

두 번째 함수의 경우 std::string sen을 값으로 받기 때문에, 
함수 내에서 문자열을 수정하면 함수 내에서 새로운 문자열 객체가 생성되고, 
함수 호출이 끝나면 해당 객체가 소멸합니다. 따라서 호출자가 전달한 문자열 객체는 변경되지 않습니다.

두 함수 모두 start와 end 변수를 사용하여 문자열을 순회하면서 
대소문자를 구분하지 않는 회문(palindrome) 여부를 확인하는 것으로 보입니다. 
다만, 첫 번째 함수는 참조로 받기 때문에 문자열 객체 자체를 수정할 수 있으며, 
두 번째 함수는 값으로 받기 때문에 수정한 결과를 새로운 문자열 객체로 반환해야 할 수 있습니다.

실무에서는 함수 인자를 전달할 때 객체의 크기가 큰 경우에는 참조를 사용하는 것이 일반적입니다. 
이는 객체를 복사하는 대신 해당 객체에 대한 참조를 전달하기 때문에 메모리 사용량과 성능에 이점이 있습니다.

따라서, 첫 번째 함수의 방식인 std::string& sen 참조를 사용하는 방식이 더 효율적일 수 있습니다. 
하지만, 함수 내에서 문자열을 수정하지 않는다면 값으로 전달하여 
복사본을 생성하는 방식이 코드의 안정성과 가독성 면에서 더 좋을 수 있습니다. 
이러한 선택은 코드의 목적과 상황에 따라 다를 수 있습니다.

 

즉 지금과 같은 방식이라면 main문에서 cout으로 sen을 출력했을때 대소문자가 변경된 값을 나타난다는 것으로 보입니다.

C++에서는 포인터로 넘기는 경우도 있지만 포인터와 비슷한 역할을 하는 참고의 형식으로도 객체를 전달하고는 합니다.

 

---

자 그러면 이제 책에서 원하는 본론으로 돌아옵시다.

책에서 원하는 방식은 다음과 같습니다. 

알파벳만 비교해라. "," 라던가 ":" 라던가는 신경쓰지 말아라

그러면 한가지 과정이 전체 코드에서 추가가 되어야합니다.

 

알파벳만 남기고 소문자만 남기는 과정이 추가되어야합니다.

그래서 다음처럼 코드를 작성할 수 있습니다.

bool palindrome(std::string& sen) {
	std::string processing_sen = "";
	for (int i = 0; i < sen.length(); i++) {
		if (sen[i] >= 'A' and sen[i] <= 'Z') {
			processing_sen += sen[i] + 32;
		}
		else if (sen[i] >= 'a' and sen[i] <= 'z') {
			processing_sen += sen[i];
		}
	}

	int start = 0; int end = processing_sen.length() - 1;
	for (int i = 0; i < processing_sen.length() / 2; i++) {
		if (processing_sen[start] != processing_sen[end])
			return false;
		start++;
		end--;
	}
	return true; 
}

 

그러면 다음의 글을 입력했을 때 어떻게 되는지 확인을 해봅시다.

A Man, a Plan, a Canal, Panama

 

성공적으로 잡아내는 모습을 보입니다.

 

 

 

---

결국 책에서 설명하는 방법은 총 3가지 입니다.

1. 리스트 (C++이라면 벡터겠군요)로 변환하는 방법

2. Deque 자료형으로 해결하는 방법

3. 슬라이싱을 이용한 방법 이는 파이썬에서는 [:1] 처럼 쓸라이싱을 사용하고, 정규식을 통해서 해결하는 방법입니다. 이를 C++에서 어떻게 표현할 수 있을지는 ChatGPT를 통해 후에 해결해보도록 하겠습니다.

 

 

---

백준의 다른 풀이를 보면서 코드의 실력을 향상시키자!

---

 

백준의 boss403 님의 코드입니다. 

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

int main(void)
{
	int a;

	cin >> a;
	cin.ignore();

	while (a--)
	{
		string input;
		bool check = true;

		getline(cin, input);
		int size = input.length();
		for (int i = 0; i < size; i++)
		{
			input[i] = tolower(input[i]);
		}

		for (int x = 0; x < size / 2; x++)
		{
			if (input[x] != input[size - x - 1])
			{
				check = false;
				break;
			}
		}

		if (check)
			cout << "Yes\n";
		else
			cout << "No\n";
	}

	return 0;
}

tolower 를 사용하면 모든 대문자를 소문자로 한 번 에 변환시킬 수 있습니다. 굉장히 편리한 방법입니다.

그렇게 변환한 소문자들을 반까지만 맨앞과 맨끝을 비교했습니다. 

코드가 간결하고 깔끔합니다.

 

 

hyjk826님의 풀이입니다. 여기서 주목할건  auto라는 놈입니다.

using namespace std;

bool f(string& str){
    for(int i{0}; i < (int)str.size() / 2; ++i){
        if(str[i] != str[(int)str.size() - 1 - i]) return false;
    }
    return true;
}

int main(){
	fastio;
    int t;
    cin >> t;
    string str;
    getline(cin, str);
    while(t--){
        getline(cin, str);
        for(auto& c : str){
            if(c >= 'A' && c <= 'Z') c = tolower(c);
        }
        if(f(str)) cout << "Yes\n";
        else cout << "No\n";
    }
}

제 코드에서는 소문자로 변환하는 과정을 다음처럼 적었었습니다.

이 코드를 보시겠습니다.

for (int i = 0; i < sen.length(); i++) {
		if (sen[i] >= 'A' and sen[i] <= 'Z') {
			sen[i] = sen[i] + 32;
		}

이 코드를 auto를 사용하면 다음처럼 변환됩니다.

 

for (auto i  : sen){
	if (sen[i] >= 'A' and sen[i] <= 'Z') {
		sen[i] = sen[i] + 32;
	}

다음처럼 작성할 수 있습니다.

그러나 위 코드는 틀립니다.

 

잠시 파이썬 이야기를 해봅시다.

list = [a, b, c, d]

for i in list:
	print(i)

위 경우에 i는 a, b, c, d 가 출력됩니다.

 

그러면 C++로 작성된 코드도 1부터 들어가는게 나이라 sen의 sen[0]의 값부터 들어가게 됩니다. 그렇기에 이렇게 수정합니다.

 

for (auto & i  : sen){
	if (i >= 'A' and i <= 'Z') {
		i = i + 32;
	}

i를 수정하면 sen의 i번째가 수정됩니다.

 

그래서 매우 유용한 방법으로 위와 같은 코드 스타일을 사용할 수 있습니다.

 

auto  라는 키워드 하나로 C++이 python 스럽게 코드를 짤 수 있습니다.

네, auto는 C++11 이후 추가된 기능으로, 변수의 자료형을 컴파일러가 추론하도록 하는 키워드입니다. 
auto를 사용하면 변수의 자료형을 직접 지정하지 않아도 되므로, 코드를 간결하게 작성할 수 있습니다. 
또한 auto는 템플릿을 사용한 코드에서 매우 유용하게 사용됩니다.

auto를 실무에서도 자주 사용하는지는 사용자의 취향이나 프로젝트의 규칙에 따라 다르겠지만,
auto는 C++에서 지원하는 강력한 기능 중 하나이므로 적극 활용하는 것이 좋습니다. 
그러나, 자료형 추론에 따른 코드 가독성이 저하될 수도 있으므로, 
적절한 상황에서 사용하는 것이 좋습니다.

 

 

여기까지 팰린드롬에 대해 알아보았으며, 팰린드롬과 관련된 백준 문제를 2문제 정도 첨부하면서 마무리 하겠습니다.

 

 

 

1213번: 팰린드롬 만들기 (acmicpc.net)

1213번: 팰린드롬 만들기

 

 

4096번: 팰린드로미터 (acmicpc.net)

4096번: 팰린드로미터