01. 배열과 문자열

문제 1.4

회문 순열 : 주어진 문자열이 회문의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

풀어보기

1. 각 문자의 등장 횟수를 구하고 홀수 번 반복되는 문자가 2개 이상이면 회문이 아니라고 판단한다.

문제를 다시 쉽게 해석해보면 예를 들어 "토토마" 라는 문자가 주어졌을 때 이를 재배치 하여 "토마토" 라는 회문을 만들 수 있는지 없는지 확인하는 문제이다.

먼저 대문자와 소문자를 구별할 것인지, 공백은 무시할 것인지 아니면 하나의 문자로 볼 것인지 확인하는 것이 좋아보인다. 일단 대소문자와 공백을 무시한다고 가정하고 문제를 풀어보자.

회문의 특징은 문자열의 등장 횟수를 count했을 때 홀수번 반복되는 문자가 1개 이거나 혹은 0개 이어야 한다.

# 1.4 회문순열
from collections import Counter

s = "Tact Coab"

def solution(s):
    s = s.lower() # 소문자로 치환
    s = s.replace(" ", "") # 공백제거
    s_list = list(s)
    odd_cnt = 0

    counter = Counter(s_list)

    for x in counter:
        if counter[x] % 2 != 0:
            odd_cnt += 1
    if odd_cnt > 1:
        return False
    else:
        return True
solution(s)

# -결과----------------------------------------------------------------------------------
# False

해답

1. 각 문자가 몇 번 등장했는지 세고, 홀수 번 등장한 문자가 한 개 이상인지 확인한다.

한 번 순회하며 각 문자열의 등장 횟수를 세고, 이후 각 문자마다 몇번 등장 했는지 확인하며 홀수 번 등장한 문자가 몇개인지 확인한다.

O(N)의 시간 복잡도가 소요 된다. 충분히 좋은 알고리즘 이지만 최선의 방향을 찾는 노력은 중요하다. 좀 더 개선할 수 있는 방법을 생각해보자.

같은 아이디어 이지만 내 풀이는 홀수개의 문자열이 몇 개인지 다 센후 검증하지만, 우리는 2개 이상인지만 확인하면 되기 때문에 홀수 개 문자열이 2개 이상 등장하는 순간 바로 프로그램을 종료할 수 있다.

// 회문순열인지 판단하는 함수
boolean isPermutationOfPalindrome(String phrase){
    int [] table = buildCharFrequencyTable(phrase);
    return checkMaxOneOdd(table);
}

boolean checkMaxOneOdd(int[] table){
    boolean foundOdd = false;
    for (int count : table){
        if (count % 2 == 1){
            if (foundOdd) {
                return false; // 홀수개 문자가 2개 이상 나오는 순간 false
            }
            foundOdd = true;
        }
    }
    return true ;
}

// 문자에 해당하는 숫자를 리턴한다. a=1, b=2 ...
int getCharNumber(Character c){
    int a = Character.getNumericValue('a');
    int z = Character.getNumericValue('z');
    int val = Character.getNumericValue(c);

    if (a <= val && val <= z){
        return val - a;
    }
    return -1;
}


// 각 문자가 몇 번씩 등장하는지 기록하여 저장하는 함수
int [] buildCharFrequencyTable(String phrase){
    int [] table = new int[Character.getNumericValue('z') - Character.getNumericValue('a') + 1]; // a~z 길이만큼 배열 생성

    for (char c : phrase.toCharArray()){
        int x = getCharNumber(c);
        if (x != -1){
            table[x]++;
        }
    }
    return table
}

2. 1번과 같지만, 홀수 개 인지 여부를 문자열을 순회하면서 동시에 확인한다.

루프를 2번에서 1번으로 줄일 수 있다. 그러나 각 문자마다 수행되는 코드가 더 많아져 성능이 향상되었다고 얘기할 수는 없다.

3. 등장 횟수를 세지 않고, 문자열이 등장할 때마다 해당 위치의 비트값을 바꿔주며 홀수, 짝수 여부를 판단한다.

시간 복잡도는 O(N)으로 똑같다. 그러나 정수 하나만 가지고 확인할 수 있기 때문에 메모리는 확실히 효율적이다.!

boolean isPermutationOfPalindrome(String phrase){
    int bitVector = createBitVector(phrase);

}

int createBitVector(String phrase){
    int bitVector = 0;
    for (char c : phrase.toCharArray()){
        int x = getCharNumber(c);
        bitVector = toggle(bitVector, x);
    }
}

// 정수의 i번째 비트값을 바꾼다.
int toggle(int bitVector, int index){
    if (index < 0 ) return bitVector;

    int mask = 1 << index;
    if ((bitVector * mask) == 0){
        bitVector |= mask;
    }else{
        bitVector &= ~mask;
    }
    return bitVector;
}

boolean checkExactlyOneBitSet(int bitVector){
    return (bitVector & (bitVector - 1)) == 0;
}

비트벡터 개념과 비트연산자 문법 정리..!