https://www.acmicpc.net/problem/1213
1213번: 팰린드롬 만들기
첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.
www.acmicpc.net
소스코드
풀이
★ 문자의 개수가 홀수인 알파벳의 수가 2개 이상이면, 해당 문자열을 펠린드롬으로 만들 수 없습니다 ! 그렇기에 주어진 문자열 안의 각각의 알파벳이 몇번씩 등장하는 지 먼저 파악해야 합니다. 그 과정을 위해 딕셔너리를 만들어서 개수를 세아렸습니다
★ 위에서 만든 딕셔너리의 key, value를 읽으면서 만약 value값이 홀수이면 cnt를 1 증가시킵니다. 이 때 cnt가 2이상이면 펠린드롬을 만들 수 없기 때문에 I'm sorry hansoo를 출력하고 반복문을 종료합니다. 개수가 홀수인 알파벳을 발견했을 때 그 알파벳은 펠린드롬의 중앙에 오기 때문에 center라는 변수에 저장해줬습니다.
★ for ~ else ~ 구문을 사용하여 for문이 break 없이 정상적으로 동작했을 때의 경우를 만들어줍니다. 이러한 경우는 펠린드롬을 만들 수 있는 경우이며, 딕셔너리를 읽으면서 ans라는 변수에 알파벳 + (알파벳 개수 // 2)를 계속해서 더해줍니다. 이 과정은 center를 기준으로 왼쪽의 문자들을 만들어가는 과정입니다.
★ 위의 과정이 끝났을 때, 펠린드롬이 ABBCBBA라고 가정했을 때, ABB까지 만들 수 있습니다. 저희는 나머지 문자도 더해줘야 하는데, 나머지 문자는 center의 왼쪽 문자들과 같기 때문에 이를 뒤집어서 center 변수와 함께 더해줍니다 !
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 15904번: UCPC는 무엇의 약자일까? (Python) (0) | 2023.06.20 |
|---|---|
| [백준 알고리즘] 18310번: 안테나 (Python) (0) | 2023.06.20 |
| [백준 알고리즘] 1969번: DNA (Python) (0) | 2023.06.19 |
| [백준 알고리즘] 1343번: 폴리오미노 (Python) (0) | 2023.06.19 |
| [백준 알고리즘] 2847번: 게임을 만든 동준이 (python) (0) | 2023.06.19 |