(프로그래머스 with python) 전화번호 목록
전화번호 목록 (Level2)
입출력 예제를 보면 각각 요소들이 다음의 인덱스에 있는 요소값들과 서로 비교해 똑같이 중복이 되면 fasle를 리턴해야 하는 문제이다. 해시를 사용하면 더 효율적으로 해결할 수 있다고 했지만 아직은 잘 모르겠다..(해시 없이 풀 수 있기 때문이다..^^)
문제에 처음 접근하는 과정도 아이디어가 떠오르지 않아 힘들었다. 일단 각 리스트에 있는 요소값들을 비교하기 위해서는 for문을 사용해야 할 것 같았다. 그래서 생각해낸 로직은 아래와 같다.
phone_book 리스트를 반복해서 돌리면서 그 안에 있는 요소와 그 다음에 있는 요소의 값을 비교하기 위해 또다시 for문을 돌려 i+1 인덱스값부터 가져와 i의 인덱스에 있는 값과 i+1에 있는 데이터를 가져와 startswith메서드를 사용하여 비교하였다.
def solution(phone_book):
phone_dict = {}
for i in range(len(phone_book)):
for j in range(i+1, len(phone_book)):
print(phone_book[i], phone_book[j], phone_book[j].startswith(phone_book[i]))
phone_dict[phone_book[i]] = phone_book[j].startswith(phone_book[i]) # 존재시 true로 반환하기 때문에 false로 반환
if True not in phone_dict.values():
return True
else:
return False
startswith, endswith(알고있다면 이 부분은 건너뛰어도 된다)
알고리즘을 풀때 startswith메서드를 가지고 풀었던 기억이 났었다. (정확한 방법을 몰라 찾아보았다.)
startswith
주어진 문자열의 시작부분을 판단하여 () 안에 있는 조건을 만족하면 True를 반환해주는 메서드이다. 코드를 참고해보자
a = ['123', '3455', '12']
for i in range(len(a)):
for j in a[i+1:]:
print(a[i], j, a[i].startswith(j))
"""
123 3455 False
123 12 True
3455 12 False
"""
startswith() 에서 a[i]의 값이 j로 시작되는 문자열이 맞으면 True를 반환해준다. 해당 문자열이 쓰였는지 비교하고 싶으면 그 대상의 값을 () 안에 써주면 된다. (나는 이부분이 좀 헷갈린다..^^)
endswith
startswith와 반대라고 생각하면 된다. a[i]의 값이 j의 값으로 끝이나면 True를 반환해준다
a = ['312', '3455', '12']
for i in range(len(a)):
for j in a[i+1:]:
print(a[i], j, a[i].endswith(j))
"""
312 3455 False
312 12 True
3455 12 False
"""
다시 돌아와서 내가 푼 로직에는 문제가 있었다. if True not in phone_dict.values(): 이 부분의 조건에서 자꾸 걸렸다. 그래서 list로 변경하여 풀어주었다. 일단 답은 잘 나왔다. 실제로 코드를 돌려보면 정확성: 70.8로 틀리는 테스트케이스도 존재하였고 효율성은 0점이였다. 아마 중첩 for문을 써서 o(n^2)의 시간복잡도가 나와서 그런것 같다.
def solution(phone_book):
book_list = []
for i in range(len(phone_book)-1):
for j in phone_book[i+1:]:
print(phone_book[i],j)
book_list.append(j.startswith(phone_book[i]))
if True not in book_list:
return True
else:
return False
계속 생각해보다 질문하기의 도움을 받았다. 대부분 먼저 sort()를 통해서 문자열을 정렬해준뒤 인덱스 0,1 0,2 0,3 이렇게 비교하지 않고 0,1 1,2 2,3 이런식으로 비교를 해주었다.
왜 그런가 하니 sort()로 정렬을 하면 이미 앞의 숫자가 똑같은경우는 바로 다음 인덱스의 값으로 나올것이다. 하나라도 값이 나오게 되면 그 리스트는 True가 되기 때문에 굳이 인덱스마다 비교를 해주지 않아도 된다.
이후 중첩 for문을 쓰지 않기 위해 애초에 요소의 길이값을 받은 후 [i : 요소의 길이값] <- 이렇게 리스트를 슬라이싱하여 startswith를 사용하였다.
'''
def solution(phone_book):
phone_book.sort() # 정렬
book_list = []
for i in range(1, len(phone_book)):
j = len(phone_book[i-1]) # 요소의 길이값
book_list.append(phone_book[i][0:j].startswith(phone_book[i-1][0:j]))
if True not in book_list:
return True
else:
return False
사실 zip과 startswith를 사용하면 훨씬 간단하게 값을 구할 수 있다
def solution(phoneBook):
phoneBook = sorted(phoneBook)
for p1, p2 in zip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
return False
return True