길이가 n인 문자열 str이 주어졌을 때, 문자열의 모든 요소가 회문을 형성할 수 있도록 각 요소의 위치를 출력하고, 회문을 만들 수 없다면 화면에 "No palindrome"이라는 메시지를 출력해야 합니다.
회문(Palindrome)이란?
회문은 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어 또는 문자열을 의미합니다. 대표적인 예로 MADAM, racecar 등이 있습니다.
일반적으로 어떤 단어나 문자열이 회문인지 판별하려면, 해당 문자열을 뒤집은 결과를 별도의 문자열에 저장한 뒤 원본과 비교하여 두 값이 같으면 회문으로 판단합니다. 하지만 이 문제는 단순히 회문 여부만 확인하는 것이 아니라, 주어진 단어나 문자열이 회문이 되도록 만드는 배열 순서를 직접 출력해야 합니다.
예를 들어 str = "tinni"라는 문자열이 있다면, 이를 intni 또는 nitin으로 재배열할 수 있습니다. 이때 인덱스는 1부터 시작하며, 결과는 2 3 1 4 5 또는 3 2 1 5 4 중 하나를 반환하면 됩니다.
위 문제는 아래 예시와 같은 방식으로 해결할 수 있습니다.
예시
Input: string str = "baa" Output: 2 1 3 Input: string str = "tinni" Output: 2 3 1 4 5
알고리즘
void printPalindromePos(string &str)
START
STEP 1: DECLARE vector<int> pos[MAX]
STEP 2: DECLARE AND ASSIGN n WITH LENGTH OF str
STEP 3: LOOP FOR i = 0 AND i < n AND i++
pos[str[i]].push_back(i+1)
END LOOP
STEP 4: SET oddCount = 0
STEP 5: DECLARE oddChar
STEP 6: LOOP FOR i=0 AND i<MAX AND i++
IF pos[i].size() % 2 != 0 THEN,
INCREMENT oddCount BY 1
SET oddChar AS i
END IF
END FOR
STEP 7: IF oddCount > 1 THEN,
PRINT "NO PALINDROME"
STEP 8: LOOP FOR i=0 AND i<MAX AND i++
DECRLARE mid = pos[i].size()/2
LOOP FOR j=0 AND j<mid AND j++
PRINT pos[i][j]
END LOOP
END LOOP
STEP 9: IF oddCount > 0 THEN,
DECLARE AND SET last = pos[oddChar].size() - 1
PRINT pos[oddChar][last]
SET pos[oddChar].pop_back();
END IF
STEP 10: LOOP FOR i=MAX-1 AND i>=0 AND i--
DECLARE AND SET count = pos[i].size()
LOOP FOR j=count/2 AND j<count AND j++
PRINT pos[i][j]
STOP
알고리즘 동작 원리
- 위치 저장: 각 문자가 나타난 위치(1부터 시작)를 문자별 벡터에 저장합니다.
- 홀수 개 문자 검사: 홀수 번 등장한 문자의 개수를 셉니다. 회문이 되려면 홀수 개로 등장하는 문자는 최대 하나여야 합니다.
- 예외 처리: 홀수 개로 등장하는 문자가 2개 이상이면 "NO PALINDROME"을 출력합니다.
- 전반부 출력: 각 문자의 절반을 회문의 전반부에 배치합니다.
- 가운데 처리: 홀수 개로 등장한 문자가 있다면 그중 하나를 회문의 가운데에 놓습니다.
- 후반부 출력: 나머지 절반을 역순으로 출력하여 회문의 후반부를 구성합니다.
이 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 사용 가능한 최대 문자 수
const int MAX = 256;
void printPalindromePos(string &str){
// 주어진 문자열에서 각 문자의 모든 위치를 삽입
vector<int> pos[MAX];
int n = str.length();
for (int i = 0; i < n; i++)
pos[str[i]].push_back(i+1);
/* 홀수 개 문자의 수를 찾음. O(n) 소요 */
int oddCount = 0;
char oddChar;
for (int i=0; i<MAX; i++) {
if (pos[i].size() % 2 != 0) {
oddCount++;
oddChar = i;
}
}
/* 회문은 홀수 개 문자를 1개 초과하여 포함할 수 없음 */
if (oddCount > 1)
cout << "NO PALINDROME";
/* 회문 전반부의 위치 출력 */
for (int i=0; i<MAX; i++){
int mid = pos[i].size()/2;
for (int j=0; j<mid; j++)
cout << pos[i][j] << " ";
}
// 홀수 개 문자 하나를 고려
if (oddCount > 0){
int last = pos[oddChar].size() - 1;
cout << pos[oddChar][last] << " ";
pos[oddChar].pop_back();
}
/* 회문 후반부의 위치 출력 */
for (int i=MAX-1; i>=0; i--){
int count = pos[i].size();
for (int j=count/2; j<count; j++)
cout << pos[i][j] << " ";
}
}
int main(){
string s = "tinni";
printPalindromePos(s);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
2 3 1 4 5