바위타는 두루미
1.4 회문 순열 본문
728x90
문제
주어진 문자열이 회문(Palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며 순열이란 문자열을 재배치하는 것을 의미한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.
예제
입력 : tact coa
출력 : True
접근법
어느 방향으로 읽어도 같은 문자열이 되기 위해서는 모든 문자가 각각 홀수개 이거나, 단 한개의 문자만 홀수 개여야한다.
방법 1 hash table을 이용하여 각 문자가 몇번 등장했는지 세고, 홀수의 갯수를 확인하기
방법 2 문자열을 읽어나가면서 홀수의 갯수를 세기
def Solution(phrase):
alpha_cnt = [0]*26
odd_cnt = 0
for alpha in phrase :
alpha_cnt[ord(alpha)-ord('a')] +=1
if alpha_cnt[ord(alpha)-ord('a')] %2 !=0 :
odd_cnt +=1
else :
odd_cnt -=1
return odd_cnt <2
방법 3 비트벡터를 이용하여 1로 세팅된 비트의 갯수가 1개이거나 0개인 경우를 확인한다.
def Solution(phrase):
alpha_chk = 0
for alpha in phrase :
alpha_chk ^= (1<< (ord(alpha)-ord('a'))
return alpha_chk ==0 | (alpha_chk-1) & alpha_chk ==0
여기서 신박했던 것은
이진수에서 1의 갯수가 단 하나인지를 체크할때 AND연산으로 가능하다는 것이다.
(확인할 수 -1 ) AND (확인할수) ==0 이면 1의 갯수는 1개이다
왜냐하면 만약 확인하고 싶은 수가 001000이라고 할때 -1을 하면 000111이 되고 그말은 즉 겹치는 부분이 없다는 뜻이다.
만약 확인하고 싶은 수가 101000이면 -1한 경우 100111이 되고 이경우 AND연산을하면 100000으로 0이 되지 않는다.
'Study > Interview준비' 카테고리의 다른 글
1.6 문자열 압축 (0) | 2019.07.25 |
---|---|
1.5 하나빼기 (0) | 2019.07.25 |
1.3 URL화 (0) | 2019.07.24 |
1.2 순열확인 (0) | 2019.07.24 |
1.1 중복이 없는가 (0) | 2019.07.24 |
Comments