[프로그래머스_python] 전화번호 목록 || 42577

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

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

진짜로............해시를 어떻게 이용해주어야 하는 건지,,,,,, 접두사만 어떻게 비교해주어야 하는건지.........
ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ여러번 시도를 해주었었다. 결국에는 해시를 이용해주지 않고 문제를 풀어주었었는데,
접두사만 비교할 수 있는 함수가 따로 있었던 게 기억이 났다.. 시도를 안해주었었지만,, 오늘 해주었다!

 

 def solution(pb): #?실패한 코드,, 런타임 에러도 났다
     for i in pb:
         cnt = 0
         for j in pb:
             for x in range(len(i)):
                 if i[x] == j[x]:
                    cnt += 1
                 else:
                     break
         if cnt == len(i):
             return True
         else:
             return False

일단 주어진 phone_book에서의 길이가 모두 제각각일 수도 있어서 인덱스 1의 길이만큼 2와 비교를 해주기엔 2의 길이가 더 짧을 수도 있으므로,,,,, 탈락!
 

#? 실패한 코드2! 값을 잘 나오지만 시간초과,,,ㅠㅠ
def solution(pb):
    pb.sort()
    cnt = 0
    for i in range(len(pb)):
        for j in pb[i+1:]:
            if pb[i] == j[:len(pb[i])]:
                cnt += 1
    if cnt == 0:
        return True
    else:
        return False 

이것만큼은 맞았으리라 생각했는데,, 시간초과가 되면서 너무너무 슬퍼했었다...ㅋㅋㅋㅋㅋ
참고로 pb는 문자열로 이루어진 list여서 pb.sort()를 해주면 숫자별로 오름차순으로 정렬된다.! (사전순 정렬)

#? 성공! 해시를 이용한 건 아닌 것 같은데ㅎㅎ,,
def solution(pb):
    pb.sort()
    cnt = 0
    for i in range(len(pb)):
        for j in pb[i+1:]:
            if pb[i] == j[:len(pb[i])]:
                return False
    return True

알고보니 그냥 필요없었던 cnt를 갖다 치워버리면 됐었다...ㅎㅎ

---

def solution(pb):
    for i in range(len(pb)-1):
        for j in range(i+1,len(pb)):
            if len(pb[i]) <= len(pb[j]):
                if pb[i] == pb[j][:len(pb[i])]:
                    return False
            else:
                if pb[j] == pb[i][:len(pb[j])]:
                    return False
    return True

이 코드는 sort를 이용해주지 않았을 경우, 조건을 추가해주어야 해서 조건을 추가하고 풀어준 코드이다.
이거를 간략하게 한 것이 바로 윗 코드!

---

접두사를 확인해볼 수 있는 함수는 startswith( )이다.
그리고 i를 전체에서 돌리고, j는 i 다음차례부터 돌리고 싶은 경우,
바로 윗 코드들처럼 i+1로 해주는 경우가 있고, 조건문으로 i != j를 추가해 주는 경우가 있고,

def solution(pb):
    pb.sort()
    for i, j in zip(pb, pb[1:]):
        if j.startswith(i):
            return False
    return True

이렇게 zip으로 묶어주는 경우가 있다...! zip이 이럴 때 쓰이라고 있는 거구나를 느낌.. 
 

---

아니 그러면 이 문제가 해시에 관련된 문제라는데,, 해시로는 대체 어떻게 풀어주는 건가 했다..
프로그래머스에서 다른 분의 코드를 보고 풀어보았는데!

def solution(pb):
    hash = {}
    for i in pb:
        hash[i] = 1
    for i in pb:
        temp = ""
        for j in i:
            temp += j
            if temp in hash and temp != i:
                return False
    return True

주어진 전화번호를 단순히 그냥 hash형태로 표현을 해주고, temp에 하나하나 문자열을 붙여주면서
이미 hash안에 존재는 하는데 기존값과는 다르다면, 다른 전화번호의 접두어에 해당하므로 false를 출력되도록 하였다.
우오......... 대박이다...ㅎㅎ
 
이 문제는 증말 다음에 또 풀어봐야지 
 
 
참고)
yuuj.tistory.com/24

[PYTHON] 프로그래머스 #42577 전화번호 목록