<div id="readability-page-1" class="page"><div>            <h2>Prologue</h2>
<p data-ke-size="size16">아... 회문 순열 문제를 풀고나서 영 찜찜해서 다시 생각해보니 딕셔너리만 쓰면 되는 문제였습니다. 바보같이 Permutation쓰고 is_palindrome 구현하고.. ㅋㅋㅋㅋㅋ 무슨 뻘짓을 한 거지!<br>딕셔너리만 쓰면 정말 쉬운 문제였는데, O(n)으로 끝날 걸, 거의 O(n^2 ~ n!) 수준으로 풀어놨으니.....<br>아이디어는 매우 단순합니다. 회문을 이루려면, 회문의 길이가 짝수인 경우엔, 모든 알파벳이 짝수개가 있으면 되고, 길이가 홀수라면, 하나 빼고 모두 짝수이면 됩니다. 따라서 홀수인 알파벳이 하나만 존재하는지 확인해주면 됩니다. <br>이걸 어떻게 그렇게 풀 수가 있을까요... ㅋㅋㅋㅋㅋㅋㅋㅋ 아무리 생각해도 웃음벨이 될 것 같습니다... ㅋㅋㅋ..</p>
<h2>코드</h2>
<pre><code>def solution(words):
    words = words.replace(' ', '')
    words_dict = {}
    for word in words:
        if word not in words_dict :
            words_dict[word] = 1
        else:
            words_dict[word] += 1
    if len(words) % 2 == 0:
        for value in words_dict.values():
            if value % 2 != 0:
                return False
    else:
        one_value = 0
        for value in words_dict.values():
            if value % 2 != 0:
                one_value += 1
            if one_value &gt; 1:
                return False

    return True</code></pre>                        
</div></div>

욱이의 IT 생존일지

Jaewook Oh

Prologue
아... 회문 순열 문제를 풀고나서 영 찜찜해서 다시 생각해보니 딕셔너리만 쓰면 되는 문제였습니다. 바보같이 Permutation쓰고 is_palindrome 구현하고.. ㅋㅋㅋㅋㅋ 무슨 뻘짓을 한 거지!
딕셔너리만 쓰면 정말 쉬운 문제였는데, O(n)으로 끝날 걸, 거의 O(n^2 ~ n!) 수준으로 풀어놨으니.....
아이디어는 매우 단순합니다. 회문을 이루려면, 회문의 길이가 짝수인 경우엔, 모든 알파벳이 짝수개가 있으면 되고, 길이가 홀수라면, 하나 빼고 모두 짝수이면 됩니다. 따라서 홀수인 알파벳이 하나만 존재하는지 확인해주면 됩니다. 
이걸 어떻게 그렇게 풀 수가 있을까요... ㅋㅋㅋㅋㅋㅋㅋㅋ 아무리 생각해도 웃음벨이 될 것 같습니다... ㅋㅋㅋ..
코드
def solution(words):
    words = words.replace(' ', '')
    words_dict = {}
    for word in words:
        if word not in words_dict :
            words_dict[word] = 1
        else:
            words_dict[word] += 1
    if len(words) % 2 == 0:
        for value in words_dict.values():
            if value % 2 != 0:
                return False
    else:
        one_value = 0
        for value in words_dict.values():
            if value % 2 != 0:
                one_value += 1
            if one_value > 1:
                return False
    return True

[PS/Python] 회문 순열

댓글