[프로그래머스] 코딩테스트 고득점 Kit > 전화번호 목록

# 문제

# 문제 접근

phone_book의 길이가 1,000,000 이기 때문에 이중루프로 돌면 시간초과가 날 것이 분명하기 때문에 다른 방법을 생각해야 한다.

A 번호가 B 번호의 접두어 이려면, B번호에서 앞에서부터 A번호 만큼의 길이를 잘라낸 부분이 A와 동일해야 한다.

phone_book을 순회하며 한 전화번호를 앞에서부터 잘라가며 접두어 리스트를 만들어 놓고 있는지 없는지 판별하면 될 것 같다.

그런데 생각해보니 단순히 리스트면 시간초과가 날 것 같으니, 읽는 속도가 빠른 set을 사용하도록 하자.

# 문제 풀이

1. 접두어들을 저장할 set을 만든다.

2. phone_book 리스트를 순회하며 전화번호의 앞에서부터 1글자, 2글자, .. N글자 까지의 접두어를 위의 set에 저장한다.

3. set은 중복을 허용하지 않지만, 없는 경우에만 저장하도록 하자.

4. 다시 phone_book 리스트를 순회하며 phone이 위의 set에 존재하는지 확인하자.

5. 존재한다면 answer 가 False가 되고 더 이상 순회할 필요 없으므로 break 하자.

6. 결과값을 반환하자.

# 코드 작성

def solution(phone_book):
    answer = True
    
    # 1. 비어있는 set 생성
    prefix_set = set()
    
    # 2. phone_book 리스트를 순회
    for phone in phone_book :
    
    	# 3. phone의 길이만큼 루프
        for j in range(len(phone)) :
        	# 4. 0 부터 j길이 까지 잘라서 접두어 생성
            prefix = phone[0:j]
            
            # 5. 접두어가 set에 없으면 add
            if prefix not in prefix_set :
                prefix_set.add(prefix)
    
    # 6. phone_book 리스트를 순회
    for phone in phone_book :
    
    	# 7. phone이 접두어 set에 존재하면 answer를 False로 바꾸고 break 
        if phone in prefix_set :
            answer = False
            break
    
    # 8. 위 과정에서 결정된 answer 반환
    return answer

 

 * 본 문제의 출처는 프로그래머스(https://programmers.co.kr/) 입니다. 문제가 될 시 삭제하겠습니다.