본문으로 건너뛰기
Knowledge Garage

[개발자 면접 준비] 문자열 알고리즘 순열 회문 찾기 - Is Palindrome Permutation?

주어진 문자열의 문자들을 재배열해 회문(palindrome)을 만들 수 있는지 판별하는 문제. 문자 빈도수 기반 O(N) 접근과 단일 루프 최적화 풀이를 Java로 정리합니다.

운
운영자
Knowledge Garage

순열 회문 찾기 - Is Palindrome Permutation?

문제: 주어진 문자가 회문의 순열인지 확인하는 함수를 작성하라.

예를 들면 스트링 Tact Coa가 주어졌을경우 True를 리턴한다. 왜냐하면 Tact Coa의 순열중에 회문이 있기때문이다.
Input: Tact Coa
Output: True (permutations:"taco cat'; "atco cta'; etc.)

문자열 문제중 기본적인 주제이다. 몸풀기로 좋은 문제인 것 같다. Java로 풀어보았다.

용어 정의 

  • Palindrome (회문): 앞으로 읽으나 뒤로 읽으나 같은 문자열.
    • 예: 토마토, 별똥별, aaabaaa 등등
  • Permutation(순열): 문자의 재배열을 뜻한다.
    • 예: ABC의 모든 순열은 ABC, BAC, CAB, ACB, BCA, CBA 총 6개이다.

위의 회문가 순열에대한 뜻을 알면 이 문제는 비교적 간단하고 쉽게 솔루션을 떠올릴 수 있을 것이다. 위에서 알아본것과 같이 회문은 앞뒤가 같은 문자열이다. 따라서 첫번재로 회문인지 확인하기위해 체크해야하는 로직이 필요하다는 것을 알게 된다. 회문여부를 확인 하기 위해서는 글자의길이가 홀수 인지 짝수인지 파악한다음 가운데를 기준으로 앞뒤가 같은지 체크하면 된다. 글자길이가 홀수이면 가운데 글자를 제외한체 비교 하면 된다. 이것을 조금더 생각해보면 모든 글자수는 짝수여야하고 글자길이가 홀수이면 하나의 문자만 1개여야 회문이라는 것을 알 수 있다. 

다시 문제의 예제를 보자. 인터뷰 대비용 문제이기 때문에 면접관에게 몇가지를 질문 하여 올바른 로직을 만들 수 있다. 예제로 나온 문자열을 보면 대소문자가 섞여있고 공백도 있다. 따라서 면접관에게 공백처리에 관한 질문을 하고 대소문자여부 최대길이 최소길이 예외상황 등에대해서 질문하도록 하자. 이번에는 대소문자와 공백만 포함하는 문자열을 다루는 경우라고 가정하고 풀겠다.

대소문자와 공백만을 대상으로하면 ASCII코드로 모든 문자를 표현할수 있따. 아스키는 128개이므로 128길이의 배열을 만들어서 사용하면 된다. 아니면 간단하게 모든 문자를 소문자로 치환한후 26길이의 배열을 써도 될 것이다.

public boolean isPermutation_twoLooops(String s){
        int[] arr = new int[26];
        int len = 0;
        for(char c : s.toLowerCase().toCharArray()){
            if(Character.isLetter(c)){
                arr[c - 'a']++;
                len++;
            }
        }

    boolean isEven = len % 2 == 0;
    for(int val : arr){
        if(val != 0 && val != 2){
            if(isEven) return false;
            else isEven = true;
        }
    }
    return true;
}</code></pre>


위와같이 작성하면 주어진 스트링의 길이 N 만큼의 시간복잡도를 사용한다는 것을 알 수있다. 두번의 for문이 사용 되었으므로 2N이고 빅오 표기법으로 정리하면 O(N)의 시간복잡도와 O(1) 공간복잡도를 사용한다.


여기서 개운치않은 기분이 든다면 for-loop 한번으로 풀지 못했기 때문일 것이다. 한번의 for-loop으로 더 효율적으로 풀수 있을까? 그렇다. 할수 있다. 아까 회문을 찾는 조건을 다시생각해보면 홀수일때는 홀수가 1개이고 짝수일때느 모든 문자열이 2개여야한다. 그렇다면 이미 발견한 문자를 차감하면 모든경유 홀수는 최대 1이 나온다는 것을 유추 할 있다. 이것을 기반으로 다시 풀어보자.


public boolean isPermutation_oneloop(String s){
        int[] arr = new int[26];
        int oddCount = 0;
        for(char c : s.toLowerCase().toCharArray()){
            if(!Character.isLetter(c)) continue;
            if(++arr[c - 'a'] % 2 == 1) oddCount++;
            else oddCount--;
        }
        return oddCount <= 1;
    }


빅오표기법으로 표기하면 같은 O(N)의 복잡도이지만 한번의 for-loop으로 문자열을 한번만 읽기때문에 더 효율적이다. 인터넷을 찾아보면 스위치 on-off 개념으로 bitwise를 활용해서 더 간단하게 풀수 있다고 하니 나중에 풀면 업데이트 하도록 하겠다.

태그

전체 글 목록