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

6 minute read

오늘 한 리스트

프로그래머스 해시 2 문제
프로그래머스 스택/큐 5 문제

프로그래머스 해시 위장

문제 유형 : 해시
위장 스파이가 되기
문제 풀이
```
import itertools
import numpy as np
def solution(clothes):
  dict_clothes={}
  for i in clothes:
      if i[1] in dict_clothes:
          dict_clothes[i[1]]+=1
            
      else:
          dict_clothes[i[1]]=1
  mem=dict_clothes.keys()
  clo_list=[]
  for key, value in dict_clothes.items():
      clo_list.append(value)
  com_num=len(clo_list)
  total=0
  for i in range(com_num):
      if i ==0:
          total+=int(np.array(list(itertools.combinations(clo_list,i+1))).sum())
          #print
      else:
          for j in np.array(list(itertools.combinations(clo_list,i+1))):
              total+=int(np.prod(j))
  return total
```
가장 먼저 시도한건 dict 형태로 바꾸는걸 시도하면서 종류는 상관이 없으니 숫자로 딕셔너리로 만들었고 그에대한 clo_list를 만들어줘 경우의 수를 계산하기 위해서 위 코드처럼 작성해줬다.
결과는 (27/28)으로 테스트 1만 시간초과로 실패했다.
내가 생각했을 때 가장 시간이 오래 걸린 가능성 있는 이유는 1. numpy 사용 2. np.array(list(itertools.combinations(clo_list,i+1))) or total+=int(np.prod(j))라고 생각이 든다. 3. itertools 사용 (이건 필수로 사용해야되니 빼기로 한다.)

import itertools
import numpy as np
import math
def solution(clothes):
    dict_clothes={}
    for i in clothes:
        if i[1] in dict_clothes:
            dict_clothes[i[1]]+=1
        else:
            dict_clothes[i[1]]=1
    mem=dict_clothes.keys()
    clo_list=[]
    for key, value in dict_clothes.items():
        clo_list.append(value)
    com_num=len(clo_list)
    total=0
    for i in range(com_num):
        result = [math.prod(tup) for tup in itertools.combinations(clo_list,i+1)]
        total+=sum(result)
    
    return total

좀더 최적화 시킨 code로 전보다 약 10배 이상 속도가 빨라졌다.
하지만 아직도 시간 초과로 실패했음… 도대채 어디서 안되는지 모르겠다… 포기!
다른 사람 풀이

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

    cnt = 1
    for num in clothes_type.values():
        cnt *= num

    return cnt - 1

역으로 생각을 했어야 했는데 못한 case인 것 같다.. 존재하는 모든 옷에서 입지 않는 경우를 추가한 다음 -1을 하면 모든 옷을 입지 않는 경우만 빼주기 때문이다.
코딩 뿐만 아니라 이러한 조합이나 경우의 수를 생각하는 방법을 고민해봐야겠다.

프로그래머스 해시 베스트앨범

문제 유형 : 해시
베스트 엘범 재생목록 만들기
문제 풀이

def solution(genres, plays):
  music_dict={}
  music_num_dict={}
  for n,(i,j) in enumerate(zip(genres,plays)):
      if i in music_dict:
          music_dict[i].append([j,n])
          music_num_dict[i]+=j
      else:
          music_dict[i]=[]
          music_dict[i].append([j,n])
          music_num_dict[i]=j
  # dict value, keys 바꾸기
  music_num_dict={v:k for k,v in music_num_dict.items()}
  # dict 정렬
  music_num_dict=sorted(music_num_dict.items(),reverse=True)
  max_music=0
  answer=[]
  check_dict={}
  for i in range(len(music_num_dict)):
      if i==0:
          max_music=len(music_dict[music_num_dict[i][1]])
          m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
          for j in range(max_music):
              answer.append(m_list[j][1])
      else:
          m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
          print(m_list)
          for j in range(len(m_list)):
              if j>max_music-1:
                  continue
              answer.append(m_list[j][1])
                
  return answer

