1213 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

** 완성본 코드를 보시고 싶으신 분은 아래 <최종 완성본> 코드만 보시면 됩니다!

 

아이디어 구현(중도 포기)

 

일단 input[] 배열에 예제 입력된 것을 string으로 담는다.

예시) input = {A,A,B,B,D,D,D,B,B,A,A}

그 다음 ArrayList에 input[] 요소들을 담아서, 그 크기가 유동적으로 변할 수 있게 한다. 

(왜냐하면, 중복되는 글자들을 지워나갈 것이므로)

 

만약 ArrayList[0](=A) 번째 요소랑 ArrayList[2](=A),[3](=B),[4](=B) 요소를 비교해서 같다면

count를 증가시키고 그 요소들을 제거해버린다.

즉, ArrayList[0]=A=ArrayList[1]=ArrayList[9]=ArrayList[10]

count 는 초기에 1로 설정해놨고, 이 경우는 총 count = 4

 

그리고 이 count는 alphabet이라는 배열에 집어넣는데

alphabet 배열은 알파벳 개수(26) 크기로 만들어서 (alphabet[0]는 A에 대응되고, [1]은 B에 대응되고..)

만약 ArrayList[0]이 A이면 alphabet[0]에다가 그 count값(4)을 입력한다.

 

그렇게 문자들의 중복 횟수를 alphabet 배열에 계산해서 넣는다.

 

팰린드롬을 만드려면 글자개수가 짝수개여야 하는데, 단 한 번은 홀수번 가능하다. 

그 글자를 팰린드롬 글자의 가운데에 넣으면 상관없기 때문

예를 들어 AABBDDDBBAA 이럴 경우 팰린드롬이 가능하다.

 

그래서 만약 alphabet 배열 값 중에 홀수개인 경우가 1개라면 위의 경우처럼 괜찮지만

2번 이상이라면 불가능 하므로 I'm Sorry Hansoo 를 출력하게 만든다.

 

이렇게 하고 나면 

alphabet[0]은 A의 개수를 의미하고 alphabet[1]은 B의 개수를 의미한다.

그 후에는 result라는 배열을 만들어서, alphabet[] 배열과 대응시켜서 결과물을 출력한다.

(그런데 또 문자열을 출력할 때 알파벳순서로 출력하라고 했으므로 alphabet[]배열 순서대로 그냥 출력하면 된다.)

 

AABBDDDBBAA

여기서 볼 수 있듯이 A는 총 4개 이지만, 가운데 글자 D를 중심으로 앞쪽에 A는 2글자, 뒤쪽에도 2글자씩 표현하고 있다.

 

alphabet[0]은 A의 개수(4)를 의미하는데, 팰린드롬을 만드려면 팰린드롬 글자의 반의 앞쪽에는 (A개수/2)개를 표현하고

뒤쪽에는 또 (A개수/2) 개를 표현해야 하므로,

 

alphabet[0]/2 만큼만 result[]배열에 A를 집어넣는다.

이렇게 alphabet[25]까지 다 하면 된다.

 

그런데, 앞에서 말했듯이 한 글자는 홀수개가 가능해서 만약 alphabet[i]가 홀수라면 그 글자는 mid 변수에 하나 빼놓고 

그 나머지를 /2 해서 위처럼 result[] 배열에 넣으면 된다.

 

그러면 result[]배열에 팰린드롬 글자의 반쪽이 완성되게 된다.

즉, AABBD 이만큼.

그리고 mid변수(D)가 있다면 result에 mid변수를 붙인다음 AABBDD,

result[]의 값을 거꾸로 돌려서 또 result[]에 붙여주면 AABBDDDBBAA

팰린드롬 글자가 완성된다.

 

..이렇게 완성하려고 했으나.. 위의 코드블록에 표시한 --------------** 아래부터 완성이 잘 안된듯 하다

즉, alphabet[]의 글자들을 result[] 글자로 표현하는데부터 막혔다.

그런데 계속 붙잡고 있으면 시간이 너무 많이 소요될 것 같아서 다른 사람의 코드를 참조하기로 했다.

 

<아래 코드는 위에서 설명했던 내용 관련 코드>

 

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




public class Main {

