[백준] 1213 팰린드롬 만들기 - 문자열(String) + 그리디(Greedy, 탐욕법) + 구현(Implementation) + StringBuilder + HASHMAP(해시맵) JAVA

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

1213번: 팰린드롬 만들기

코드설명

문자열 그리디 구현 StringBuilder를 활용하는 문제입니다.

 

문제로직입니다.

1. 각 알파벳의 개수를 int[] alphabet에 넣습니다. ( 알파벳이 개수는 26개 임을 활용하고, str.charAt(i) - 'A' 를 활용하여 int[] 형에 넣을 수 있습니다. )

2. 홀수인 알파벳의 개수를 구하고, 해당 알파벳의 위치를 구합니다.

3. 만약 홀수인 알파벳이 1개 이상이라면 팰린드롬은 불가능하니 중단시키고, 만약 홀수인 알파벳이 1개라면 주어진 알파벳의 개수가 홀수여야만 중간에 넣을 수 있습니다. 짝수라면 중간에 1개를 팰린드롬으로 만들지못합니다.

4. 알파벳 사전순으로 하기 위하여 처음 alphabet부터 순회하며 짝수인 알파벳일 경우 짝수씩 result값에 먼저 추가해줍니다.

5. 만약 alphaoddcnt == 1 이라면, 즉 홀수인 알파벳의 개수가 1개 존재한다면 가운데에 넣습니다.

6. 4번 과정에서 저장한 알파벳을 StringBuilder의 reverse함수를 사용하여 다시 넣으면 팰린드롬이 완성됩니다.

 

처음에 백트래킹에 팰린드롬을 구별하는 함수를 만들어서 진행했습니다.

하지만, 메모리초과 및 시간초과가 났습니다.

사실, 문제의 조건에 최대 50글자이기에 모든 조합을 완전탐색할경우 50 팩토리얼의 조합의 수가 나오기에 시간초과가 날 것 같다고 생각했지만, 한번 풀어보고 싶어서 풀어봤습니다.

해당 코드도 남겨두었습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int[] alphabet = new int[26];
	public static String str = "";
	public static int alphabetOddCnt = 0;
	public static int alphabetcenterIdx = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str = st.nextToken();
    	for(int i=0;i<str.length();i++) {
    		alphabet[str.charAt(i) - 'A']+= 1;
    	}
    	
    	for(int i=0;i<26;i++) {
    		if(alphabet[i] % 2 != 0) { //알파벳의 개수가 홀수일경우의 수를 더해줍니다.
    			alphabetcenterIdx = i;
    			alphabetOddCnt += 1; //알
    		}
    	}
    	
    	//만약 홀수인 개수가 1개 이상이라면, 불가능하다
    	//만약 길이가 짝수이면서 알파벳의 개수가 1개일경우라면, 알파벳을 가운데에 두지 못하므로 팰린드롬을 완성하지 못한다.
    	if(alphabetOddCnt > 1 || (alphabetcenterIdx == 1 && str.length() % 2 == 0)) {
    		System.out.println("I'm Sorry Hansoo");
    		return ;
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=0;i<26;i++) {
    		for(int j=0;j<alphabet[i] / 2; j++) {
    			sb.append( (char) (i + 'A') );
    		}
    	}
    	StringBuilder result = new StringBuilder(sb.toString());
    	if(alphabetOddCnt == 1) {
    		result.append((char) (alphabetcenterIdx + 'A'));
    	}
    	String answer = result.toString() + sb.reverse();
    	System.out.println(answer);

    }
}

 

 

