문제 링크
문제
티어: 골드 2
알고리즘: 그리디
입력
첫째 줄에 문자열 S가 주어진다. 이 길이는 최대 50이고, 알파벳 소문자로만 이루어져 있다.
출력
첫째 줄에 정답을 출력한다. 만약 불가능한 경우에는 -1을 출력한다.
풀이
만들 수 있는 안티 팰린드롬 문자열 중 사전순으로 가장 앞서는 것을 출력해야 한다.
안티 팰린드롬이 안되는 경우는 어떤 경우일까?
- 길이가 짝수인 경우는 가장 많은 문자의 수가 현재 문자열이 길이/2 + 1 이상인 경우 무조건 불가능하다.
- 길이가 홀수인 경우는 가장 많은 문자의 수가 현재 문자열이 길이/2 + 2 이상인 경우 무조건 불가능하다.
왜냐하면 대칭시켰을 때 같은 위치에 서로 다른 문자가 와야하는데, 같은 문자가 반 이상이면 무조건 하나 이상은 같은 문자가 되기 때문이다. (홀수는 가운데가 같아도 되기 때문에 조건이 약간 다름)
그 외의 경우는 무조건 안티 팰른드롬이 가능한데, 사전순으로 가장 앞서는 것을 출력해야 한다.
사전순으로 가장 앞서는 문자열을 만들기 위해서는 가장 앞에 사전순으로 가장 앞에 있는 문자를 배치해야 한다. 그리고 그와 짝이 되는 (길이 - 1 - i)의 인덱스에는 다른 문자를 배치해 줘야 하는데, 그러한 문자중 사전순으로 가장 뒤에 위치한 문자를 배치하는 것이 최선의 선택이 된다.
여기서 중요한 점은 계속 안티 팰린드롬이 될 수 있는지를 체크해야 한다는 것이다. 만약 안티 팰린드롬이 될 수 없는 경우 그 다음 사전순으로 뒤에 위치한 문자를 배치해야 한다. (뒤의 문자를 건드려야 최적 해를 구할 수 있다.)
왜냐하면 처음에는 안티 팰린드롬이 가능할지라도 덜 중복된 문자를 앞 뒤로 배치하다보면, 가장 많은 문자가 현재 남은 길이/2 + 1 이상이 되는 경우가 있기 때문이다.
또 중요한 점은 홀수인 경우는 가운데가 같아도 되기 때문에 이를 다르게 처리하는 게 중요하다. 그래서 나는 초기에 문자열의 길이가 홀수이면서, 가장 많은 문자의 수가 정확히 문자열의 길이/2 + 1인 경우는 해당 문자를 가운데의 배치해 줬다. 이후에는 짝수의 길이를 가졌기 때문에 똑같이 처리해 주면된다.
그리디 풀이의 시간 복잡도는 O(N^2)이다.
소스 코드
import java.io.*;
import java.util.*;
class Char implements Comparable<Char> {
int ind;
char c;
Char(int ind, char c) {
this.ind = ind;
this.c = c;
}
@Override
public int compareTo(Char o) {
return Character.compare(this.c, o.c);
}
}
class Info {
int ind, cnt;
Info(int ind, int cnt) {
this.ind = ind;
this.cnt = cnt;
}
}
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
boolean[] visited = new boolean[S.length()];
if(!posible(S, visited)) {
System.out.println(-1);
return;
} else {
Char[] chars = new Char[S.length()];
for(int i=0; i<S.length(); i++) {
chars[i] = new Char(i, S.charAt(i));
}
Arrays.sort(chars);
char[] answer = new char[S.length()];
if(S.length() % 2 == 1) {
Info result = findMaxChar(S);
if(S.length()/2 + 1 == result.cnt) {
answer[S.length()/2] = S.charAt(result.ind);
visited[result.ind] = true;
}
}
for(int i=0; i<S.length()/2; i++) {
int fCursor = 0;
while(visited[chars[fCursor].ind]) {
fCursor += 1;
}
answer[i] = chars[fCursor].c;
visited[chars[fCursor].ind] = true;
int bCursor = S.length() - 1;
while(true) {
if(!visited[chars[bCursor].ind]) {
visited[chars[bCursor].ind] = true;
if(posible(S, visited)) {
answer[S.length() - 1 - i] = chars[bCursor].c;
break;
} else {
visited[chars[bCursor].ind] = false;
}
}
bCursor -= 1;
}
}
if(answer[S.length()/2] == '\u0000') {
int cursor = 0;
while(visited[chars[cursor].ind]) {
cursor += 1;
}
answer[S.length()/2] = chars[cursor].c;
}
System.out.println(String.valueOf(answer));
}
}
static boolean posible(String S, boolean[] visited) {
HashMap<Character, Integer> map = new HashMap<>();
int leftSize = 0;
for(int i=0; i<S.length(); i++) {
if(!visited[i]) {
if(map.get(S.charAt(i)) == null) {
map.put(S.charAt(i), 0);
}
map.put(S.charAt(i), map.get(S.charAt(i)) + 1);
leftSize += 1;
}
}
int max = -1;
for(Map.Entry<Character, Integer> entry : map.entrySet()) {
if(max < entry.getValue()) {
max = entry.getValue();
}
}
if(leftSize % 2 == 0 && leftSize/2 < max) {
return false;
} else if(leftSize % 2 == 1 && leftSize/2 + 1 < max) {
return false;
}
return true;
}
static Info findMaxChar(String S) {
Info result = new Info(-1, -1);
HashMap<Character, Info> map = new HashMap<>();
for(int i=0; i<S.length(); i++) {
if(map.get(S.charAt(i)) == null) {
map.put(S.charAt(i), new Info(i, 0));
}
map.put(S.charAt(i), new Info(map.get(S.charAt(i)).ind, map.get(S.charAt(i)).cnt + 1));
}
int max = -1;
for(Map.Entry<Character, Info> entry : map.entrySet()) {
if(result.cnt < entry.getValue().cnt) {
result = new Info(entry.getValue().ind, entry.getValue().cnt);
}
}
return result;
}
}