세무민의 알고가자 : [프로그래머스] 전화번호 목록 문제 풀기

이번에 풀어볼 문제는 전화번호 목록 문제!

생각보다 쉬웠지만 삽질을 조금 많이함 ㅎ

---

문제 설명

 

 

---

제한 사항 및 입출력 예시

---

풀이

사실 이번 문제는 쉽게 접근할 수 있는 문제 중 하나이다.

위의 예시처럼 i번째 문자열이 i+1번째 문자열에 포함이 된다면 False를 반환하면 되구 

포함되는 접두사가 하나도 없다면? True를 반환하면 된다.

곰곰히 생각하다가 문제를 풀 방법은 딱 2가지가 생각났다. 

첫번째 : 2중 For문을 돌리면서 하나씩 확인해보기 

2중 포문으로 사용하는건 정확한 방법이지만 N^2 시간복잡도가 소요되기 때문에 효율성에서 많이 떨어진다.

두번째 : 정렬을 한번 해준 후 하나씩 증가하면서 확인하기

정렬을 이용하는 방법을 생각한 걸 예시로 보여드리면 

위에 처럼 문자열 정렬을 하게 되면 포함된 값이 존재하는지 쉽게 확인할 수 있다.

---

코드

1. 반복문을 이용한 방법

 def solution(phone_book): 
   checking = True
   checktext = ""

    while len(phone_book) > 0:
        checktext = phone_book[0]
        phone_book = phone_book[1:]
        checkstr = (' '.join(phone_book))
        numbering = checkstr.find(checktext)
        if numbering == -1:
            checktext = ""
        else:
            checking = False
            break
    
    return checking

2중 For문을 사용하게 되면 효율성 부분에서 많이 떨어지는 것을 알 수 있다.

우선 find를 이용해서 문자열을 비교해주고 존재한다면 False를 반환해주는 코드를 작성했다.

그렇지만 테스트케이스 4개에 실패했다.

곰곰히 생각해보면 이렇게 비교하다보면 오차가 생길 수 있다는 생각이 들었다.

1. 정렬을 이용한 방법

def solution(phone_book):
    checking = True
    phone_book.sort()
    for i in range(len(phone_book) - 1):
        if phone_book[i] in phone_book[i+1]:    
            checking = False
            break
            
    return checking

정렬을 이용한 방법으로 작성해봤다.

포함된 값이 존재한다면 False를 반환시켰다.

끄읕!

---

다음에는 더 좋은 알고리즘 포스팅으로 찾아오겠습니다.