99클럽 코테 스터디 5/99일차 TIL #전화번호 목록(미들러)

 

문제:전화번호 목록호 목록

출처: 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

1. 문제 설명

문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.구조대 : 119박준영 : 97 674 223지영석 : 11 9552 4421전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.제한 사항

2. 문제 해석

phone_book이라는 리스트 내에 있는 문자열(숫자)들 중 서로가 포함관계인 것들이 있는 경우를 찾는 것.

119, 1199999가 있으면 1199999가 119를 가지고 있고, 이럴 경우 false를, 이런 포함관계인 경우가 하나도 없을 경우 true를 return 한다.

3. 문제 풀이

풀이 (1) 91.7/100

한 번호가 다른 번호의 접두어인 경우 확인하기

1. phone_book에서 가장 길이가 짧은 것 찾기
- 중복 주의

2. 가장 길이가 짧은 것을 기준으로 각 문자열을 슬라이싱

3. set을 만들어서 원래 길이보다 짧으면 true
길이가 같으면 false

def solution(phone_book):
    
    cutted_phone_book = []
    shortest_num_len = len(phone_book[0])
    for phone_number in phone_book:
        
        if len(phone_number) < shortest_num_len:
            shortest_num_len = len(phone_number)
    for phone_number in phone_book:
        cutted_phone_book.append(phone_number[:shortest_num_len])
        
    # print(cutted_phone_book)
        
    set_cutted_phone_book = set(cutted_phone_book)
    
    if len(set_cutted_phone_book) != len(phone_book):
        return False
    else:
        return True

 Test는 통과하지만...

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.00ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.2MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.00ms, 10.2MB)
테스트 10 〉	통과 (0.00ms, 10.2MB)
테스트 11 〉	실패 (0.01ms, 10.4MB)
테스트 12 〉	통과 (0.00ms, 10.2MB)
테스트 13 〉	통과 (0.00ms, 10.2MB)
테스트 14 〉	실패 (0.41ms, 10.3MB)
테스트 15 〉	통과 (0.94ms, 10.4MB)
테스트 16 〉	통과 (0.44ms, 10.5MB)
테스트 17 〉	통과 (0.51ms, 10.4MB)
테스트 18 〉	통과 (0.67ms, 10.3MB)
테스트 19 〉	통과 (0.77ms, 10.7MB)
테스트 20 〉	통과 (0.80ms, 10.5MB)

2개의 test case에서 실패를 얻었다.

처음에는 이중 for문을 돌지 않아도 되어 로직을 나름 편하게 짠건가? 하고 만족했지만 2 case해결이 되지 않아 시간을 많이 허비했다.

생각보다 case들이 복잡하지 않은거 아닌가 했는데 간과한 case가 있었다.

2. 가장 길이가 짧은 것을 기준으로 각 문자열을 슬라이싱
-> 길이가 짧지 않은 경우가 해결이 안됨
ex) 888 8888 11 12 1234
=> 888이 가장 짧은게 아님

이런 case를 길이가 가장 짧은 숫자를 기준으로 하면 걸러낼 수 없게 된다.

그래서 다시 이중 for문으로 문제를 해결해보려 했다.

풀이 (2) 91.7/100

def solution(phone_book):
    
    sorted_phone_book =  sorted(phone_book)
    # print(sorted_phone_book)
    
    for i in range(len(sorted_phone_book)-1):
        for j in range(i+1, len(sorted_phone_book)):
            # print(sorted_phone_book[i], sorted_phone_book[j][:len(sorted_phone_book[i])])
            if sorted_phone_book[i] == sorted_phone_book[j][:len(sorted_phone_book[i])]:
                return False
    
    return True

해당 방법으로 무난하게 테스트는 통과했다.

하지만 예상대로 효율성 테스트에서 통과하지 못한다.

앞서  test case 2개를 통과하지 못했던 것과 비교해 보면 통과는 했으나 효율성에서 2개가 걸려 동일한 점수를 얻었다.

문제점을 시간내에 파악하지 못하였다...ㅠㅠ

 

풀이 (3) 100/100

이 문제는 sorted() 함수를 잘못 알고 있어서 문제를 어렵게 접근했던 것이다.

테스트는 무난하게 통과하는데 여기서 봐야할 것이 있다.

test 3에서 phone_book을 sorted 한 결과를 보면 내가 생각한 것과 매우 다르게 정렬되어 있었다.

입력값은 다음과 같다 : ["12", "123", "1235", "567", "88"]

그러면 sorted() 함수를 써서 나오는 결과가 

["12", "88" , "123", "567" ,"1235" ] 이라고 생각했다.

실제로 출력해보면 크기의 오름차순이 아니라 숫자 앞자리부터 오름차순을 정렬한 것을 알 수 있다.

다음 예시도 마찬가지이다.

sorted() 전: ["119", "97674223", "1195524421"]

sorted() 후: ['119', '1195524421', '97674223']

이 이유는 내가 자료형을 착각했기 때문이다. 

만약 리스트 내에 있는 값들이 str 형이 아닌 int 자료형이었으면 어떻게 달라질까.

lst_str = ["119", "97674223", "1195524421"]
lst_int = [119, 97674223, 1195524421]

print(sorted(lst_str))
print(sorted(lst_int))

>>['119', '1195524421', '97674223']
>>[119, 97674223, 1195524421]

보이는 것 처럼 위 리스트(문제에 나온)의 경우 문자열들을 비교하는 상황이기 때문에 숫자의 크기로 비교하는 것이 아니다.

