코딩인터뷰 완전분석 - 1.2 순열 확인

 

코딩인터뷰 완전분석 (게일 라크만 맥도웰)

 

 

 

01. 배열과 문자열

문제 1.2

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

풀어보기

순열 관계라는 것은 두 문자열에서 사용된 문자는 같은데 문자의 순서만 다른 형태라는 것을 의미한다.

 

1. 정렬 후 리스트 비교

먼저 두 문자열의 길이가 같은지 확인한다. 길이가 다르면 순열 관계가 아니라고 판단한다.

길이가 같다면 두 문자열을 정렬하여 두 개의 리스트가 같은지 비교연산자를 통해 비교한다.

# 1.2 순열 확인

def istnsduf(str1, str2):
    if len(str1) == len(str2):

        listStr1 = list(str1)
        listStr2 = list(str2)
        listStr1.sort()
        listStr2.sort()

        if listStr1 == listStr2:
            return True
    return False

print('ABC', 'AER', istnsduf('ABC', 'AER'))
print('CBS', 'SCB', istnsduf('CBS', 'SCB'))

# -결과----------------------------------------------------------------------------------
# ABC AER False
# CBS SCB True

---

모법답안

먼저 확인 해야 할 사항은. 대소문자는 구별할 것인지? 그리고 공백은 어떻게 볼 것인지?

여기서는 대소문자를 구별하고 공백을 하나의 문자열로 판단하기로 한다.

 

 

1. 정렬하여 비교하기

순열 관계의 문자열은 정렬하면 같은 문자열이 되기 때문에 정렬 후 두 문자열을 비교해주면 된다. 단순하고 이해하기 쉽다는 측면에서 좋은 풀이이지만, 효율성 측면에서는 최적은 아니다.

 

 

2. 문자열에 포함된 문자의 출현 횟수가 같은지 비교

순열 관계의 문자열은 동일한 문자가 동일한 횟수로 출현한다는 특징이 있다. 이를 각각 문자열에서 기록하고 이 횟수를 비교한다

1번 풀이는 O(NlogN) 의 시간 복잡도, 2번 풀이는 O(N)의 시간 복잡도가 걸릴 것 같다!