[C++] 백준(BOJ) 10988 팰린드롬인지 확인하기

 

풀이1 (내 풀이)

• string의 가운데 인덱스를 기준으로 양 옆의 문자가 같으면 continue, 다르면 break후 0을 출력한다
• 이때, 가운데 인덱스의 기준이 string의 길이가 홀수, 짝수인 경우가 다르므로 이를 고려하여 가운데 인덱스를 정한다. 

#include <iostream>
#include <string>
using namespace std;
/*
* string의 길이가 홀수인 경우 
* 가운데 문자의 인덱스 k 부터 시작하여 for문으로 
  arr[k-i] == arr[k+i]인지 확인후 i++ 하여 한번이라도 아니면 멈추고 0을 출력한다.
* string의 길이가 짝수인 경우
* string 길이 반 = k 라 하여 for문으로
  arr[k-i] == arr[k+1+i]인지 확인후 i++하여 똑같이 시행한다.
*/
int main() {
	string s;
	int k;
	int i = 0;
	cin >> s;
	if (s.length() % 2 != 0) //s 길이가 홀수인 경우
	{
		k = s.length() / 2;
		while (k - i >= 0)
		{
			if (s[k - i] != s[k + i]) {
				cout << "0";
				break;
			}
			else {
				i++;
				continue;
			}
		}
		if (k - i < 0)
			cout << "1";
	}
	else //s 길이가 짝수인 경우
	{
		k = s.length() / 2 - 1;
		while (k - i >= 0)
		{
			if (s[k - i] != s[k + 1 + i]) {
				cout << "0";
				break;
			}
			else
			{
				i++;
				continue;
			}
		}
		if (k - i < 0)
			cout << "1";
	}
	
		
	return 0;
}

시간복잡도:
문자열의 길이를 n이라하면, 대략 n/2 만큼 while문 내부의 코드를 시행하므로 O(n/2) = O(n)

 

풀이2 (다른사람)

• 함수를 써서 코드의 복잡성을 줄였다.
• string s의 길이가 홀수/짝수인지에 상관없이, s[i] 와 s[len-1-i] 를 i =0 부터 비교할 수 있다.

#include <iostream>
using namespace std;

bool isPalindrome(string s){
	int len = s.length();
    for (int i =0; i< len/2; i++){
    	if (s[i] != s[len-1-i]) {
        	return 0;
         }
     }
     return 1;
}

int main(){
	ios_base::sync_with_stdio(false); //두 표준 입출력 동기화 해제
    
	string str;
     cin >> str;
     cout<<isPalindrome(str);
	return 0;
}

이때, ios_base::sync_with_stdio(false); 에 대해서는 다음 포스트에서 다룬다.

---