[백준] 1213 : 팰린드롬 만들기 (Greedy알고리즘, String.copyValueOf()) - JAVA

백준 알고리즘 분류 (그리디 알고리즘)

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

 

 

# 문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

 

# 예제

입력

AABB

 

출력 :  첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

ABBA

 

# 필요개념

해당 문제를 풀 때, 신경써야 하는 조건은 크게 두가지라고 생각했다.

 

1. 홀수개인 알파벳이 2개 이상이면 팰린드롬으로 바꿀 수 없다.

2. 정답이 여러개라면 사전순으로 출력한다.

 

2번 조건때문에 1개 이상 알파벳을 갖는 경우, 순차적으로 리스트에 담아주고 리스트에 들어있는 애들만 마지막에 배열에 넣어주었다. 이때, 홀수인 알파벳이 한개이면서, 그 알파벳의 개수 또한 한 개인 경우 (EX | DDCCA) 에는 한가운데에 넣어주어야 하기 때문에 리스트에서 삭제해주었다. 

 

이 과정을 거치게 되면 리스트의 가운데에 있는 원소들을 삭제해야 할 때가 많아서 ArrayList가 아닌 LinkedList를 사용하였다. 

 

 ✅LinkedList vs ArrayList

나는 보통 ArrayList를 사용했다. 그러나 성능적인 문제를 생각하여 해당 문제에서는 ArrayList가 아닌 LinkedList를 사용하였다. 

 

ArrayList는 배열형태의 리스트로, 중간 데이터를 삭제하면 뒤에 있던 데이터들을 한 칸씩 옮겨야 하지만, LinkedList는 가리키고 있는 주소만 변경해주면 되기 때문에 더 좋은 성능을 갖는다.

 

출처 : http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html 다

 

단순하게 데이터를 조회하는 경우에는 ArrayList를, 중간 데이터를 삭제해야 할때에는 LinkedList를 사용하는 것이 좋다.

 

 

✅ 리스트의 remove() 메소드

리스트의 메소드 중에서 remove는 2가지 종류를 가진다.

• 인자로 int형 데이터를 갖는 경우 : 인덱스로 인식해 해당 인덱스에 위치한 데이터를 삭제한다.
• 인자로 객체 데이터를 갖는 경우 : 해당 객체 자체를 찾아 삭제한다.

나는 리스트에 인덱스를 넣었기 때문에 중복되는 데이터가 없었다. 따라서 객체형을 넣어 데이터를 찾을 수 있었다.

이때 int를 박싱하기 위해 앞에 (Integer) 을 써주었다.

 

 

✅ String.copyValueOf() 메소드

나는 정답데이터를 char배열에 넣었기 때문에 String 타입으로 반환해주어야 했다. 그래서 char배열을 String으로 반환하는 메소드를 찾아보았다.

• String.valueOf(char[] arr)
• String.copyValueOf(char[] arr)

두 메소드의 차이는 없다고 하기 때문에 편한 것을 사용하면 된다!

 

# Code

package Programmers;

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

public class Mains {
    static int[] arr;
    static String input;
    static List<Integer> idxStored = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        arr = new int[26];
        for (int i = 0 ; i < input.length() ; i++) {
            arr[input.charAt(i) - 65]++; // A = 0, B = 1 ..
        }
        String ans = check();
        System.out.println(ans);
    }
    public static String check() {
        int oddCnt = 0;
        int oddIdx = 0;
        char[] ans = new char[input.length()]; // 정답배열 생성

        for (int i = 0 ; i < arr.length ; i++) {
            if (arr[i] % 2 == 1) { // 홀수인 거 찾기 -> 홀수인개 1개 넘으면 불가능
                oddCnt++;
                oddIdx = i;
            }
            if (arr[i] > 0) idxStored.add(i);
        }
        if (oddCnt > 1) return "I'm Sorry Hansoo";

        if (oddCnt == 1) {
            ans[input.length() / 2] = (char)(oddIdx + 65);
            if (arr[oddIdx] == 1) {
                idxStored.remove((Integer) oddIdx);
            }
        }

        int index = 0;
        for (int i = 0 ; i < idxStored.size() ; i++) {
            int idx = idxStored.get(i); // 2번 이상 들어간 애의 인덱스
            for (int j = 0 ; j < arr[idx] / 2 ; j++) {
                ans[index] = (char)(idx + 65);
                ans[ans.length - 1 - index] = (char)(idx + 65);
                index++;
            }
        }
        return String.copyValueOf(ans);
    }
}

 

# 결과