[프로그래머스/python] 전화번호 목록

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

해시... 문제였지만 해시로 풀진 않았다.

로직

1. phone_book을 소팅해준다.

 

2. length == 1일 경우는 명백히 True 케이스이므로 바로 리턴해준다.

  (⁕ 매우 쵸큼이지만 효율성을 높여줘서 그냥 넣었다.)

 

3. prefix를 하나 설정하고,
   prefix 이후 ~ prefix와 맨 앞자리가 달라지기 전까지를 target으로 삼고

   find()로 prefix인지 확인한다.

   

 

코드

def solution(phone_book):
    length = len(phone_book)
    phone_book.sort()

    if length == 1:
        return True

    for i in range(length - 1):
        for j in range(i + 1, length):

            # 각 전화번호의 길이가 1이상이므로 0으로 하드코딩 가능
            if phone_book[i][0] != phone_book[j][0]: break

            # prefix인지 확인
            if phone_book[j].find(phone_book[i]) != -1:
                return False

    return True

 

 

나는 find()를 사용했는데 다른 코드를 보니 startswith()을 사용했길래 참고해서 바꿔보니 비슷했다.

어느쪽이 좋다 나쁘다라기 보다는 테스트 케이스마다 효율성이 조금씩 다르게 나타나는 것 뿐, 큰 차이는 없다.

 

find()를 사용했을 때

startswith()을 사용했을 때

 

통과는 했지만 찝찝했다.

 

그리고 코드가 그냥 보기에는 O(n^2)으로 보이지만
사실 find() 자체도 O(m)이라서 효율성은 더 떨어지게된다.
중간에 break 부분 감안하더라도 그래봤자 O(nlogn) * O(m) 이다.

 

이 문제는 생각보다 배울 것이 많다고 생각했던게,

다양한 접근법, 다양한 풀이들이 존재했다.

그래서 다른 코드들로 살짝 공부를 해보기로 했다.

 

다른 코드로 공부하기 1

근데 그냥 소팅 안하고 그냥 이중 for문으로 돌린 다음 두 비교 대상 문자열 중 길이가 작은 문자열을 prefix로 가정하고 비교해주는 것이다. 그냥 한 마디로 브루트 포스 방식인데 이게 더 효율성이 좋다..ㅎㅎ

(아니 근데 문자열 비교는 O(m)이면 효율성은 나랑 비슷한 것가튼뎅😂)

 

완전탐색 하는게 훨씬 더 효율성이 좋다.. 허무하다..ㅎ

다른 코드로 공부하기 2

정석적인 방법, 해쉬를 사용한 방식이다.

모든 phone_book의 요소를 hash에 넣는다(value는 상관없음)

phone_book의 모든 요소(전화번호)를 다시 순회하면서 임시 변수 temp에다가 번호 하나씩을 추가해가며 hash에 temp이 있는지 확인한다.

예를 들어 hash_map에 {'123', '23', '12'} 가 있다고 가정한다.

phone_book의 모든 요소(전화번호)를 다시 순회한다.

첫 번째 전화번호 '123'의 번호를 하나하나씩 임시 변수 temp에 추가하고 그 때마다 temp이 hash_map에 있는지 확인한다. (단, temp이 현재 번호인 '123'과 같아서는 안된다)

  1) temp = '1' → temp in hash_map = False

  2) temp = '12' → temp in hash_map = True
temp이 '12'가 되었을 때 hash_map 안에 있는 요소와 일치하는 것이 있으므로, False를 리턴하면 된다.

 

모든 요소를 순회했을 때, 일치하는 것이 없었다면 마지막에 True를 리턴한다.

확실히 효율성이 더 좋아진다.

위 방식은 list가 아닌 hash에 접근하는 방식이기 때문에 O(n^2)으로 효율성이 확실히 더 좋다.

 

다른 코드로 공부하기 3

이거 보고 regex은 생각도 못했기 때문에 헠.. 소리가 나왔당

 

먼저 간단하게 re 모듈을 복습해보면

 

점프 투 파이썬 - 정규표현식 시작하기 中 match 객체의 메서드

1. 기본 매칭 방법

1-1. 컴파일 된 패턴 객체를 여러 번 사용(매칭)할 경우 

p = re.compile(정규표현식)
m = p.match( 'string goes here' )
if m:
    print('Match found: ', m.group())
else:
    print('No match')

1-2. 한 번만 비교해줄 경우

# 컴파일과 매칭을 동시에
m = re.match('[a-z]+', "python")

2. 메타문자 사용법

• ^은 문자열의 처음을 의미
• $는 문자열의 마지막을 의미

# python이라는 문자열이 반드시 앞에 들어가야하는 패턴
re.compile("^python")

# python이라는 문자열이 반드시 뒤에 들어가야하는 패턴
re.compile("$python")

 

요 1번 2번을 잘 활용하면, 대강 각이 나온다.

사실 1번의 브루트 포스 방식과 동일하지만 prefix인지를 확인하는 방식이 다를 뿐이다.

 

이중 for 문을 돌면서 두 비교 대상이 서로 같지 않으면서, 동시에 prefix인지 re 라이브러리를 통해 확인해준다.

re 모듈을 활용해 prefix인지 확인하는 구체적인 로직은 아래와 같다.

• 대상이 되는 문자열(pivot)이 반드시 앞에 들어가는 패턴객체( p = re.compile("^"+pivot) )를 만들고,
• 비교 대상이 되는 문자열(target)을 p.match(target)을 통해 prefix인지 확인해준다.

 

효율성도 나쁘지 않다!

 

효율성 테스트는 sort()보다 좋게 나왔지만, 기본적인 테스트 케이스에서 시간이 꽤 걸렸다.

아무래도 패턴 객체를 만드는데 시간이 오래걸리지 않나... 라는 추측을.. 해본당..