[Algorithm] 프로그래머스 전화번호 목록(해시)

문제

 

 

  해당 문제를 풀 때 단순히 각 리스트 원소가 다른 리스트 원소의 앞 부분에 위치하는지, 그 원소로 시작하는 지를 따지려면 반복문을 2번 써야 하는 것.

 

풀이

 

  문제 해결 아이디어는, "어떤 번호가 다른 번호의 접두어라면, 이 둘을 정렬했을 때 앞 뒤에 위치"하게 된다는 것이다.

 

  즉, ["1235", "123", "12345", "012"] 라는 리스트를 정렬하게 되면 문자열 리스트는 대문자에서 소문자 순서로, 알파벳 순서로 정렬되므로,

 

  ["1012", "123", "12348", "1235"] 가 된다.

 

  1.  따라서, i 번째 원소를 i+1번째 원소와 비교하며,

 

  2-1.  i + 1번째 원소의 [앞에서부터 ~ i번째 원소의 길이 만큼]이 i번째 원소와 같은지를 확인한다.

 

  2-2.  여기서, i번째 원소가  i+1번째 원소로 시작한다는 것이므로 startwith()를 사용해서 해당 원소로 시작하는지를 따질 수도 있다.

 

  3.  만약, 같은 경우가 발생하면, 어떤 한 번호가 다른 번호의 접두어인 것이므로 False를 리턴한다.

 

def solution(phone_book):
    answer = True
    # 어떤 번호가 다른 번호의 접두어라면 이 둘은 정렬했을 때 앞뒤에 위치
    phone_book = sorted(phone_book)

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

 

def solution(phone_book):
    answer = True
    # 어떤 번호가 다른 번호의 접두어라면 이 둘은 정렬했을 때 앞뒤에 위치
    phone_book = sorted(phone_book)

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

 

  +  사실, 나는 리스트 정렬 후 i 번째 원소가 i+1번째 원소의 문자열에 포함되는지를 따지는 in 을 써서 풀었었다.

 

 

다른 풀이 1 - zip() 함수 + startswith 사용

 

  -  사실, zip() 함수 안에 인자로 넣을 리스트의 원소의 개수가 같아야만 쓸 수 있다고 생각했는데,

 

  -  앞의 리스트는 처음부터, 뒤의 리스트는 index 1 부터 넣어주면 i 번째와 i+1번째에 대한 비교가 가능한 것이었다.

 

def solution(phone_book):
    answer = True
    # 어떤 번호가 다른 번호의 접두어라면 이 둘은 정렬했을 때 앞뒤에 위치
    phone_book = sorted(phone_book)

    for num1, num2 in zip(phone_book, phone_book[1:]):
        if num2.startswith(num1):
            answer = False
            return answer
                
    return answer

 

다른 풀이 2 - 해시 함수 사용

 

def solution(phone_book):
    answer = True

    dic = dict()
    for i in phone_book:
        dic[i] = 1

    for num in phone_book:
        tmp = ""
        for j in num:
            tmp += j
            if tmp in dic and tmp != num:
                print('tmp : ', tmp, ' num : ', num)   # 즉, num :  1195524421 에 대한 반복문을 진행할 때, tmp에 119가 + 되었을 때
                answer = False
                
    return answer

 

  -  각 번호를 이루는 문자들을 tmp 에 저장해가면서,

 

  -  tmp가 dic의 딕셔너리 키 값으로 존재하는지 확인 + 그 tmp 가 자신과 같은지 확인

 

  -  tmp가 num의 각 문자를 더해가면서 만들어진 String일 때, 

   

    dic의 딕셔너리 키로 존재하는데, num(자신)과 같아지지 않았다면, tmp는 딕셔너리의 다른 키 값이면서 + num(자신)의 접두어 일 것

 

  -  예를 들어, phone_book = ["119", "97674223", "1195524421"] 로 주어졌을 때

 

    num :  "1195524421" 에 대한 반복문을 진행할 때, tmp에 "119"가 + 되었을 때

 

    tmp = "119" 는 이미 딕셔너리 키에 존재하는 값이고 + num과는 같지 않기 때문에 answer = False 처리

 

 

참고

 

  -  https://velog.io/@chaegil15/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%B4%EC%8B%9C-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D