정답률 : 3/15 처참하다. 어느 케이스에서 문제인지 생각을 해보면 같은 재생횟수를 고려하지 않았다.

def solution(genres, plays):
    music_dict={}
    music_num_dict={}
    for n,(i,j) in enumerate(zip(genres,plays)):
        if i in music_dict:
            music_dict[i].append([j,n])
            music_num_dict[i]+=j
        else:
            music_dict[i]=[]
            music_dict[i].append([j,n])
            music_num_dict[i]=j
    # dict value, keys 바꾸기
    music_num_dict={v:k for k,v in music_num_dict.items()}
    # dict 정렬
    music_num_dict=sorted(music_num_dict.items(),reverse=True)
    max_music=0
    answer=[]
    for i in range(len(music_num_dict)):
        check_dict={}
        if i==0:
            max_music=len(music_dict[music_num_dict[i][1]])
            m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
            for j in m_list:
                if j[0] in check_dict:
                    check_dict[j[0]].append(j[1])
                else:
                    check_dict[j[0]]=[]
                    check_dict[j[0]].append(j[1])
            for j in check_dict.keys():
                answer+=sorted(check_dict[j])
            
        else:
            m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
            for j in m_list:
                if j[0] in check_dict:
                    check_dict[j[0]].append(j[1])
                else:
                    check_dict[j[0]]=[]
                    check_dict[j[0]].append(j[1])
            num=0
            for j in check_dict.keys():
                for k in sorted(check_dict[j]):
                    num+=1
                    if max_music<num:
                        continue
                    answer.append(k)
    return answer

test case를 좀더 추가해서 진행했다.

[“classic”, “pop”, “classic”, “classic”, “pop”, “pop”, “k-pop”, “k-pop”, “k-pop”], [500, 600, 150, 800, 2500, 2500, 1250, 250, 1250] 정답: [4, 5, 1, 6, 8, 7, 3, 0, 2]

[“classic”, “pop”, “classic”, “classic”, “pop”, “pop”], [500, 600, 150, 800, 2500, 2500] 정답: [4, 5, 1, 3, 0, 2] 최종 정답 4/15 흠…

def solution(genres, plays):
music_dict={}
music_num_dict={}
for n,(i,j) in enumerate(zip(genres,plays)):
    if i in music_dict:
        music_dict[i].append([j,n])
        music_num_dict[i]+=j
    else:
        music_dict[i]=[]
        music_dict[i].append([j,n])
        music_num_dict[i]=j
# dict value, keys 바꾸기
music_num_dict={v:k for k,v in music_num_dict.items()}
# dict 정렬
music_num_dict=sorted(music_num_dict.items(),reverse=True)
max_music=2
answer=[]
for i in range(len(music_num_dict)):
    check_dict={}
    if i==0:
        #max_music=len(music_dict[music_num_dict[i][1]])
        m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
        for j in m_list:
            if j[0] in check_dict:
                check_dict[j[0]].append(j[1])
            else:
                check_dict[j[0]]=[]
                check_dict[j[0]].append(j[1])
        num=0
        for j in check_dict.keys():
            for k in sorted(check_dict[j]):
                num+=1
                if max_music<num:
                    continue
                answer.append(k)
            
    else:
        m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
        for j in m_list:
            if j[0] in check_dict:
                check_dict[j[0]].append(j[1])
            else:
                check_dict[j[0]]=[]
                check_dict[j[0]].append(j[1])
        num=0
        for j in check_dict.keys():
            for k in sorted(check_dict[j]):
                num+=1
                if max_music<num:
                    continue
                answer.append(k)
return answer

이제 보니 2개씩만 보내는 걸로 되어있었다… ㅂㄷㅂㄷ;
위 테스트 케이스가 오히려 혼란을 가져온듯 하다.

def solution(genres, plays):
music_dict={}
music_num_dict={}
for n,(i,j) in enumerate(zip(genres,plays)):
    if i in music_dict:
        music_dict[i].append([j,n])
        music_num_dict[i]+=j
    else:
        music_dict[i]=[]
        music_dict[i].append([j,n])
        music_num_dict[i]=j
