[백준 / #1213 / C++] 팰린드롬 만들기

이번 문제는 팰린드롬 만들기 즉, 회문(palindrome) 만들기 문제이다.

 

알고리즘 대회에서 자주 나오고 자주 보이는 회문 문제이다!

 

백준 실버3 문제로 배정되어있다.

 

이하는 편의상 팰린드롬을 회문으로 작성하겠다.

 

 

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

1213번: 팰린드롬 만들기

 

 

 처음에는 전에 백트래킹(backtracking)으로 palindrome을 구현한 경험이 있기 때문에 해볼까 하였지만 백트래킹을 재귀

 

로 구현하는 걸 좋아하는 나로서는 생각하기 힘들기도 했고, 문제에서 주어진 숫자도 적고 오히려 재귀로 구현하면 더 많은

 

경우의 수를 계산하게되어 시간복잡도만 늘어나는 것 같아 도중에 방향을 바꿨다.

 

 

 

그리하여 생각한 방법이 그리디 알고리즘이다. (그리..그리)

 

그리디 알고리즘에 대해 간단하게 설명하자면 미래를 생각하지 않고 지금 이 순간에 최적의 선택을 하며 진행해나가 답을

 

도출해내는 알고리즘이다.

 

 

 

 그리디 알고리즘을 사용한 이유는 문제에서 우선 여러 경우의 수가 있다면 사전 순으로 출력한다고 하였다. 그러면 사전

 

순이 아닌 회문(palindrome)은 정답이 아니기 때문에 그리디 알고리즘의 취지인 미래를 생각하지 않고 현재에서 최선의 선

 

택을 하는 것이 적합하다 생각했다. 후를 생각하지 않아도 되는 이유는 회문(palindrome)의 특성상 뒤에는 reverse된 문자

 

열이 오기 때문에 자동으로 완성되게 된다. 따라서 회문을 이루는 문자열의 앞쪽에서 사전순이기 때문에 최선의 선택을 해

 

가며 문자열을 완성시키면 된다고 생각했다.

 

 

따라서 완성시킨 코드는 다음과 같다.

 

 코드에서 cnt함수의 역할은 입력된 문자열에서 각각의 알파벳의 나타난 횟수를 세고 벡터에 저장한다.

 

각각의 문자의 횟수를 세기 편하게 하기 위해 C++ STL algorithm 헤더에 있는 sort 함수를 사용하여 사전 순으로 먼저 정렬

 

해주었다. 이렇게 정렬되었다면 문자열에서 다음 문자와 같은지 체크하며 같다면 count를 +1 해주고 다르다면 마찬가지로

 

count를 +1 해주고 문자의 횟수를 저장해두는 벡터인 cnt_alphabet에 저장한 후 다시 count를 0으로 돌려준다. (지금 쓰다

 

가 깨달은 사실이 count++ 가 중복되니까 바깥으로 빼줘서 코드를 줄일 수 있었다..ㅠㅠ 다음부터는 조금 더 면밀히 살피겠

 

다 ㅠㅠ)

 

  이렇게 문자가 나타난 횟수를 모두 세주었다면 이제 회문을 만들어나갈 차례이다. 사전 순으로 문자를 세주었으므로 여기

 

여기서도 그냥 차례대로 문자를 더해주면 된다. 이 말이 무슨 말이냐, cnt_alphabet에 저장한 횟수가 어차피 사전 순이기 때

 

문에 천천히 이 벡터의 앞에서부터 더해주면 된다. 회문의 특성에 대해 생각해보자. 회문은 앞과 뒤에 한 번씩 문자가 똑같

 

이 나타나야 하므로 문자열이 나온 횟수를 / 2  한 만큼 문자를 더해주면 된다. 그런데 여기서 회문이 불가능한 경우는 문자

 

가 짝수(even number)만큼 나오면 모두 가능하지만 홀수(odd number)만큼 나오는 문자가 2개 이상이면 회문을 만들 수 없

 

다. 따라서 flag라는 정수형을 하나 만들어주고 odd number가 나오면 flag를 odd number가 나온 인덱스로 바꿔준다.

 

여기서! flag가 이미 -1이 아닌 다른 수라면 그 전에 odd number가 한 번 발생했다는 의미이고, 이는 곧 회문을 만들 수 없음

 

을의미한다. 따라서 flag를 -3으로 바꿔주고 반복문을 종료한다. 그렇게 반목문 속에서 / 2 해준 만큼 string에 더하고

 

cnt_alphabet 또한 / 2  해주고 새로 저장한다. 이렇게 문자열을 모두 더한 후 종료하고, odd number가 발생한 인덱스를 가

 

지고 있는 flag의 인덱스에 해당하는 문자를 더해주고 그 뒤에 반복문을 통해 reverse로 벡터를 돌며 회문을 완성한다.

 

 

이렇게 코드가 완성되었다.

 

최대한 자세하게 설명하려고 하다 보니 글의 비율이 압도적으로 많은 것 같다 ㅠㅠ 설명을 안한 부분은 코드에 주석으로 달

 

아놨으니 한 번씩 확인하면 된다!