프로그래머스-전화번호 목록 풀이

프로그래머스에 있는 코딩테스트연습 중 해시에 있는 전화번호 목록을 풀어보았습니다.

문제는 아래와 같습니다.

출처 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42577

 

문제의 요지는 접두어를 찾으면 됩니다.

 

처음에 어떻게 할까 고민하다가... 파이썬에서 문자열을 쉽게 인덱스 할 수 있다는 점을 이용하여 풀어보았습니다.

 

파이썬의 경우 아래와 같은 형식으로 쉽게 인덱스가 가능합니다.

str = "Hello world"
print(str[0:5])
#Hello
print(str[5:])
#world
print(str[1:3])
#el
print(str[-1])
#l

마치 리스트처럼 숫자와 : 를 이용해서 문자열의 원하는 부분을 가지고 올 수있습니다. 참고로 -를 사용하면 뒤에서부터 인덱스 할 수도 있습니다.

 

어쨋든

 

일단 알고리즘은 아래와 같습니다.

1.sorted함수를 이용하여 길이를 기준으로 오름차순으로 정렬을 한 뒤(이렇게 하면 자기자신보다 뒤에 있는 번호는 자신의 접두어일수가 없습니다-나보다 큰수이기 때문에)

2.리스트의 첫번째 녀석을 접두어로 가정하여 두번째 녀석부터 마지막 녀석까지 비교를 합니다

3.첫번째 녀석의 길이를 가지고 와서 두번째 녀석의 앞부분만 인덱스하여 비교해 줍니다.

4.만약 찾았다면 바로 False를 리턴해 주고 종료

5.못찾았다면 2번~4번을 반복해줍니다 끝까지

6.이래도 다 못찾았다면 True리턴 후 종료

 

시간복잡도는 O(n^2)입니다. 아래는 코드입니다~

def solution(phone_book):
    answer = True
    #정렬하기.
    sortedPhoneBook=sorted(phone_book, key=len)
    #배열의 총 길이
    totalLen=len(sortedPhoneBook)
    #접두어가 되는 인덱스
    for prefixIndex in range(totalLen):
    	#비교대상이 되는 인덱스
        for nonPrefixIndex in range(prefixIndex+1,totalLen):
        	#접두어 번호
            prefixNumber=sortedPhoneBook[prefixIndex]
            #비교대상 번호
            nonPrefixNumber=sortedPhoneBook[nonPrefixIndex]
            prefixLen=len(prefixNumber)
            #접두어아닌지 비교하는 부분
            if str(nonPrefixNumber)[:prefixLen] == str(prefixNumber):
                answer = False
                #찾았다면 바로 리턴
                return answer
                
    return answer

주석도 있어서 알아보는데 크게 어려움을 없을것입니다.

 

제 컴퓨터에서 테스트결과는 아래와 같습니다.

쪼끔 느리다~

 

결론

1. Python에서 문자열인덱스는 간단하다

2. 이걸 해시로 어떻게 푸는걸까?

3. 프로그래밍언어의 특징을 잘 알면 조금 더 문제를 쉽게 풀 수 있다

 

-끝-