# dict value, keys 바꾸기
music_num_dict={v:k for k,v in music_num_dict.items()}
# dict 정렬
music_num_dict=sorted(music_num_dict.items(),reverse=True)
max_music=2
answer=[]
for i in range(len(music_num_dict)):
    check_dict={}
    m_list=sorted(music_dict[music_num_dict[i][1]],reverse=True)
    for j in m_list:
        if j[0] in check_dict:
            check_dict[j[0]].append(j[1])
        else:
            check_dict[j[0]]=[]
            check_dict[j[0]].append(j[1])
    num=0
    for j in check_dict.keys():
        for k in sorted(check_dict[j]):
            num+=1
            if max_music<num:
                continue
            answer.append(k)
            
return answer

최적화 한 코드이다.

프로그래머스 스택/큐 같은 숫자는 싫어

문제 유형 : 스택/큐
중복숫자 없애기

def solution(arr):
  b=10
  answer=[]
  for i in arr:
      if b!=i:
          b=i
          answer.append(b)
  return answer

바로 해결은 했지만 스택/큐로 다시 코드를 짜면

def solution(arr):
  answer=[]
  while arr:
      t1=arr.pop(0)
      if answer==[]:
          answer.append(t1)
      else:
          if t1!=answer[-1]:
              answer.append(t1)
  return answer

이랫는데 시간 초과가 뜬다 ㅎ

프로그래머스 스택/큐 작업 개수 찾기

문제 유형 : 스택/큐
작업 개수 찾기

def solution(progresses, speeds):
  answer=[]
  while progresses:
      progresses=[x+y for x,y in zip(progresses,speeds)]
      num=0
      while (progresses[0]>=100):
          num+=1
          progresses.pop(0)
          speeds.pop(0)
          if not progresses:
              break
      if num>0:
          answer.append(num)
  return answer

완료! while문을 한번 활용해보고 싶어서 사용해봤다.

프로그래머스 스택/큐 올바른 괄호

문제 유형 : 스택/큐
올바른 괄호

def solution(s):
  T1,T2=0,0
  if s[0] == ")" or s[-1]=="(":
      return False
  while s!="":
      if "()" in s:
          s=s.replace("()","")
      else:
          return False
  return True

replace를 사용해서 진행해봤고 결과는 정확도 100% 지만 효율성은 0이다. 효율성을 높이기 위해서 while문을 대체해봐야겠다.

def solution(s):
  T1,T2=0,0
  for i in range(100000):
      if "()" in s:
          s=s.replace("()","")
          if s=="":
              return True
      else:
          return False
  return True

for문 사용 확실히 좀 빠른 것 같은데 아직도 효울성은 꽝이다..

def solution(s):
    if s[0] == ")" or s[-1]=="(":
        return False
    index=[]
    for c in s:
        if "("==c:
            index.append(c)
        else:
            if not index or index.pop()!="(":
                return False
    if index:
        return False
    return True

