전화번호 목록 →기준값 갱신+startswith()+숫자문자열 정렬★★

1차 극복

예) 119 > 119234 (접두어인 경우) false, 
     119 > 12119234 (중간 포함이므로 접두어 아님) true
     119 > 12342119 (끝에 포함이므로 접두어 아님) true

 

 

▶ startswith() → 테스트 케이스1 극복

 

 

 

2차 극복

 

▶ 테스트 케이스 ["11" "1"] → false가 나와야된다. 

    왜냐하면 아래와 같이 정렬하는 경우 
   

    ["1" "11"] →  "11"안에 접두어 "1"이 있으므로 false가 나와야된다. 

    이러한 테스트 케이스를 극복하기 위해 미리 "문자열길이"를 기준으로 정렬해준다. (어차피 틀린 풀이)

 

 

3차 극복 

▶ break를 사용하는 경우 안쪽 for문을 종료하고, 바깥쪽 for문을 다시 수행하지만,

   

   접두어가 포함된 문자열을 찾은 경우 return False하면 함수가 바로 종료되므로,

 

   바깥쪽 for문을 순회하는 비효율성을 제거할수있다. 

 

  →효율성 테스트 1,2만 통과 

 

 

 

4차 극복

 

▶ 효율성 테스트 3,4 실패

 

정렬기준을 "문자열 길이"에서 sort()로 바꾸었다.

 

 

str으로 구성된 리스트를 sort()로 정렬하면

 

"숫자문자열"의 첫번째 index의 "숫자문자"에 따라 정렬된다. 

phone_book = ["3", "1117", "213", "123456789"] 일 때

sort()정렬을 하는 경우 

 

"문자열의 길이와 무관하게"

아래와 같은 결과가 나온다.  

['1117', '123456789', '213', '3']


왜 그렇냐?? 왜!!!!!!!!!!!

sort() 함수는 문자열을 정렬할 때, 
즉, 각 문자열 요소의 첫 번째 인덱스의 문자 기준으로 정렬이 이루어진다.
 
그래서 주어진 리스트에서는 첫 번째 인덱스인 '1'이 제일 앞에 위치하고, 그 다음으로 '2'가 위치하고,

마지막으로 '3'이 위치한다.

그래서 정렬 결과가  ['1117', '123456789', '213', '3'] 으로 출력된다. 


그러면 본래 문제로 들어서 Hint를 설명하겠다. 

phone_book = ["11", "1", "1117", "213", "123456789"]

위의 코드를 정렬하면 

['1', '11', '1117', '123456789', '213']

여기서 이미 Hint가 나왔다. 

"1" 옆에는 가장 가까운 "11" 숫자 문자열이 존재한다.

그러면 "1117" 비교할 필요가 없다. cutting하면 된다.

다시 말해서 정렬한 후 접두어의 옆에만 확인하면 끝이다.!!! 

왜냐하면 sort()한 결과 접두어의 우측 옆에는 가장 가까운 숫자문자열이 오기 때문이다!!! 

가장 가까운 문자열이 접두어를 포함하고 있지 않다면,

그 나머지 숫자문자열은 check할 필요가 없다.

 

 

→ 이중 for문에서 for문 1개를 삭제할 기회가 생겼다.

 

 

 

 

 

 

 

 

 

 

 

 

 

나의 풀이 

def solution(phone_book):
    phone_book.sort()
    answer=True


    for i in range(len(phone_book)-1):
        standard=phone_book[i]
        if  phone_book[i+1].startswith(standard):
            answer=False
            return answer
    return answer