백트래킹을 사용하여 메모리초과 및 시간초과가 나는 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static String str = "";
	public static Character[] tempStr;
	public static boolean[] visited;
	public static ArrayList<Character> arr = new ArrayList<>();
	public static HashSet<String> hashset = new HashSet<>();
	public static String answer = "";
	public static ArrayList<String> answerArr = new ArrayList<>();
	public static String tempStrValue = "";
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str = st.nextToken();
    	for(int i=0;i<str.length();i++) {
    		arr.add(str.charAt(i));
    	}
    	visited = new boolean[str.length()];
    	tempStr = new Character[str.length()];
    	Collections.sort(arr);
    	makeString(0);
    	Collections.sort(answerArr);
    	if(answerArr.size()  == 0) {
    		System.out.println("I'm Sorry Hansoo");
    	}else {
    		System.out.println(answerArr.get(0));	
    	}
    	

    }
	
	public static void makeString(int level) {
		if(level == str.length()) { //여기서 회문검사할것임.
			tempStrValue = "";
			for(Character a : tempStr) {
				tempStrValue += a;
			}
			
			if(hashset.contains(tempStrValue)) {
				return ;
			}
			hashset.add(tempStrValue);

			
			if(palindrome(0, str.length() - 1) == true) { //만약 회문이라면 해당 팰린드롭 출력하고 종료시킨다.
				answerArr.add(tempStrValue);
			}
			return ;
		}
		
		for(int i=0;i<str.length();i++) {
			
			if(visited[i] == false) {
				visited[i] = true;
				tempStr[level] = str.charAt(i);
				makeString(level + 1);
				visited[i] = false;
			}
		}
	}
	
	public static boolean palindrome(int start, int end) {
		while(start < end) {
			if(tempStr[start] == tempStr[end]) {
				start += 1;
				end -= 1;
			}else {
				return false;
			}
		}
		
		return true;
	}
	
	

}

 

HashMap을 활용한 코드입니다.

package Main;

import java.util.*;
import java.io.*;

public class Main {
    public static int N;
    public static String name;
    public static HashMap<Character, Integer> alphabet_hashmap = new HashMap<>();
    public static Stack<Character> stack = new Stack<>();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		name = st.nextToken();
        for(int i=0;i<name.length();i++) {
        	char alpha = name.charAt(i);
        	alphabet_hashmap.put(alpha, alphabet_hashmap.getOrDefault(alpha, 0) + 1);
        }
        
        palindrome();
        	
    }
    
    public static boolean palindrome() {
    	//홀수이든, 짝수이든 오직 하나의 단어만이 홀수의 개수로서 존재할 수 있다.
    	boolean isOddExist = false;
    	char oddNumber ='0';
    	for(char c = 'A'; c <= 'Z'; c++) {
    		if(alphabet_hashmap.containsKey(c) && alphabet_hashmap.get(c) % 2 == 1) {
    			//만약 주어진 입력에 홀수인 단어의 개수가 1개 초과라면, I'm Sorry Hansoo
    			if(isOddExist == true) {
    				System.out.println("I'm Sorry Hansoo");
    				return false;
    			}
    			oddNumber = c;
    			alphabet_hashmap.put(c, alphabet_hashmap.get(c) - 1);
    			isOddExist = true;
    		}
    	}
    	
    	//만약 홀수이고, 홀수인 단어가 한개라면,  
    	if(name.length() % 2 == 1) {
    		for(char c = 'A'; c <= 'Z'; c++) {
        		if(alphabet_hashmap.containsKey(c) && alphabet_hashmap.get(c) % 2 == 0) {
	    			int cnt = alphabet_hashmap.get(c);
	    			for(int i=0; i<cnt/2; i++) {
	    				System.out.print(c);
	    				stack.add(c);
	    			}
	    			alphabet_hashmap.remove(c);
        		}
    		}
    		
    		System.out.print(oddNumber);
    		while(!stack.isEmpty()) {
    			System.out.print(stack.pop());
    		}
    		
    	}
    	
    	//만약 짝수라면, 
    	else if(name.length() % 2 == 0) {
    		for(char c = 'A'; c <= 'Z'; c++) {
        		if(alphabet_hashmap.containsKey(c) && alphabet_hashmap.get(c) % 2 == 0) {
	    			int cnt = alphabet_hashmap.get(c);
	    			for(int i=0; i<cnt/2; i++) {
	    				System.out.print(c);
	    				stack.add(c);
	    			}
	    			alphabet_hashmap.remove(c);
        		}
    		}
        	while(!stack.isEmpty()) {
        		System.out.print(stack.pop());
        	}
    	}
    	return true;
    }
    

}