효율성 테스트를 좀 더 구상해본 결과 앞에 있는 “(“만 확인하는 코드를 작성했음. 결과 정확도 (18/18), 효율성 (2/2)

남들이 푼 코드

def is_pair(s):
    wt = 0
    for c in s :
        if c == '(' : wt += 1
        elif c == ')' : wt -= 1
        if wt < 0 : return False
    return wt == 0

”(“, “)”에 + -를 줌으로 wt가 0이 나오도록 만든 코드 매우 깔끔하다…

프로그래머스 스택/큐 프린터

문제 유형 : 스택/큐
프린터 중요도가 높은 프린터부터 뽑기

def solution(priorities, location):
  #answer = 0
  index=[i for i in range(len(priorities))]
  last=[]
  while priorities:
      p_out=priorities.pop(0)
      ind=index.pop(0)
      for i in priorities: 
          if p_out<i:
              priorities.append(p_out)
              index.append(ind)
              continue
      if (not index) or (ind!=index[-1]):
          last.append(ind)
  answer=last.index(location)
  return answer+1

정답 (3/20) 시간 초과가 많아서 효율적인 코드를 생각했을 때 max가 있음

def solution(priorities, location):
  #answer = 0
  index=[i for i in range(len(priorities))]
  last=[]
  while priorities:
      p_out=priorities.pop(0)
      ind=index.pop(0)
      if not index:
          last.append(ind)
          continue
      if p_out< max(priorities):
          priorities.append(p_out)
          index.append(ind)
          continue
      last.append(ind)
  answer=last.index(location)
  return answer+1

max로 만들어주자마자 올클!

def solution(priorities, location):
  queue =  [(i,p) for i,p in enumerate(priorities)]
  answer = 0
  while True:
      cur = queue.pop(0)
      if any(cur[1] < q[1] for q in queue):
          queue.append(cur)
      else:
          answer += 1
          if cur[0] == location:
              return answer

any를 사용하면 어떤한 값이라도 큰게 있으면 True를 반환함 괜찮은 함수인듯 함.

프로그래머스 스택/큐 다리를 지나는 트럭

문제 유형 : 스택/큐
다리를 지나갈 때 걸리는 시간을 측정하는 코드

def solution(bridge_length, weight, truck_weights):
  answer = 0
  list_time=[]
  list_truck_ing=[]
  while truck_weights:
      answer+=1
      p_truck=truck_weights.pop(0)
      if sum(list_truck_ing)+p_truck<=weight:
          list_truck_ing.append(p_truck)
      list_time=[i+1 for i in list_time]
      list_time.append(1)
      if not truck_weights:
          answer+=bridge_length
          continue
      if sum(list_truck_ing)+truck_weights[0]<=weight:
          continue
      while sum(list_truck_ing)+truck_weights[0]>weight:
          rm_cnt=bridge_length-list_time.pop(0)
          answer+=rm_cnt
          list_truck_ing.pop(0)
          list_time=[i+rm_cnt for i in list_time]
  return answer

정답은 총 (10/14)개 맞음 시간은 충분하고 예외적으로 처리해야 할건 추가한 test case 1, 2, [1,1,1], 4 연속적으로 들어갈 때 예외처리를 안했다.

def solution(bridge_length, weight, truck_weights):
  answer = 0
  list_time=[]
  list_truck_ing=[]
  while truck_weights:
      answer+=1
      p_truck=truck_weights.pop(0)
      list_truck_ing.append(p_truck)
      list_time=[i+1 for i in list_time]
      list_time.append(1)
      if not truck_weights:
          answer+=bridge_length
          continue
      if sum(list_truck_ing)+truck_weights[0]<=weight:
          if list_time[0]==bridge_length:
              list_time.pop(0)
              list_truck_ing.pop(0)
          continue
      while sum(list_truck_ing)+truck_weights[0]>weight:
          rm_cnt=bridge_length-list_time.pop(0)
          answer+=rm_cnt
          list_truck_ing.pop(0)
          list_time=[i+rm_cnt for i in list_time]
  return answer

다른 사람 풀이
다리 길이만큼 deque를 만들어 준다음 진짜 다리를 건너는 것처럼 시뮬레이션을 해준다음 마지막은 다리 길이만큼 더해주는 걸로 끝냄

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        #print(bridge)
        #print(bridge.popleft())
        # popleft => 왼쪽에서 pop함
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

매우 잘짠 코드 같다 ㅎㅎ 하지만 실제로 테스트해본 결과 내 코드가 좀더 빨라서 기분이 좋았다.

Share on

Twitter Facebook LinkedIn

Changhee Yang

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

오늘 한 리스트

프로그래머스 해시 위장

프로그래머스 해시 베스트앨범

프로그래머스 스택/큐 같은 숫자는 싫어

프로그래머스 스택/큐 작업 개수 찾기

프로그래머스 스택/큐 올바른 괄호

프로그래머스 스택/큐 프린터

프로그래머스 스택/큐 다리를 지나는 트럭

Share on

Leave a comment

You may also enjoy

ControlNet Demo

SMPL_mesh short path algorithm (Dijkstra, pygeodesic)

Amass dataset 2D Projection (2)

Amass dataset 2D Projection