프로그래머스_전화번호 목록

1. 문제

출처 : 프로그래머스

2. 소스코드 ( python3 )

def solution(phone_book):     answer = True     for i in range(len(phone_book)):         for j in range(i+1, len(phone_book)):             I, J = str(phone_book[i]), str(phone_book[j])             lenI, lenJ = len(I), len(J)             if lenI > lenJ:                 if I[:lenJ] == J : return False             else:                 if I == J[:lenI] : return False                  return answer

 

3. 고찰

1) 문제 이해

하나의 번호가 다른 번호의 앞에 오는지를 확인하는 문제이다.

처음에 문제를, 한 번호가 다른 번호에 속해있는지 확인하는 문제로 착각해서 잘못 풀었었다.

즉 예를 들어 '31' '1' 의 답은 True이고

'31', '3'의 답은 False이다.

 

2) 알고리즘

for i : 모든 원소에 대해서 확인하고,

    for j : i 다음 원소들에 대해서 확인한다.

        i, j번째 원소를 각각 string형태로 받아온다.

        각 번호들의 길이를 각각 받아온 후

        I의 길이가 길면, I의 앞부분과 J의 번호가 일치하는 지 확인하고,

        J의 길이가 길면, J의 앞부분과 I의 번호가 일치하는 지 확인한다.

        일치한다면 False 리턴.

이중 for문을 다 돌았는데 일치하지 않았다면 True를 리턴한다.

 

3) 시간복잡도

이중 for문을 돌리기 때문에 입력으로 N개의 번호가 들어온다면

이 코드의 시간복잡도는 O(N^2)이다.