2023 팀네이버 신입 공채 준비 (2) 프로그래머스 해시

오늘 한 리스트

1. 프로그래머스 해시 3 문제

프로그래머스 해시 포켓몬

• 문제 유형 : 해시 최대한 고를 수 있는 포켓몬 고르기 문제 풀이

  def solution(nums):
    CP_nums=len(nums)/2
    kindof_P=list(set(nums))
    if CP_nums <= len(kindof_P):
        return CP_nums
    else:
        return len(kindof_P)
  

• 중요했던 Code => set 중복을 없애주는 코드로 memory 사용량을 줄이는 방법을 택함
  1. 포켓몬 전체 수를 구함
  2. 어떤 종류의 포켓몬이 있는지 set 함수를 통해 중복을 제거함
  3. 종류의 포켓몬이 더 많으면 CP_nums를 출력 아니면 kindof_P를 출력

이유 : 종류가 많으면 고를 수 있는 포켓몬이 최대치에서 반밖에 안되고 종류 포켓몬이 적으면 고를 수 있는 포켓몬의 갯수가 정해지기 때문임
다른 사람 풀이

def solution(ls):
    return min(len(ls)/2, len(set(ls)))

=> 더 작은 숫자를 고를 코드를 한번에 고름

프로그래머스 해시 완주하지 못한 선수

• 문제 유형 : 해시 마라톤 완주 못한 사람 찾기 while 문을 사용한 풀이

  def solution(participant, completion):
    while completion:
        com_p=completion.pop(0)
        participant.pop(participant.index(com_p))
    return participant[0]
  

  문제는 전부 맞췄지만 효율성 test에서 실패함 이유 => index를 찾을 때 리스트의 크기에 따라서 너무 큰 계산량이 요구 됨.

dict 이용

def list_to_dict(list_p):
    p_dict={}
    for i in list_p:
        if i in p_dict:
            p_dict[i]+=1
        else:
            p_dict[i]=1
    return p_dict

def solution(participant, completion):
    res_dict=list_to_dict(participant)
    res1_dict=list_to_dict(completion)
    if res_dict.keys() != res1_dict.keys():
        return [x for x in list(res_dict) if x not in list(res1_dict)][0]
    else:
        check_id=list(res_dict.keys())
        for id in check_id:
            if res_dict[id]!=res1_dict[id]:
                return id

이 코드도 문제는 전부 맞췃지만 효울성 test 5문제에서 1문제 밖에 못맞췄다.
이유가 무엇인가 고민을 해봤을 때 [x for x in list(res_dict) if x not in list(res1_dict)][0]이 코드에서 list를 포함한 것이 문제가 될 것 같아서 제거해서 진행해봤다.

def list_to_dict(list_p):
    p_dict={}
    for i in list_p:
        if i in p_dict:
            p_dict[i]+=1
        else:
            p_dict[i]=1
    return p_dict

def solution(participant, completion):
    res_dict=list_to_dict(participant)
    res1_dict=list_to_dict(completion)
    if res_dict.keys() != res1_dict.keys():
        return [x for x in res_dict if x not in res1_dict][0]
    else:
        check_id=list(res_dict.keys())
        for id in check_id:
            if res_dict[id]!=res1_dict[id]:
                return id

모든 문제를 통과하고 효율성도 모두 통과했다. keys를 가져오게 되면 dict형태로 가져오게 되는데 굳이 list로 바꾸지 않아도 되고 list를 바꾼 순간 매우 높은 computation이 되어서 실패한 듯하다. 담부턴 이런 실수하지 말아야겠다.

다른 사람 풀이

import collections
def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

이걸 보고 처음 두눈을 의심했다.
collections.Counter는 내가 만들어준 def list_to_dict와 같은 결과 값을 보낸다고 생각하면 되는데 여기서 카운터 객체는 서로 뺄수가 있다고 한다. 그래서 위 값이 가능한 거라고 ㄷㄷ;; 고수의 세계는 너무 어지럽다.

프로그래머스 해시 전화번호 목록

• 문제 유형 : 해시 전화번호 겹치는지 않겹치는지 찾기 dict.keys()를 활용해 풀기

  def solution(pb):
    dict_pb = dict.fromkeys(sorted(pb))
    for i in dict_pb.keys():
        num=0
        for j in dict_pb.keys():
            if i in j:
                num+=1
        if num==2:
            return False
    return True
  

  이전의 실수를 덮기위해 list를 사용하지 않고 풀어봤다.

  1. sorted로 우선 정렬을 해줌
  2. dict으로 보내는 코드를 해줌
  3. keys()를 이용해 for문을 돌리는데 만약 keys안에 번호가 있을 경우 False로 만들게끔 했다. 예를 들어 ‘119’ ‘119256’은 if i in j에 포함된다.

결과 => 정확성 62.5(15/20), 효율성 8.3(2/4)
코드를 확인해본 결과 num>=2일 떄를 생각 못햇다.

def solution(pb):
    dict_pb = dict.fromkeys(sorted(pb))
    for i in dict_pb.keys():
        num=0
        for j in dict_pb.keys():
            if i in j:
                num+=1
        if num>=2:
            return False
    return True

결과 => 정확성 62.5(16/20), 효율성 8.3(2/4)
뭔가 잘못된 것 같다. 생각하지 못한 case가 있는 것 같은데 코드를 좀더 바꿔보기로 했다.

def solution(pb):
    dict_pb = dict.fromkeys(sorted(pb))
    bf_mem=''
    for i in dict_pb.keys():
        if bf_mem!='' and bf_mem in i:
            return False
        bf_mem=i
        
    return True

이 코드는 앞에 잇던 key 값을 저장한 후에 다음 for 문을 거칠 때 값을 확인하는 코드다.
결과 =>(19/20), 효율성 (4/4) 하나 케이스가 뭔지 모르겠는데 좀더 생각해 봐야겠다.
인터넷에 검색해본 결과 in 함수는 [‘123’,’2123] 일때 True를 배출한다고 한다. 따라서 이 케이스를 제외시킬 수 있는 코드를 다시 짜야한다.

def solution(pb):
    dict_pb = dict.fromkeys(sorted(pb))
    bf_mem=''
    for i in dict_pb.keys():
        if bf_mem!='' and bf_mem in i:
            length=len(bf_mem)
            num=0
            for n,j in enumerate(bf_mem):
                if j==i[n]:
                    num+=1
            if num==length:
                return False
        bf_mem=i
        
    return True

결과 => 완풀

다른 사람 문제 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

startswith는 어떤 문자열이 특정 문자로 시작하는지 확인하는 코드임. 처음알았다 ㅎ