Haribo Blog

알고리즘, 문제풀이, ML, AI

자물쇠와 열쇠

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

보석 쇼핑

2020-11-16

Haribo

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

Lv.3
- 보석 쇼핑 풀이
  - 코드
  - 사야할 보석 종류 리스트 구하기
보석 쇼핑 풀이

보석 쇼핑 문제 바로가기 코딩 테스트에서 시간잡아먹는 비율이 코딩 10%, 알고리즘 고안 90% 인것같다. 특히나 효율성이 포함된 문제라면…

이문제에서 효율성의 핵심은 Dictionary를 이용하는 것이다.

커서가 이동하며 장바구니(Dictionary)안에 모든 보석종류가 들어올때 까지 R 커서가 오른쪽으로 이동하고, 모든 보석 종류가 장바구니안에 들어오면 왼쪽커서를 오른쪽으로 이동시키며 범위를 줄여나간다.

최종 정답은 정답 후보중 가장 길이가 짧은(R - L) [L, R]을 return하는 것이다.

그리고 장바구니의 보석이 0개가 되면 삭제를 시켜주어야하고, 이미 있는 보석이면 +1 해주어야한다. 왜냐하면 이 문제에서 효율성을 판단하는 핵심이 바로 장바구니의 사이즈로 모든 종류의 보석을 샀는지를 판단해야하기 때문이다. **

코드
```
def solution(gems):
    products = list(set(gems))
    l = 0
    r = 0
    bucket = {}
    answer = [0, len(gems)]
    while(l <= len(gems) and r <= len(gems)) :
        if len(bucket) == len(products) :
            if answer[1]-answer[0] > r-l:
                answer = [l, r]
            bucket[gems[l]] -= 1
            if bucket[gems[l]] == 0 : del bucket[gems[l]]
            l += 1
        else :
            try :
                if gems[r] in bucket : bucket[gems[r]] += 1
                else : bucket[gems[r]] = 1
            except :
                break
            r += 1
    answer[0] += 1
    return answer
```
사야할 보석 종류 리스트 구하기

보석을 몇종류 사야하는지를 set을 이용하여 구해줍니다.
```
products = list(set(gems))
```
Read All

동굴 탐험

2020-11-16

Haribo

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

DFS/BFS Graph Lv.4

동굴 탐험 풀이
- 코드 (by.김현우)

동굴 탐험 풀이

동굴 탐험 문제 바로가기 이 문제는 어떻게 풀어야할지 감이 안잡혀서 풀이 해설을 봤지만… 해설대로 구현을 해도 효율성에서 계속 막혀서 성공한 사람의 코드중 김현우님의 코드가 가장 잘 짠거같아서 그분의 코드를 이해하고 공부했습니다.

코드 (by.김현우)

import sys
sys.setrecursionlimit(10**6)# 재귀 깊이 설정

def haveCycle(node):
    if visit[node]:
        if visit[node] == -1:
            return True
        return False
    visit[node] = -1
    for _next in inv_graph[node]:
        if haveCycle(_next):
            return True
    visit[node] = 1
    return False

def make_inv_graph(node, parent):
    for child in graph[node]:
        if child != parent:
            inv_graph[child].append(node)
            make_inv_graph(child, node)

def solution(n, path, order):
    global graph, inv_graph, visit
    graph, inv_graph, visit = [[] for _ in range(n)], [[] for _ in range(n)], [0]*n
    for parent, node in path:
        graph[parent].append(node)
        graph[node].append(parent)
    make_inv_graph(0, -1)
    for parent, node in order:
        inv_graph[node].append(parent)
    for node in range(n):
        if haveCycle(node):
            return False
    return True

Read All

22/23

Haribo Blog

자물쇠와 열쇠 풀이

코드

외벽 점검 풀이

코드

문자열 압축 풀이

코드

기둥과 보 설치 풀이

코드

괄호 변환 풀이

코드

가사 검색 풀이

코드

코드

수식 최대화 풀이

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

보석 쇼핑 풀이

코드

사야할 보석 종류 리스트 구하기

동굴 탐험 풀이

코드 (by.김현우)