ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [HackerRank] Sherlock and Anagrams 풀이(java)
    알고리즘/알고리즘 문제 2019. 4. 22. 21:20

    내가 알고리즘을 정말 못푸는 건가싶다. 이 문제 푸는데 3시간 걸렸다. 몇달 뒤에 다시 풀어도 이정도 걸릴 것 같아서 기록해두기.

     

    이 문제는 anagram을 찾는 문제인데,

    anagram이란 철자 바꾸기 놀이를 뜻하는데, 철자를 재배열해서 다른 문자로 만드는 것이다.

    즉, 어떻게 배열되어있든 두 단어를 비교했을 때 알파벳만 맞으면 된다.(순서가 뒤죽박죽이라도)

     

    위의 예시 중 하나를 들자면, ifailuhkqq는 ifafai는 순서는 다르지만 동일한 알파벳을 가지고 있다. 단일 알파벳이라도 ii는 순서를 바꿔도(의미가 없지만) 같다.

     

    내 풀이의 시간복잡도는 O(n^4) 이다. 아주 비효율적인 시간복잡도 같지만, 다 풀고 나서 다른 풀이들도 봤는데 O(n^4)의 시간복잡도를 가지고 있었다.

     

    예시 하나를 두고, 어떻게 풀까 고민했는데 'abba' 로 시작해보겠다.

    첫번째 시작 단어 'a'부터 시작하고 화살표(->)로 비교대상을 표현.                                         
    
    (첫번째 문자열부터 시작)'a' -> 'b', 'b', 'a'
    
    'ab' -> 'bb', 'ba'
    
    'abb' -> 'bba'
    
    (다음 문자열 비교로 넘어감) 'b' -> 'b', 'a'
    
    'bb' -> 'ba'
    
    (다음 문자열 비교로 넘어감) 'b' -> 'a'

    1. 비교하기 시작할 문자는 항상 +1로 시작하는 걸 알 수 있다. 이 부분이 아래 k = i+1 인 for문이다.

    • 'ab'를 비교시작할 때 'ba'부터 시작하듯이

    • 'abb'를 비교시작할 때 'bba'부터 시작하듯이

     

    2. 순서와 상관없이 알파벳만 일치하면 되기 때문에 기준이 되는 문자열을 LinkedList에 일단 담아두고 일치하는 알파벳을 찾으면 하나씩 없애도록 했고, 하나라도 틀린 알파벳이 나오면 바로 for문을 break하도록 했다.

     

    3. 'ab'를 비교하면 길이가 2인 문자열까지만 비교하듯이 문자열 길이를 저장하기 위한 변수 stringLength 를 사용했다.

     

    4. 기준이 되는 문자열이 주어진 문자열의 마지막 알파벳까진 만들 필요 없기 때문에 for문은 s.length -1 까지만 도는 것으로 했다.

     

    5. java에서 배열 변수에서 다른 배열변수로 값을 할당하면 얕은 복사가 되어 깊은 복사를 위해 for문을 직접 돌려주었다.

    public class SherlockAndAnagrams {
    
        static int sherlockAndAnagrams(String s) {
    
            int result = 0;
    
            for(int i=0; i<s.length()-1; i++) {
                int stringLength = 1;
    
                for(int j=i; j<s.length()-1; j++) {
    
                    LinkedList<String> perCharacter = new LinkedList<>();
    
                    // 비교할 기준이 될 문자 만듦
                    for(int k=i; k<i+stringLength; k++){
                        perCharacter.add(String.valueOf(s.charAt(k)));
                    }
    
                    for(int k=i+1; k<s.length(); k++){
                        boolean matchFlag = true;
                        LinkedList<String> dummyCharacter = new LinkedList<>();
    
                        // 체크할 문자길이가 실제 문자길이보다 길어지면 break
                        if(k+stringLength > s.length()){
                            break;
                        }
    
                        // 깊은 복사를 위해서 직접 for문 돌림
                        // 비교하려는 문자열을 원상태로 되돌려 비교하기 위해
                        for(int l=0; l<perCharacter.size(); l++) {
                            dummyCharacter.add(perCharacter.get(l));
                        }
    
                        // 기준되는 문자열과 만들어지는 문자열들을 비교
                        for(int l=k; l<k+stringLength; l++) {
                            String comparingChar = String.valueOf(s.charAt(l));
    
                            // 알파벳 순서가 달라도 존재만 하면 되기 때문에
                            // 존재 유무를 체크해서 remove
                            if(dummyCharacter.contains(comparingChar)) {
    
                                dummyCharacter.remove(comparingChar);
                            }
                            // 존재하지 않는 틀린 문자가 나오면 더이상 비교가 필요없이 Anagram에서 탈락
                            else {
                                matchFlag = false;
                                break;
                            }
                        }
    
                        if(matchFlag){
                            result++;
                        }
    
                    }
                    stringLength++;
    
                }
    
            }
    
            return result;
        }
    
    
        public static void main(String[] args) {
    
            System.out.println(SherlockAndAnagrams.sherlockAndAnagrams("mom"));
        }
    }
Designed by Tistory.