LeetCode - ReorganizeString

<문제>

https://leetcode.com/problems/reorganize-string/

Reorganize String - LeetCode

- 같은 문자가 인접하지 않도록 재배열하는 문제입니다.

<wrong>

- 나열되어 있는 문자열을 하나씩 꺼내어 만들면서 인접한지 체크하는 방법은 시간복잡도를 초과하게 됩니다.

 

<접근법>

- s : [1~500]

- 영어 소문자 26개가 나타날 수 있습니다.

- 같은 문자가 인접하지 않으려면 각 문자를 돌아가면서 선택하여 결과 문자열을 만드는 것으로 생각할 수 있습니다.

e.g) aabb -> abab,   aaabbc -> acabab / ababac

- 그렇다면 가장 자주 나타나는 문자를 먼저 사용하는 것이 유리하겠습니다.

- 같은 빈도수라면 우선순위를 정해야 겠습니다. (영어일 경우 알파벳순이 일반적입니다.)

 

<Key point>

- 가장 자주 나타나는 문자를 알기 위해서는 먼저 각 문자의 count를 구해야 합니다.

 시간복잡도 O(s) : s가 500이므로 충분합니다.

- 자주 나타나는 문자를 먼저 사용하기 위해서는 MaxHeap의 자료구조가 필요합니다.

 시간복잡도 O(log(x)) : 문자의 종류는 26가지 입니다. (영어소문자)

- MaxHeap에서 2개의 문자(X,Y) 를 꺼낸뒤 결과문자열을 만듭니다.

- 꺼낸 문자의 Count를 1 감소시키고 다시 넣습니다.

 

<boundary>

- MaxHeap에 문자가 1개만 남은경우는 ?? (현재 남은 문자 Z)

a) 해당 문자의 count가 1이상이라면 : 이후 만들어지는 문자열은 같은 문자가 인접할 수 밖에 없습니다. -> 불가능

b) 해당 문자의 count가 1이라면 :  이전 결과 문자열을 만들때 MaxHeap에서 꺼낸 문자가 X,Y 라고 하고 Y!=Z 이면 가능

 1. Y=Z 가 되는 케이스

 Y=Z 이라면 꺼낼당시 Y:2 이며 -> X:1 , Y:2 인 경우는 MaxHeap의 정의에 모순이 됨 

                                            또한 X:2이상 , Y:2 인 경우는 MaxHeap 문자가 1개 남는다는 가정과 모순이 됨

 2. 따라서 Y!=Z 인 경우만 가능함

 Y!=Z 이라면 꺼낼당시 Y:1 이며 -> Z(1) 관계없이 성립

 

<solution>

import java.util.Comparator;
import java.util.PriorityQueue;

public class ReorganizeString {

    public class Info{
        public char key;
        public int count;

        public Info(char key, int count){
            this.key=key;
            this.count=count;
        }
    }

    public static void main(String[] args){
        ReorganizeString module = new ReorganizeString();
        module.reorganizeString("aab");
    }
    public String reorganizeString(String S) {
        String ret = "";
        int[] array = new int[26];
        for(int i = 0; i < S.length(); i++){
            array[S.charAt(i) - 'a']++;
        }
        PriorityQueue<Info> pq = new PriorityQueue<Info>(new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return (o1.count - o2.count)* - 1;
            }
        });
        for(int i = 0; i < 26; i++){
            if(array[i] > 0 ) {
                pq.add( new Info((char)(i+'a'), array[i]) );
            }
        }

        while(!pq.isEmpty()){
            if(pq.size() > 1){
                Info a = pq.poll();
                Info b = pq.poll();
                ret += a.key;
                ret += b.key;

                a.count--;
                b.count--;

                if(a.count > 0 ){
                    pq.add(a);
                }
                if(b.count > 0 ){
                    pq.add(b);
                }
            }else{
                Info a = pq.poll();
                if(a.count ==1){
                    ret +=a.key;
                }else{
                    ret="";
                }
            }
        }
        return ret;
    }
}

<참고>

https://github.com/ggthename