코딩 인터뷰 완전 분석 1.2 파이썬3 풀이

문제

1.2 순열 확인 : 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

 

제한 사항

1. 순열 관계가 무엇인지 알아야 함. -> 같은 문자로 구성 되었지만 순서가 다른 문자열.
2. 문자열 길이의 제한이 없다.
3. 문자 또한 알파벳에 대한 제한이 없다.
4. 주어진 문자열의 순서를 바꾸어도 되는지에 대한 제한이 없다.
5. 두 문자열의 길이가 다르면 False다.

 

아이디어1

각각의 문자열을 정렬한다. -> O(nlogn)

앞에서 부터 한 문자 비교한다. -> O(n)

 

공간복잡도

주어진 문자열을 건드려서 안되면 O(n)

상관없다면 O(1)

 

시간복잡도

O(nlogn)

 

아이디어2

하나의 문자열의 문자를 키로 해쉬테이블을 만든다.

해쉬테이블의 값은 하나의 문자열 문자의 카운트를 한다.

다음 문자열이 해쉬테이블을 음으로 카운트 한다.

모든 해쉬테이블의 값이 0이면 True, 아니라면 False이다.

 

공간복잡도

O(n) 사실은 n보다는 작다. 문자의 종류만큼 있다.

 

시간복잡도

O(n)

 

테스트케이스

True 경우

• ‘aaaaaaaaaaaaaaa’ , ‘aaaaaaaaaaaaaaa’
• ‘abcdefg’ , ‘gfedcba’
• ‘1,2,3,4,5,6,7’ , ‘1234567,,,,,,’
• ‘0’ , ‘0’
• ‘aaabbb’ , ‘bbbaaa’

 

False 경우

• ‘0’ , ‘1’
• ‘aaaaaaaaaaaaaab’ , ‘caaaaaaaaaaaaaa’
• ‘ababababababab’ , ‘bababababababc’
• ‘1,2,3,4,’ , ‘1,2,3,4’
• ‘aaabbb’ , ‘cccaaa’

 

코드

아이디어 1

def is_combination(first_str, second_str):

    if len(first_str) != len(second_str):
        return False

    first_str = sorted(first_str)
    second_str = sorted(second_str)

    for index in range(0, len(first_str)):
        if first_str[index] != second_str[index]:
            return False

    return True


# True 경우
print(is_combination('aaaaaaaaaaaaaaa' , 'aaaaaaaaaaaaaaa'))
print(is_combination('abcdefg' , 'gfedcba'))
print(is_combination('1,2,3,4,5,6,7' ,'1234567,,,,,,'))
print(is_combination('0' , '0'))
print(is_combination('aaabbb' , 'bbbaaa'))

# False 경우
print(is_combination('0' , '1'))
print(is_combination('aaaaaaaaaaaaaab' , 'caaaaaaaaaaaaaa'))
print(is_combination('ababababababab' , 'bababababababc'))
print(is_combination('1,2,3,4,' , '1,2,3,4'))
print(is_combination('aaabbb' , 'cccaaa'))

아이디어 2

def is_combination(first_str, second_str):

    if len(first_str) != len(second_str):
        return False

    char_table = {}

    for char in first_str:
        char_table[char] = 0

    for char in first_str:
        char_table[char] += 1

    for char in second_str:
        try:
            char_table[char] -= 1
        except KeyError:
            return False

    for value in char_table.values():
        if value != 0:
            return False

    return True


# True 경우
print(is_combination('aaaaaaaaaaaaaaa' , 'aaaaaaaaaaaaaaa'))
print(is_combination('abcdefg' , 'gfedcba'))
print(is_combination('1,2,3,4,5,6,7' ,'1234567,,,,,,'))
print(is_combination('0' , '0'))
print(is_combination('aaabbb' , 'bbbaaa'))

# False 경우
print(is_combination('0' , '1'))
print(is_combination('aaaaaaaaaaaaaab' , 'caaaaaaaaaaaaaa'))
print(is_combination('ababababababab' , 'bababababababc'))
print(is_combination('1,2,3,4,' , '1,2,3,4'))
print(is_combination('aaabbb' , 'cccaaa'))

힌트

#1 두 문자열이 서로 순열관계에 있다는 말이 무슨 의미인지 설명해 보라. 이제, 여러분이 말한 정의를 살펴봐라. 그 정의에 따라 문자열을 확인할 수 있겠는가?

#84 O(NlogN) 시간의 해법이 하나 존재한다. 다른 해법은 추가 공간을 사용하지만 O(N) 시간이 걸린다.

#122 해시테이블이 유용한가?

#131 서로 순열 관계에 있는 두 문자열은 같은 문자 집합으로 이루어져 있고, 그 순서만 다를 것이다. 순서도 같게 만들 수 있는가?

 

해답

1.1의 풀이와 유사하게 128 크기의 캐릭터 배열을 사용하여 문자가 들어있는지 확인하였다. 소팅하는 것은 똑같았다.