[C언어 백준] 실버 4/ 1213번 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
#include <string.h>
#include<stdbool.h>
 
 
 
 
 
 
int main() {
 
    char c[51];
    int alpha[26] = { 0 };
    scanf("%s", c);
    
 
    int lenStr = strlen(c);
 
    for (int i = 0; i < lenStr; i++) {
        alpha[c[i] - 'A']++;
    }
    
    //홀수 일때 가운데를 고려
    int count = 0;
    char mid=NULL;
    for (int i = 0; i < 26; i++) {
        if (alpha[i] % 2 != 0) {
            mid = i+'A';
            count++;
            alpha[i]--;
 
        }
    }
 
    if (count == 0) {
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < alpha[i] / 2; j++) {
                printf("%c", i + 'A');
            }
        }
 
        for (int i = 25; i >= 0; i--) {
            for (int j = 0; j < alpha[i] / 2; j++) {
                printf("%c", i + 'A');
            }
        }
    }
    else if (count == 1) {
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < alpha[i] / 2; j++) {
                printf("%c", i + 'A');
            }
        }
        printf("%c", mid);
 
        for (int i = 25; i >= 0; i--) {
            for (int j = 0; j < alpha[i] / 2; j++) {
                printf("%c", i + 'A');
            }
        }
 
    }
    else {
        printf("I'm Sorry Hansoo");
    }
    
    
}
 

 

이 문제에 거의 3일을 시달렸다.. 반례를 못찾겠어서 정말 괴로웠다. 결국 내가 쓴 코드는 끝까지 틀렸습니다였고 다른 사람들이 쓴 코드를 보고 다시 아이디어를 정립해봤다.

 

1. 홀수로 연속된 알파벳이 홀수개이면 안된다.

AABBB 는 홀수로 연속된 알파벳 B가 3개가 딱 하나 있기 때문에 ABBBA로 팰린드롬이 가능하지만

AABBBCCC는 얘는 홀수로 연속된 알파벳이 B,C 총 2개가 있기 때문에 팰린드롬을 만들수 없다. 

 

2. 홀수로 연속된 알파벳은 무조건 가운데 한자리를 차지한다.

오히려 이게 실버 난이도이다 싶은게 아무리 홀수로 연속된 알파벳이 5개,7개,9개.. 등등이 있어도 결국에는 가운데에는 한자리만 차지한다. 

ABBBA 라던지 ABBBCBCBBBA 라던지 결국에는 홀수로 연속된 알파벳은 가운데 한자리만 신경써주면 된다.

 

그래서 너가 썼던 코드는?

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include<stdbool.h>
 
 
 
 
 
 
int main() {
 
    char c[51] = { 0 };
    int alpha[26] = { 0 };
    scanf("%s", c);
    int odd = 0;//홀수가 두개이상이면 안됨
    bool res = true;
    //만약에 연속되는 수가 홀수면 처음 중간 끝
    //연속되는 수가 짝수면 양끝만
 
    
    int lenStr = strlen(c);
 
    
    for (int i = 0; i < lenStr; i++) {
        if ('A' <= c[i] && c[i] <= 'Z') {
            alpha[c[i] - 'A']++;
        }
        
    }
 
    
    
    int arr[51] = { 0 };
    int midLen = lenStr / 2;
    int pointer = 0;
 
    for (int i = 0; i < 26; i++) {
 
        if (odd > 1) {
            res = false;
        }
        else {
 
            if (alpha[i] > 0) {
                if (alpha[i] % 2 == 1) {
                    odd++;
                    int std = (int)(alpha[i] / 2);
                    for (int j = 0; j < std; j++) {
                        arr[pointer + j] = i+65;
                        arr[lenStr - (pointer + j) - 1] = i+65;
                    }
                    //무조건 중간에 가는건 하나만 가능 혹은 홀수 이런건 딱 하나의 케이스만 가능 odd에서 걸러지니까!
                    //ABB 하면 왜 A만 나올까
                    arr[midLen] = i+65;
                    pointer += std;
                }
 
                }
                if (alpha[i] % 2 == 0) {
                    int std = alpha[i] / 2;
                    for (int j = 0; j < std; j++) {
                        arr[pointer + j] = i+65;
                        arr[lenStr - (pointer + j) - 1] = i+65;
                    }
                    pointer += std;
 
 
                }
 
            }
            
 
            
        }
 
    
 
    if(!res) {
        printf("I'm Sorry Hansoo\n");
    }
    else {
        for (int i = 0; i < lenStr; i++) {
            printf("%c", arr[i]);
        }
    }
    
    
    
}

 

도대체 어디서 틀린건지 모르겠다. 소문자도 판별하고, ABB 같은 반례도 통과했는데..

 

혹시 이 글을 보신 분 중에 틀린부분을 찾으셨다면 댓글로 알려주세요..!ㅜㅜㅜ