[Level 2] 전화번호 목록

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

---

접근

in 연산을 통해 파악하려고 했으나 몇몇 케이스에서 실패를 하였다. 

정렬을 해야할 필요가 있었고 오름차순으로 정렬을 한다면 정수형으로 봤을 때 맨 앞 글자가 작은 순서대로 앞에온다. 만약 맨 앞 글자가 같다면 그 다음 수를 보기 때문에 in 연산을 사용할 수 있게된다.

 

1233, 33 이라는 케이스가 있을 때 문자열의 길이를 오름차순으로 정렬한다면 33이 1233안에 있는지 판단하겠지만 문자열의 앞 글자로 정렬하면 1233이 33안에 포함되어있는지를 검사한다.

 

구현

입력받은 전화번호 목록을 정렬시킨다. 맨 앞 글자를 기준으로 오름차순 정렬된다.

그렇다면 정수형으로 바꿨을 때 맨 앞의 숫자가 작은 순서대로 있고 in을 통해 접두사를 판별할 수 있다.

def solution(phone_book):
    answer = True
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book[i] in phone_book[j]:
                return False
    return answer

---

다시 풀기

위의 코드는 다시 풀었을 때 틀렸다고 나온다.

8월에 다시 풀었을 때 str1.startswith(str2)를 사용하였고, 이는 str1이 str2로 시작하는지 판별하는 함수이다.

따라서 다음과 같은 코드로 구현할 수 있다.

- 정렬을 했을 때 앞의 문자로만 비교하면 되기 때문에 정렬을 하고

- i+1의 문자가 i의 문자로 시작하는지 판별하여 True일 때 False를 반환한다.

def solution(phone_book):
    answer = True
    phone_book = sorted(phone_book)
    N = len(phone_book)
    for i in range(N-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return answer