Haribo Blog

• 편집 거리

  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

  ---

• 자물쇠와 열쇠

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 자물쇠와 열쇠 풀이
    • 코드

  자물쇠와 열쇠 문제 바로가기

  자물쇠와 열쇠 풀이

  코드

  import numpy as np
  def solution(key, lock):
      N, M = len(lock), len(key)
      lock = np.pad(lock, ((M-1,M-1),(M-1,M-1)), 'constant', constant_values=0)
      for _ in range(4) :
          key = rotate(key)
          for i in range(M+N-1) :
              for j in range(M+N-1) :
                  lock_ = np.array(lock)
                  lock_[i:i+M, j:j+M] ^= key
                  if lock_[M-1 : N + M-1, M-1 : N + M-1].sum() == N**2 :
                      return True
      return False
  
  def rotate(key):
      return np.array(list(zip(*key[::-1])))
  

  ---

  Read All

  ---

• 외벽 점검

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 외벽 점검 풀이
    • 코드

  외벽 점검 문제 바로가기

  외벽 점검 풀이

  코드

  from itertools import permutations
  def solution(n, weak, dist):
      answer = []
      dists = [list(x) for x in permutations(dist)]
      weaks = [weak] + [weak[i+1:]+[x+n for x in weak[:i+1]] for i, _ in enumerate(weak[:-1])]
      for weak in weaks :
          for dist in dists :
              check = weak[0]
              for i, d in enumerate(dist) :
                  check += d
                  if check >= weak[-1] :
                      answer.append(i)
                      break
                  else :
                      check = [x for x in weak if x > check][0]
      return min(answer)+1 if answer else -1
  

  ---

  Read All

  ---

• 문자열 압축

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.2
  • 문자열 압축 풀이
    • 코드

  문자열 압축 문제 바로가기

  문자열 압축 풀이

  코드

  def solution(s):
      return min(press(s, index) for index in list(range(1, int(len(s)/2) + 1)) + [len(s)])
  
  def press(s, index) :
      result = ''
      coef = 1
      while(len(s) > index) :
          piv, s = s[:index]
          s = s[index:]
          if piv != s[:index] :
              result += str(coef) + piv if coef != 1 else piv
              coef = 0
          coef += 1
      result += str(coef)+ s if coef != 1 else s
      return len(result)
  

  랜덤여신 , Yang Sang-Ho 님의 코드를 조금 참고하였습니다.

  ---

  Read All

  ---

• 기둥과 보 설치

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.3
  • 기둥과 보 설치 풀이
    • 코드

  기둥과 보 설치 문제 바로가기

  기둥과 보 설치 풀이

  너무 어려워서 5명 정도 다른사람이 푼 코드를 보고 공부해서 다시 짰습니다. 머리가 멍청하면 몸이 고생한다는 말이 괜히 있는게 아니었습니다. 문제에서 알려주는 제한사항은 꼭 꼼꼼하게 3~4번 읽고 코드를 작성해야 한다는 사실을 깨달았습니다.

  코드

  def solution(n, build_frame):
      global N
      N = n
      answer = []
      for frame in build_frame :
          if frame[3] == 1 : # 설치
              answer.append(frame[:-1])
              if not check_rule(answer) : answer.pop() # 설치 규칙에 위배되면 넣은거 pop
          else : # 삭제
              del answer[answer.index(frame[:-1])]
              if not check_rule(answer) : answer.append(frame[:-1]) # 삭제 규칙에 위배되면 다시 삽입
      answer.sort()
      return answer
  def check_rule(answer) :
      for frame in answer :
          x, y, structure = frame
          if x < 0 or y < 0 or x > N or y > N : return False
          if structure == 0 :
              if y == 0 or [x, y, 1] in answer or [x-1, y, 1] in answer or [x, y-1, 0] in answer : continue
              else : return False
          else :
              if [x, y-1, 0] in answer or [x+1, y-1, 0] in answer or ([x-1, y, 1] in answer and [x+1, y, 1] in answer) : continue
              else : return False
      return True
  

  ---

  Read All

  ---

• 괄호 변환

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Lv.2
  • 괄호 변환 풀이
    • 코드

  괄호 변환 문제 바로가기

  괄호 변환 풀이

  코드

  def solution(p):
      if p == '' : return ''
      u, v = split(p)
      return u + solution(v) if check_right(u) else '('+ solution(v) + ')' + reverse(u[1:-1])
  def check_balance(p) :
      return str.count('(') == str.count(')')
  def check_right(p) :
      count = 0
      for i in p :
          count += 1 if i == '(' else -1
          if count < 0 : return False
      return True
  def split(p) :
      for i in range(1, len(p)+1) :
          if check_balance(p[:i]) :
              return p[:i], p[i:]
  def reverse(p) :
      return ''.join(['(' if x==')' else ')' for x in p])
  

  ---

  Read All

  ---