	  public static void main(String[] args) throws IOException {

		  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input[]= br.readLine().split("");
		ArrayList<String> data = new ArrayList<>();
	
		
		for(int i=0; i<input.length;i++) {
			data.add(input[i]);
		}
			
		
		int alphabet[] = new int [26]; 
	
		for(int i=0;i<data.size();i++) {
			String s = data.get(i);
		
			int count =1;
			for(int j=i+1;j<data.size();j++) {
				if(data.get(j).equals(s)) {
					count++;
					data.remove(j);
					j--;
				}else {
					continue;
				}
				}
			
				int order = (int) s.charAt(0) -65;
				alphabet[order]=count;
			}
			
		
	
		int odd =0;
		for(int i=0;i<26;i++) {
		
			
			if(alphabet[i]%2==1) {
				odd++;
				if(odd==2) {
					System.out.println("I'm Sorry Hansoo");
				}
			}
			
			//--------------**
			char result[]= new char [50];
			char mid;
			
			
			for(int k=0; k<26;k++) {
				if(alphabet[k]!=0) {
					if(alphabet[k]%2!=0) {
						mid=(char)(k+65);
					}
					
					int num = alphabet[k]/2;
					while(num -->0) {
					for(int e=0;;e++) {
					result[k+e]=(char)(k+65);
				}}
			}
			}			
				}
			}
		}

<최종 완성본>

아래 참고 자료의 블로그를 참고해서 작성했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	  public static void main(String[] args) throws IOException {

		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		  String input = br.readLine();
		  
		  int alphabet[] = new int [26];
		 
		  for(int i=0; i<input.length();i++) {
			  alphabet[input.charAt(i)-65]++;
		  }
		  
		  int count =0;
		  int mid =0;
		  for(int i=0;i<26;i++) {
			  if(alphabet[i]%2!=0) {
				  count++;
				 mid=i;
			  }
		  }
		  
		  if(count>1) {
			  System.out.println("I'm Sorry Hansoo");
			return;
		  }
		  
		  StringBuilder make = new StringBuilder();
		  
		  for(int i =0; i<26;i++) {
				  for(int j=0; j<alphabet[i]/2;j++) {
				  make.append((char)(i+65));
			  } 
		  }
		  
		 StringBuilder result = new StringBuilder(make.toString());
		  if(count==1) {
			  make.append((char)(mid+65));
		  }
		  
		  System.out.println(make.toString()+result.reverse());
				}
			}

 

alphabet[] 배열을 만들어서 입력된 글자들의 글자수를 배열 값으로 넣는다.

 

즉, AABBC를 입력받았다면

alphabet[0] = 2 (A글자 갯수)

alphabet[1]=2  (B글자 갯수)

alphabet[2]=1 (C글자 갯수)

 

 

그 후 alphabet[]배열의 값이 홀수인지 따진다. 그래서 그 경우만큼 count수를 증가시킴 

글자수가 홀수인 경우는 한 번은 가능하지만, 두번부터는 불가능하기 때문

(AABBC는 ABCBA으로 가능하지만,  

AAACBB는 불가)

 

그리고 홀수인 경우 한 번은 가능하기 때문에 그 알파벳의 인덱스를 mid변수로 받는다

 

그 다음 StringBuilder를 이용해서 글자를 만드는데,

i=0일때, j=0이면(입력값이 AABBC라면 j는 alphabet[0]/2=1 즉, j<1이므로 j=0일때만 for문 사용)

그래서 make StringBuilder에다가 (char)(i+65) 즉, 알파벳 A를 붙인다. (1번)

 

i=1일 때도 마찬가지로 StringBuilder에다가 B를 1개 붙임

i=2일때는 C를 의미하는데, alphabet[2]/2=0이다. 왜냐하면 j가 int형이라서

그래서 얘는 StringBuilder에 붙지 않고 

 

최종적으로 AB가 완성되서 for문을 나옴

 

그리고 count==1인 경우, 즉 글자 C는 count가 1이라서,

여기서 붙게 됨

즉, StringBuilder에 ABC가 완성됨

이렇게 한 다음 result의 reverse즉, BA를 붙여주면 완성

 

기억하기 ) 

 for(int j=0; j<alphabet[i]/2;j++) {
이 부분 코드가 너무 마음에 들었다.                  

 

 

 

주의 하기 )

count>=1 인 경우는 글자수가 홀수개인 경우가 1개 이상인 경우인데,

1개일 경우에는 팰린드롬을 만들 수 있지만, 2개부터는 만들 수가 없다. 

그래서 count>1 인 경우는 그냥 i'm sorry Hansoo를 출력하고 끝내야 하는데,

 

코드에서 만약 if (count>1) 부분에서 return; 안 하면

count>1인 경우도 아래 코드(팰린드롬 글자를 만듦)들을 실행하기 때문에 오류가 난다. 

 

참고 자료 : 

https://broship.tistory.com/134?category=845145