Haribo Blog

• 나누어 떨어지는 숫자 배열

  2021-01-16

  Haribo

  프로그래머스

  Lv.1
  • 코드

  나누어 떨어지는 숫자 배열 바로가기

  코드

  def solution(arr, divisor):
      answer = sorted([num for num in arr if num%divisor == 0])
      return answer if answer else [-1]
  

  Read All

  ---

• 같은 숫자는 싫어

  2021-01-16

  Haribo

  프로그래머스

  Lv.1
  • 코드

  같은 숫자는 싫어 바로가기

  코드

  def solution(arr):
      new_arr = []
      for num in arr :
          if num not in new_arr[-1:]: new_arr.append(num)
      return new_arr
  

  Read All

  ---

• 가운데 글자 가져오기

  2021-01-16

  Haribo

  프로그래머스

  Lv.1
  • 코드

  가운데 글자 가져오기 바로가기

  코드

  def solution(s):
      return s[len(s)//2-1:len(s)//2+1]
  

  Read All

  ---

• K번째수

  2021-01-16

  Haribo

  프로그래머스

  Lv.1
  • 코드

  K번째수

  코드

  def solution(array, commands):
      return [sorted(array[i-1:j])[k-1] for i, j, k in commands]
  

  Read All

  ---

• 3진법 뒤집기

  2021-01-16

  Haribo

  프로그래머스  월간_코드_챌린지_시즌1

  Lv.1
  • 코드

  3진법 뒤집기

  코드

  def solution(n):
      ternary = ''
      while n > 0: #3진법 수를 뒤집으며 생성
          n, remainder = divmod(n, 3)
          ternary += str(remainder)
  
      return int(ternary, 3)
  

  Read All

  ---

• 2016년

  2021-01-16

  Haribo

  프로그래머스

  Lv.1
  • 코드

  2016년

  코드

  import datetime
  def solution(a, b):
      answer = ['MON','TUE','WED','THU','FRI','SAT', 'SUN']
      return answer[datetime.date(2016,a,b).weekday()]
  

  Read All

  ---

• 가짜 해밀토니안

  2021-01-15

  Haribo

  프로그래머스  월간_코드_챌린지_시즌1

  Tree  DP  DFS/BFS  Lv.5
  • 가짜 해밀토니안
    • 코드

  가짜 해밀토니안

  다시 쓸예정. 참고ㄴㄴ

  코드

  import sys
  sys.setrecursionlimit(400000)
  from collections import defaultdict
  def set_depth_subtree(node, prev) :
      sub_trees, depths = [], []
      for child in graph[node] :
          if child == prev : continue
          set_depth_subtree(child, node)
          sub_trees.append((sub_tree[child], child))
          depths.append((depth[child], child))
          depth[node] = max(depth[node], depth[child] + 1)
      sub_trees.sort(reverse=True)
      depths.sort(reverse=True)
      if len(sub_trees) >= 2 :
          if sub_trees[0][1] != depths[0][1] : sub_tree[node] = sub_trees[0][0] + depths[0][0] + 1
          else : sub_tree[node] = max(sub_trees[0][0] + depths[1][0] + 1, sub_trees[1][0]+depths[0][0] + 1)
      elif len(sub_trees) == 1 : sub_tree[node] = sub_trees[0][0] + 1
  
  
  def DFS(node, prev, height) :
      global answer
      sub_trees, depths = [], []
      for child in graph[node] :
          if child == prev : continue
          sub_trees.append((sub_tree[child], child))
          depths.append((depth[child], child))
      sub_trees.sort(reverse=True)
      depths.sort(reverse=True)
      for child in graph[node] :
          if child == prev : continue
          next_height = height + 1
          if depths[0][1] != child :
              next_height = max(next_height, depths[0][0] + 2)
          elif len(depths) >= 2 and depths[0][1] == child :
              next_height = max(next_height, depths[1][0] + 2)
          DFS(child, node, next_height)
      if (len(sub_trees) >= 3) :
          answer = max(answer,
                       sub_trees[0][0]+sub_trees[1][0]+height,
                       sub_trees[0][0]+sub_trees[2][0]+depths[1][0]+1,
                       sub_trees[0][0]+sub_trees[1][0]+depths[2][0]+1)
      elif (len(sub_trees) == 2) :
          answer = max(answer, sub_trees[0][0]+sub_trees[1][0]+height)
  
  def solution(t):
      global  answer, N, graph, sub_tree, depth
      N = len(t) + 1
      graph = defaultdict(list)
      sub_tree, depth = [1]*N, [1]*N
      answer = 0
      for v1, v2 in t:
          graph[v1].append(v2)
          graph[v2].append(v1)
      set_depth_subtree(0, -1)
      DFS(0, -1, 1)
      return answer
  

  ---

  Read All

  ---

• 방의 갯수

  2020-12-29

  Haribo

  프로그래머스

  Lv.5
  • 방의 갯수
    • 코드

  방의 갯수

  계속 시간초과가 뜨길래 list말고 dictionary를 쓰니 허무하게 바로 통과되었습니다. 정적인 자료구조는 list를 쓰고 동적인 자료구조는 dictionary를 쓰는것이 훨씬 이득인것 같습니다.

  ---

  코드

  from collections import defaultdict
  
  def add(x, y) :
      return [(x[0]+y[0]/2, x[1]+y[1]/2), (x[0]+y[0], x[1]+y[1])]
  def check(point, next_, arrow) :
      return next_ in points and arrow not in points[point] and (arrow+4)%8 not in points[next_]
  def solution(arrows):
      global points
      answer = 0
      move = [(-1,  0), (-1,  1), (0,  1), (1,  1), (1,  0), (1, -1), (0, -1), (-1, -1)]
      points = defaultdict(set)
      point = (0, 0)
      for arrow in arrows :
          for next_ in add(point, move[arrow]) :
              answer += 1 if check(point, next_, arrow) else 0
              points[point].add(arrow)
              point = next_
      return answer
  

  ---

  Read All

  ---

• 편집 거리

  2020-12-20

  Haribo

  Algorithm

  DP
  • 편집 거리(Edit Distance)

  편집 거리(Edit Distance)

  ---

  정확하게 기억은 나지 않지만 카카오 2020 겨울 인턴 코딩테스트에 편집거리에 관한 문제가 있었습니다.

  편집거리는 두 단어의 유사도의 크기를 측정하는 단위입니다. 제 예상이지만 검색엔진에 잘못된 단어를 검색 했을 때, 단어를 추천해주는 알고리즘이 바로 편집거리 알고리즘이 아닐까 생각합니다.

  

  두 단어 economy 와 yummy 를 한번 보겠습니다. 두 단어는 길이도 틀리고, 시작 알파벳도 틀립니다.

  ---

  Read All

  ---

• 블록 이동하기

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  DFS/BFS  Graph  Lv.3
  • 블록 이동하기 풀이
  • 코드

  블록 이동하기 문제 바로가기

  블록 이동하기 풀이

  코드

  import numpy as np
  from collections import deque
  def sort_(state) : return sorted(state, key=lambda x : (x[0], x[1]))
  def add(x, y) : return (x[0]+y[0], x[1]+y[1])
  def check(head, tail) : return Board[head[0], head[1]] == 0 and Board[tail[0], tail[1]] == 0
  def check_(state, move, cord) : return cord != state and cord not in move
  def moving(head, tail) :
      state = sort_([head, tail])
      moving = [[1, 0], [-1, 0], [0, 1], [0, -1]]
      move = [sort_([add(head,x), add(tail, x)]) for x in moving if check(add(head, x), add(tail, x))]
      rotate = [sort_([head, add(head, x)]) for x in moving  if check(head, add(head, x)) and check(tail, add(tail, x)) and check_(state, move, sort_([head, add(head, x)]))] +\
               [sort_([tail, add(tail, x)]) for x in moving  if check(head, add(head, x)) and check(tail, add(tail, x)) and check_(state, move, sort_([head, add(head, x)]))]
      return move+rotate
  def solution(board):
      global Board, N
      N = len(board)
      Board = np.pad(board, ((1,1),(1,1)), 'constant', constant_values=1)
      que = deque([[(1, 1), (1, 2), 0]])
      visted = [[(1, 1), (1, 2)]]
      while que:
          head, tail, cost  = que.popleft()
          if head == (N, N) or tail == (N, N):
              return cost
          for child in moving(head, tail):
              if child not in visted:
                  que.append([*child, cost+1])
                  visted.append(child)
  

  ---

  Read All

  ---