• 가사 검색

  2020-11-26

  Haribo

  프로그래머스  2020_KAKAO_BLIND_RECRUITMENT

  Tree  Lv.4
  • 가사 검색 풀이
    • 코드

  가사 검색 문제 바로가기

  가사 검색 풀이

  처음보는 트라이 구조 자료구조를 이용해 문제를 풀어야해서 매우 감이 안잡혔었습니다. 역시 이런문제는 한번 맞아봐야 다음부터 제대로 풀 수 있습니다. 제 기억으로 2021 공채 시험에서도 트라이 구조를 이용한 문제가 3번인가 4번으로 나왔었는데 꼭 이해하고 넘어 가시길 바랍니다.

  코드

  import re
  
  def solution(words, queries):
      answer = []
      trees = [Trie() for _ in range(10000)]
      inv_trees = [Trie() for _ in range(10000)]
      for word in words :
          trees[len(word)-1].insert(word)
          inv_trees[len(word)-1].insert(word[::-1])
      for query in queries :
          if query[0] == '?' :
              answer.append(inv_trees[len(query)-1].query(re.sub('[^a-z]', '', query[::-1])))
          else :
              answer.append(trees[len(query)-1].query(re.sub('[^a-z]', '', query)))
      return answer
  
  class TrieNode:
      def __init__(self, char):
          self.char = char
          self.counter = 0
          self.children = {}
  
  class Trie(object):
      def __init__(self):
          self.root = TrieNode("")
  
      def insert(self, word):
          node = self.root
          for char in word:
              node.counter += 1
              if char in node.children:
                  node = node.children[char]
              else:
                  new_node = TrieNode(char)
                  node.children[char] = new_node
                  node = new_node
          node.counter += 1
      def query(self, word) :
          node = self.root
          for char in word :
              if char not in node.children : return 0
              node = node.children[char]
          return node.counter
  

  ---

  Read All

  ---

• 키패드 누르기

  2020-11-16

  Haribo

  프로그래머스  2020_카카오_인턴쉽

  Lv.1
  • 코드

  2020 카카오 인턴십

  키패드 누르기 문제 바로가기

  코드

  def solution(numbers, hand):
      results = []
      left = 10
      right = 12
  
      for number in numbers :
          if number in [1, 4, 7] :
              results.append('L')
              left = number
          elif number in [3, 6, 9] :
              results.append('R')
              right = number
          else : # 2, 5, 8, 0의 경우 거리 계산
              if number == 0: number = 11
              q_l, r_l = divmod(left-1, 3) # 왼손 숫자의 좌표
              q_r, r_r = divmod(right-1, 3) # 오른손 숫자의 좌표
              q_n, r_n = divmod(number-1, 3) # 현재 숫자의 좌표
  						
              if abs(q_n - q_r) + abs(r_n - r_r) > abs(q_n - q_l) + abs(r_n - r_l):
                  results.append('L')
                  left = number
              elif abs(q_n - q_r) + abs(r_n - r_r) < abs(q_n - q_l) + abs(r_n - r_l) :
                  results.append('R')
                  right = number
              else : # 거리가 같은 경우
                  if hand == 'right' :
                      results.append('R')
                      right = number
                  else :
                      results.append('L')
                      left = number
      return ''.join(results)
  

  Read All

  ---

• 수식 최대화

  2020-11-16

  Haribo

  프로그래머스  2020_카카오_인턴쉽

  Stack/Queue  Lv.2
  • 수식 최대화 풀이
    • 시골우유, 신철호 님의 코드

  수식 최대화 문제 바로가기

  수식 최대화 풀이

  이 문제는 제가푼 코드보다 시골우유 , 신철호 님께서 푼 코드가 훨씬 간결하고 세련되어서 그 코드를 바탕으로 풀이를 해보겠습니다.

  ---

  시골우유, 신철호 님의 코드

  import re
  from itertools import permutations
  
  def solution(expression):
      #1
      op = [x for x in ['*','+','-'] if x in expression]
      op = [list(y) for y in permutations(op)]
      ex = re.split(r'(\D)',expression)
  
      #2
      a = []
      for x in op:
          _ex = ex[:]
          for y in x:
              while y in _ex:
                  tmp = _ex.index(y)
                  _ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
                  _ex = _ex[:tmp]+_ex[tmp+2:]
          a.append(_ex[-1])
  
      #3
      return max(abs(int(x)) for x in a)
  

  Read All

  ---