알고리즘 문제 풀이 - 해시

프로그래머스 문제 풀이

완주하지 못한 선수

1. Sort를 이용한 해결
   • comple, parti를 sort
   • for문을 돌면서 comple[i]와 parti[i]가 맞지 않으면 break
     ex) {eden, leo, kiki} {eden, kiki}
   • 다 돌았는데도 break에 걸리지 않으면 parti에 마지막 인자값이 정답 (for else)
   • 주의점은 completion의 길이만큼 for문을 돌아야 함. comple=parti-1 이기 때문에 parti로 돌릴 경우 마지막 i가 못 들어감

def solution1(participant, completion):
    participant.sort()
    completion.sort()

    answer = ''
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break;

    else:
        answer = participant[len(participant) - 1]

    # print(answer)

    return answer

2. hash를 이용한 해결법
   • parti에 대해 hashMap을 만든다
     {eden=2, leo=1, kiki=1}
   • comple에 빼준다.
     {eden=1, leo=0, kiki=0}
   • value가 0이 아닌 값이 정답

def solution2(participant, completion):
    answer = ''
    data = dict()
    for i in participant:
        if i in data.keys():
            v = data[i]
            data[i] = v + 1

        else:
            data[i] = 1

    for i in completion:
        v = data[i]
        data[i] = v - 1

    for k, v in data.items():
        if v != 0:
            answer = k

    return answer

전화번호 목록

1. Sort 후 2중 for문을 이용해서 전체 비교 -> 시간 복잡도 에러 발생 (해결 방법 X)

2. Sort 후 바로 앞만 확인, 이미 문자열로 정렬되어 있는 상태이기 때문에 바로 앞만 비교 하면 됨
   

3. HashMap을 이용

• hashMap이나 hashSet에 data값 저장
• 하나씩 빼가면서
  1
  11
  119
  1195
  ...
  데이터가 dict에 있는지 확인, 있다면 false, 단 자기 자신은 제외
  

def solution(phone_book):
    answer = True


    # 방법 1 (시간 초과)
    # phone_book.sort()
    # for i in range(len(phone_book)):
    #     for j in range( i +1 ,len(phone_book)):
    #         if phone_book[j].startswith(phone_book[i]):
    #             return False

    # 방법 2 (sort를 이용하여 바로 앞만 확인)
    # phone_book.sort()
    # for i in range(len(phone_book)-1):
    #     if phone_book[i+1].startswith(phone_book[i]):
    #         answer=False

    # 방법 3. (해시를 이용)
    data = dict()
    for i in phone_book:
        data[i] = 1

    for num in phone_book:
        temp = ""
        for j in num:
            temp += j 
            if temp in phone_book and temp != num: 
                answer = False



    return answer