문자열을 적절히 쪼갠 후 하나로 합칠 때, 사전상으로 가장 앞에 오는 단어를 구하는 문제이다.
한 문자내의 쪼갠 문자 순서는 바뀌면 안된다
먼저 아이디어는 각 단어를 가리키는 포인터가 각각 존재하며,
맨 앞부분만 서로 비교했을 때 가장 작은 값을 stringbuilder에 하나씩 붙인다.
처음에는 단순히 사전순, 길이순으로 정렬해서 풀었는데, 이 경우는 ABCCC, BACCC인 경우 ABABCCCCCC 예외케이스가 나온다.
이는 BAA, BA 테스트 케이스를 해결하기 위해 문자열의 길이를 함께 봤기 때문에 생긴 예외케이스이다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<String> string = new ArrayList<String>();
int index[] = new int[n];
int length[] = new int[n];
PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
for (int i = 0; i < n; i++) {
string.add(in.next());
}
string.sort(Comparator.comparing(String::length).reversed().thenComparing(String::compareTo));
for (int i = 0; i < n; i++) {
queue.add(new Alphabet(i, string.get(i).charAt(index[i])));
length[i] = string.get(i).length();
}
StringBuilder sb = new StringBuilder("");
while (!queue.isEmpty()) {
Alphabet alphabet = queue.poll();
sb.append(alphabet.ch);
int nextIndex = alphabet.index;
if (index[nextIndex] < length[nextIndex] - 1) {
index[nextIndex]++;
queue.add(new Alphabet(nextIndex, string.get(nextIndex).charAt(index[nextIndex])));
}
}
System.out.println(sb.toString());
}
}
class Alphabet implements Comparable<Alphabet> {
int index;
char ch;
int length;
public Alphabet(int index, char ch) {
this.index = index;
this.ch = ch;
}
@Override
public int compareTo(Alphabet o) {
if (ch == o.ch) {
return Integer.compare(index, o.index);
}
return Character.compare(ch, o.ch);
}
@Override
public String toString() {
return "(" + index + ", " + ch + ")";
}
}
그렇다면 문자열을 큐에 넣을때마다 정렬해야 한다는 소리인데
문자열 자체를 맨 앞 부분을 하나씩 제거해야하기 때문에,
연산을 할 때마다 새로운 객체를 반환하는 불변객체 String보다는 StringBuffer을 사용했다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>(new BufferComparator());
for (int i = 0; i < n; i++) {
queue.add(new StringBuffer(in.next()));
}
while (!queue.isEmpty()) {
//System.out.println(queue);
StringBuffer alphabet = queue.poll();
System.out.print(alphabet.charAt(0));
alphabet.deleteCharAt(0);
if (alphabet.length() > 0) {
queue.add(alphabet);
}
alphabet = null;
}
System.out.println();
}
}
class BufferComparator implements Comparator<StringBuffer> {
public int compare(StringBuffer s1, StringBuffer s2) {
int min = Math.min(s1.length(), s2.length());
for (int i = 0; i < min; i++) {
if (s1.charAt(i) > s2.charAt(i)) {
return 1;
} else if (s1.charAt(i) < s2.charAt(i)) {
return -1;
}
}
return Integer.compare(s2.length(), s1.length());
}
}
BufferComparator을 직접 구현해서 정렬해주도록 했다.
결과는 53%에서 시간초과..
결론적으로는 로직 자체는 같으나, 커스텀 Comparator을 사용하지 않고 기본 Comparable로 정렬하여 사용하는 방법이라면 통과가 된다.
문제 조건에서 공백은 없이 알파벳 대문자로만 구성되어 있다고 했기 때문에,
문자 마지막에 'a'를 붙여주면 (ASCII - \0: 0, a: 097, A: 065)
모든 대문자는 'a'보다 작기 때문에 커스텀 Comparator를 사용하지 않고 기본 Comparable을 사용하면서 같은 동작을 하도록 만들 수 있다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>();
for (int i = 0; i < n; i++) {
queue.add(new StringBuffer(in.next() + "a"));
}
while (!queue.isEmpty()) {
StringBuffer alphabet = queue.poll();
System.out.print(alphabet.charAt(0));
alphabet.deleteCharAt(0);
if (alphabet.length() > 1) {
queue.add(alphabet);
}
alphabet = null;
}
System.out.println();
}
}
이 문제에서 주의해야 하는 대표 테스트케이스는 아래와 같다
4
CCCA
CCCB
CCCD
CCCE
2
ABCCC
BACCC
2
BAA
BA
PriorityQueue의 정렬 방법
PriorityQueue 내부의 정렬은 아래와 같은 함수를 이용하여 정렬된다.
정렬 자체에 영향을 주는 가장 큰 요소는 정렬 알고리즘인데, 이는 머지 소트로 동일하다.
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = key;
}
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
왠지는 모르겠지만.. 아래는 기본 Comparable과 custom Comparator이다.
어디서 차이가 발생했는지 시간날 때 compareTo 함수를 좀 더 까봐야겠다...
int compareTo(AbstractStringBuilder another) { // StringBuffer::compareTo
if (this == another) {
return 0;
}
byte val1[] = value;
byte val2[] = another.value;
int count1 = this.count;
int count2 = another.count;
if (coder == another.coder) {
return isLatin1() ? StringLatin1.compareTo(val1, val2, count1, count2)
: StringUTF16.compareTo(val1, val2, count1, count2);
}
return isLatin1() ? StringLatin1.compareToUTF16(val1, val2, count1, count2)
: StringUTF16.compareToLatin1(val1, val2, count1, count2);
}
class BufferComparator implements Comparator<StringBuffer> { // Custom BufferComparator
public int compare(StringBuffer s1, StringBuffer s2) {
int min = Math.min(s1.length(), s2.length());
for (int i = 0; i < min; i++) {
if (s1.charAt(i) > s2.charAt(i)) {
return 1;
} else if (s1.charAt(i) < s2.charAt(i)) {
return -1;
}
}
return Integer.compare(s2.length(), s1.length());
}
}
