본문 바로가기
알고리즘 풀이

[algorithm] 페어 - 프로그래머스: 폰켓몬, 전화번호 목록

by 째깍단 2023. 6. 2.

[해시] 문제

새로운 유형을 공부하기 위해 해시 문제를 가져왔다.

 

 

 

 해시 hash

- 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값

- key : value  값을 가진다

   키 = key

   고유값 = value

- 같은 종류의 자료를 묶어서 파악하는데 사용

- 모든 데이터 값을 고유의 값인지 확인 가능

 

 

해시 알고리즘

긴 길이의 데이터를 짧은 길이의 데이터로 변환하는 알고리즘

따라서 제3자는 짧은 길이의 데이터로부터 원래의 데이터를 복구할 수 없어야 하며,

동일한 출력을 갖는 서로 다른 데이터를 찾을 수 없어야 한다

 

 

 

 

 

[해시 참고]

https://ejyoo.tistory.com/72

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

 

 

 

 

 


 

 

폰켓몬 : https://school.programmers.co.kr/learn/courses/30/lessons/1845

 

답: 

더보기

해시로 풀이하지 않았음.ㅠ

def solution(nums):
    peek = len(nums) // 2
    set_nums = len(set(nums))
    if peek < set_nums:
        return peek
    else:
        return set_nums

 

한줄로 줄여보기

def solution(nums):
    peek = (len(nums) // 2)       
    return peek if peek < len(set(nums)) else len(set(nums))\

 

 

문제 분석 및 해석

nums  => len() 으로 1/2 값을 구하기

최대한 다르게 뽑는 수를 찾기 = 중복값 없애기 = set() 집합!

같거나 작으면 nums값을 리턴.

크면 set길이를 return

 

 

과정

 

주어진 nums배열을 2로 나눈 몫을 구하고,

set으로 중복값을 제거한 집합길이를 저장

 

def solution(nums):
    peek = len(nums) // 2
    set_nums = len(set(nums))

 

 

이후 if문으로 적절한 값을 반환하도록 하였다.

 

 

 

 

 

 


 

 

 

전화번호 목록 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

 

답: 

더보기

내 답

def solution(phone_book):
    phone_list = sorted(phone_book)
    #sorted를 사용하여 번호 순으로 정렬 (숫자 크기가아닌 맨 앞 번호에 따라 정렬된다)
    
    for a, b in zip(phone_list, phone_list[1:]):
    # zip으로 list의 0+, 1+번째 요소를 각각 a, b에 저장하며 반복문
        if b.startswith(a):  #b의 앞글자와 a의 앞글자를 비교
            return False
    return True

 

 

해시 맵을 이용하여 클론코딩

 

def solution(phone_book): 
    # hash map 생성하기
    hash_map = {} 
    for book in phone_book: 
        hash_map[book] = 1
    # print(hash_map) {'119':1, "97674223":1, "1195524421":1}
    
    # 접두어가 Hash map에 존재하는지 찾기 
    for phone in phone_book: 
        arr = "" 
        for p in phone: 
            arr += p   # 앞에서 한글자씩 더해주는 것임!! 1  11  119 ...
            # hash_map의 key에 값이 들어있는지 확인, 자기자신일 경우는 제외
            if arr in hash_map and arr != phone:       
                return False
    return True

 

 

문제 분석 및 해석

""" 

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인

"""

 

생각한 풀이

각 요소들의 앞 2글자 꺼내기

해당 요소들끼리 비교하기

동일한 것이 있으면 false

 

이 과정대로 풀이하였는데 테스트 케이스 중 실패한 것이 있고, 효율성 테스트도 4개모두 실패하였음

 

 

 

 

그래서 startswith()함수 / 클론코딩을 하며 공부함

풀이는 답에 주석으로 달아두었다.

 

 

 

 

 

 

 

 


 

 

 

아래 두 풀이는 같아보이지만, 하나는 실패케이스가 뜬다. 왜인지 생각해보기

 

def solution(phone_book):
    phone_book.sort()
    for a, b in zip(phone_book, phone_book[1:]):
        if b.startswith(a):
            return False
    return True

 

def solution(phone_book):
    phone_book.sort()
    for a, b in zip(phone_book, phone_book[1:]):
        if b.startswith(a):
            return False
    	else:
            return True

 

 

>>>

더보기

else:  return True 를 넣었을 때 

for문에서 모든 값을 확인하고 True값을 반환하는 것이아닌,

중간에 if문 충족을 못할시 True를 반환하는 형식으로 되어있기 때문!