반면 두 번째 리스트의 경우 int형 숫자들이 포함되어 숫자들의 크기를 비교해서 재배열하게 된다.

그러면 왜 "119", 다음에 "97674223"이 아니라 "1195524421" 가 나오는 걸까.

정리를 ChatGPT가 찰떡같이 해줬다.

---

문자열과 숫자 배열의 정렬 결과가 다른 이유는 문자열과 숫자가 정렬되는 방식이 다르기 때문입니다.

1. 문자열 정렬:
   • 문자열은 사전식(lexicographical)으로 정렬됩니다. 즉, 각 문자의 유니코드 값을 기준으로 정렬됩니다.
   • 예를 들어, "119", "97674223", "1195524421"은 첫 번째 문자부터 비교하여 순서가 결정됩니다.
   • sorted(lst_str)의 결과는 다음과 같습니다:
     • 첫 번째 문자열의 첫 번째 문자: "1", "9", "1"
     • "1"이 "9"보다 작기 때문에 "119"와 "1195524421"이 앞에 오고, "97674223"이 뒤에 옵니다.
     • "119"과 "1195524421"은 첫 번째 문자가 동일하므로 두 번째 문자를 비교합니다.
     • 두 번째 문자가 "1"이고 "1"로 같으므로 세 번째 문자를 비교합니다.
     • ... 이러한 방식으로 전체 문자열을 비교하여 정렬합니다.
   • 따라서 결과는 ['119', '1195524421', '97674223']입니다.
2. 숫자 정렬:
   • 숫자는 크기 순으로 정렬됩니다. 즉, 숫자의 값 그 자체를 기준으로 정렬됩니다.
   • sorted(lst_int)의 결과는 다음과 같습니다:
     • 숫자의 크기 순으로 정렬하면 119, 97674223, 1195524421 순으로 정렬됩니다.
   • 따라서 결과는 [119, 97674223, 1195524421]입니다.

요약하면, 문자열은 각 문자의 유니코드 값에 따라 사전식으로 정렬되고, 숫자는 그 값에 따라 크기 순으로 정렬되기 때문에 정렬 결과가 다르게 나타납니다.

---

그렇다 문자열의 비교의 경우 앞에서 부터 하나씩 비교를 하게 되는 것이고, 숫자의 경우 숫자의 크기만을 가지고 비교하기 때문이다.

그러면 문제에 이 방법을 어떻게 적용할까.

def solution(phone_book):
    
    sorted_phone_book =  sorted(phone_book)
    
    for i in range(len(sorted_phone_book)-1):
        
        if sorted_phone_book[i] == sorted_phone_book[i+1][:len(sorted_phone_book[i])]:
                return False

    return True

어차피 sorted()를 통해 숫자인척하는 문자열의 비교를 앞쪽부터 비교하기 때문에 이미 비교할 대상이 바로 옆에 있게 된다.

그 말은 우리가 앞에서부터 중복이 되는 숫자를 찾는 방식을 복잡하게 생각할 필요 없이 내 바로 옆 숫자랑 비교해보면 되는 것이었다. 

이미 sorted()를 이용하여 배열이 정리가 되면 앞에 짧은 숫자가, 그 뒤에 그 숫자와 겹치지만 더 긴 숫자가 정렬되어 있다.

그래서 현재 숫자와 그 숫자 길이만큼 그 다음 숫자를 잘라서 비교해보면 끝이다.

이중 for문을 사용할 필요가 전혀 없었던 것이었다!

 

 

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.1MB)
테스트 4 〉	통과 (0.00ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.00ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.3MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.00ms, 10.3MB)
테스트 14 〉	통과 (0.55ms, 10.2MB)
테스트 15 〉	통과 (0.52ms, 10.2MB)
테스트 16 〉	통과 (0.70ms, 10.1MB)
테스트 17 〉	통과 (1.28ms, 10.3MB)
테스트 18 〉	통과 (0.96ms, 10.3MB)
테스트 19 〉	통과 (0.96ms, 10.3MB)
테스트 20 〉	통과 (1.87ms, 10.4MB)

무난하게 모든 케이스를 통과하고

 

테스트 1 〉	통과 (2.73ms, 10.7MB)
테스트 2 〉	통과 (2.69ms, 10.7MB)
테스트 3 〉	통과 (100.32ms, 30.6MB)
테스트 4 〉	통과 (86.42ms, 28.1MB)

2중 for문이 없어졌기에 효율성 테스트도 모두 통과하는 것을 볼 수 있다.

2중 for문이 없어졌으니 당연히 시간 복잡도가 n^2에서 n으로 획기적으로 줄었다.

 

4. 주요 코드 및 정리

4.1 리스트 정렬: sorted()

lst = [119, 97674223, 1195524421]

# 오름차순 정렬
print(sorted(lst))

# 내림차순 정렬
print(sorted(lst, reverse=True))

>> [119, 97674223, 1195524421]
>> [1195524421, 97674223, 119]

 

4.2 문자열 정렬

문자열의 경우 앞의 값 부터 하나씩 비교해 나가므로 숫자형 비교와 전혀 다르므로 주의!

lst_str = ["119", "97674223", "1195524421"]
lst_int = [119, 97674223, 1195524421]

print(sorted(lst_str))
print(sorted(lst_int))

>> ['119', '1195524421', '97674223']
>> [119, 97674223, 1195524421]