[Baekjoon] 1213_팰린드롬 만들기

Silver III

문제(출처: https://www.acmicpc.net/problem/1213)

---

< 팰린드롬 만들기 >

 

문제 풀이 

 

팰린드롬이 가능한지 확인하기 위해 주어진 문자열에서 각 알파벳 개수를 센다.

짝수일 때 각 알파벳이 홀수개가 하나라도 있다면 팰린드롬을 만들 수 없다. 또한, 홀수일 때 각 알파벳이 홀수개가 여러 개 있다면 팰린드롬을 만들 수 없다. 이 조건을 먼저 확인해 준다. 

위의 조건을 통과하면 팰린드롬을 만들어준다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class _1213_ { // 팰린드롬 만들기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		String str = bf.readLine();

		HashMap<Character, Integer> map = new HashMap<>();
		ArrayList<Character> list = new ArrayList<>();

		for (int i = 0; i < str.length(); i++) {
			char x = str.charAt(i);
			if (!map.containsKey(x)) {
				map.put(x, 1);
				list.add(x);
			} else {
				map.replace(x, map.get(x) + 1);
			}
		}

		Collections.sort(list);

		boolean flag = false;
		char a = ' ';
		boolean result = false;
		for (char x : map.keySet()) {
			if (map.get(x) % 2 != 0) {
				if (!flag) {
					flag = true;
					a = x;
				} else {
					result = true;
					break;
				}
			}
		}

		if (str.length() % 2 == 0 && flag) {
			result = true;
		}

		String answer = "";

		if (!result) {
			char arr[] = new char[str.length()];
			int front = 0, back = str.length() - 1;

			for (char x : list) {
				while (map.get(x) > 1) {
					arr[front++] = x;
					arr[back--] = x;
					map.replace(x, map.get(x) - 2);
				}
			}
			if(str.length()%2!=0) {
				arr[front] = a;
			}

			for (char x : arr) {
				answer += x;
			}
		}

		if (result) {
			System.out.println("I'm Sorry Hansoo");
		} else {
			System.out.println(answer);
		}
	}
}

 

Main

변수)
str : 영어 이름
map : 각 알파벳 개수
list : 존재하는 알파벳
flag : 홀수개의 알파벳이 있는지 여부
a : 홀수개 알파벳
result : 홀수개의 알파벳이 2개 이상인지 여부
answer : 정답
arr : 팰린드롬 정답 배열
front, back : arr 배열 index

 

- 영어 이름(str) 입력

- 입력받은 문자열(str)에 포함된 알파벳 개수 세기

- 문자열(str)에 포함된 알파벳을 사전순으로 정렬

- 알파벳 개수 센 map을 순환하면서 홀수개가 있는지 확인

: 홀수개가 하나 있다면 그 값도 저장(a)

: 홀수개가 여러 개라면 문자열의 길이와 상관없이 팰린드롬을 만들 수 없음

- 문자열(str)의 길이가 짝수이고 홀수개인 알파벳이 있다면 팰린드롬을 만들 수 없음

- 팰린드롬을 만들 수 있는 조건이라면(result)

: 위에서 알파벳 사전순으로 정렬(list) 한 값을 순서대로 확인하면서 앞 뒤로 값 채우기

: 입력받은 문자열의 길이가 홀수라면 위에서 저장해 둔 값(a)을 가운데에 채우기

: 배열 -> 문자열 변환

- result 여부에 따라 불가능 문자열 출력 or 팰린드롬 출력

---

---