boj 1294: 문자열 장식

문자열을 적절히 쪼갠 후 하나로 합칠 때, 사전상으로 가장 앞에 오는 단어를 구하는 문제이다.

한 문자내의 쪼갠 문자 순서는 바뀌면 안된다

 

먼저 아이디어는 각 단어를 가리키는 포인터가 각각 존재하며,

맨 앞부분만 서로 비교했을 때 가장 작은 값을 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());
        }
    }