1-K

내 풀이(http://boj.kr/034ae8f94666485b9509a4f48c84e627) - 틀림

공유 소스 보기

---

1-K

1-k 1213 팰린드롬 만들기 문제를 풀어 보도록 하겠습니다.

일단 이 문제는 팰린드롬을 만들기 불가능하다면 sorry를 출력을 하고, 그게 아니면 팰린드롬을 만들어서 출력을 하는 거죠. 그리고 아스키 코드 순으로 오름차순으로 했을 때 가장 앞에 것을 출력하면 되는 문제입니다.

일단은 불가능한 경우가 있다고 했으니까 불가능한 경우가 뭔지를 생각을 해야겠죠. 어떤 경우에 불가능할까요?

바로 홀수가 2개 이상이면 좀 불가능하겠죠?

예를 들어서, ABAAA는 AABAA로 팰린드롬으로 만들 수 있는 반면, ABAC 라고 있을 때는 어떻게 하든 팰린드롬으로 만들기가 불가능하죠.

즉, 홀수 개가 2개 이상이면 불가능하겠구나 라고 생각을 하시는 거예요. 이거는 생각하기가 쉬워요.

일단은 팰린드롬이라고 했을 때 짝수 개가 쭉 나오면 괜찮겠죠. 그런데 홀수 개가 여러 개 나온다? BBBCCC인 경우 양끝이 같으면서 안에 거가 같으려면 어떻게 해도 안 만들어집니다.

이런 식으로 작게 작게 테스트 케이스를 만들어서 생각해보시는 거예요.

이런 식으로 작은 테스트케이스를 만들어봐도 충분히 안되는 경우의 수를 체크할 수 있으니까 이런식으로 작게 작게 일단 해보는 거예요.

생각으로 안되면 이런 식으로 직접 써보면서 불가능한 경우의 수를 찾아야 돼요.

지금처럼 이렇게 불가능한 경우의 수를 찾았다고 합시다. 홀수가 2개 이상이면 안된다고 해요. 그럼 저희는 이제 팰린드롬만 만들면 되겠죠.

일단은 문자를 받아서 이런 식으로 만들어 놔요. 문자별로 몇 개를 쓸 수 있는지 알기 쉽게 적어놓는 거죠.

일단 오름차순이니까 홀수 개인 C부터 붙이고, 그 다음에 앞 뒤에다가 B를 붙이고, 또 거기에 앞 뒤에다가 A를 이렇게 붙이면 되겠네요.

지금 보시면 제가 C를 첫 번째로 붙이고 B를 두 번째로 붙이고 A를 세 번째로 붙인 걸 볼 수가 있죠.

가장 ASCII 코드 상으로 가장 위에 있는 것, 그러니까 Z부터 이런 식으로 먼저 붙인 걸 볼 수가 있죠.

왜냐하면 끝에서부터 붙여야 이런 식으로 결국 A가 앞에 오는 오름차순이 되니까요. 팰린드롬을 만들 수 있다면, 오름차순으로 출력을 하라는 게 이 문제의 핵심이니까.

---

자 코드를 보면서 설명을 해보도록 할게요.

일단 코드를 보시면 Counting 배열이 있죠. 이제는 익숙하셔야 됩니다.

그래서 이렇게 Counting 배열로 문자를 카운팅을 해놔요.

카운팅을 해놓고 이 문자가 몇 개야? 하고 보는거죠.

지금 보시는 것처럼 창고에 제가 A가 4개, B가 2개, C가 3개 이렇게 만들어 놨죠. 이걸 기반으로 하는 거예요.

원래 문자의 순서는 상관이 없는 거죠. 이걸 기반으로 다시 재배열을 해야 되니까.

자 그러면 여기까지 왔어요. 그러면 제가 처음에 뭐라고 했죠?

Z부터 붙인다 라고 했죠? 큰 거부터 붙인다고 했습니다. 만약에 cnt[i]가 있다면, 그러니까 문자가 들어가 있는 거라고 했을 때 이런 식으로 붙일 겁니다.

& 1은 AND 1이라고 읽는데, 홀수라는 의미예요. % 2 == 1로 바꿔서 생각하면 됩니다.

즉, cnt[i] & 1 은 cnt[i] % 2 == 1 과 같은 거죠.

왜냐면 홀수는 이진수로 나타내면 1 0 이 아니라 1 1 이런 식으로 되거든요? 짝수는 무조건 1 1 0 이에요. 그러니까 짝수는 마지막 게 무조건 0으로 끝나고, 홀수는 1로 끝나요. 그래서 AND 연산자 1 이라고 하면, true 값이 되는 게 홀수다 라고 할 수 있습니다.

그래서 이 cnt[i]가 홀수이면서 홀수인 게 2개 이상이면 안된다고 했죠.

자 일단 홀수개인 거는 mid로 이렇게 설정을 해놔요. mid는 이따가 설명을 드릴게요.

그리고 flag를 ++해요. 그리고 cnt[i]를 --합니다.

그리고 나서 만약에 flag가 2개면 break를 거는 거죠.

flag가 2개면 이렇게 sorry를 출력하게 되는 겁니다.

그 다음에 이 반복문이 뭐냐면 붙이는 작업인 거예요. i가 Z부터니까

만들어지고 있는 게 ret이죠. 그래서 ret에다가 앞 뒤로 붙이는 거예요.

앞에다가 붙이고, 뒤에다가 붙이고 있죠.

이렇게 하면 앞뒤로 붙이니까 cnt[i] 두 개를 소모하게 되죠.

만약에 cnt[i]가 4개가 있다면, 한번 붙이고 또 한번 붙일 수 있죠. 그래서 j += 2가 증감식에 오게 됩니다.

그리고 아까 mid를 이렇게 정의했죠.

이건 왜 그러냐면, 홀수가 1개 들어오는 경우가 있어요. 이 문제는 홀수가 2개 이상이면 불가능하다라고 했으니까 홀수가 1개일 때는 괜찮은 거죠. ABA 이런 경우겠죠.

자 그럼 이 1개가 들어왔을 때는 어떻게 해야 되냐? 중앙에다 넣으면 되겠죠. 홀수가 들어온다? 중앙에다 넣으면 됩니다.

그래서 홀수 개가 있으면 이 mid를 정의하고, 이 mid를 나중에 ret.insert 해서 넣어주는 겁니다. 그리고 mid를 따로 빼줬으니까 cnt[i]--; 해준거죠.

그래서 로직이 참 중요해요. 결국에는 오름차순으로 해야 되기 때문에 Z부터 이렇게 붙였다 라고 하는 거, 그리고 입력받은 문자열의 문자가 몇 개있냐 이게 중요하기 때문에 counting 배열을 만들어서 했다는 것, 마지막으로 ret에다가 붙이는 로직까지 해봤습니다.