Haribo Blog

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

키패드 누르기

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

경주로 건설

2020-11-16

Haribo

프로그래머스 카카오

DFS/BFS Lv.3

코드

2020 카카오 인턴십

경주로 건설 바로가기

코드

import heapq
from collections import deque

def solution(board):
    n = len(board)
    # 상, 우, 하, 좌
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cost_board = [[[float('inf')] * 4 for _ in range(n)] for _ in range(n)]

    # 우선순위 큐 사용
    queue = []
    heapq.heappush(queue, (0, 0, 0, -1))  # 비용을 맨 앞에 두어 우선순위 결정

    while queue:
        cost, h, w, direction = heapq.heappop(queue)

        for d, (dh, dw) in enumerate(directions):
            h_new, w_new = h + dh, w + dw
            if direction != -1 and d == (direction + 2) % 4: continue # 역주행

            if 0 <= h_new < n and 0 <= w_new < n and board[h_new][w_new] == 0:
                cost_new = cost + 100
                if direction != -1 and direction != d:
                    cost_new += 500

                if cost_new <= cost_board[h_new][w_new][d]:
                    cost_board[h_new][w_new][d] = cost_new
                    heapq.heappush(queue, (cost_new, h_new, w_new, d))

    return min(cost_board[n - 1][n - 1])

Read All

24/24

Haribo Blog

키패드 누르기

코드

수식 최대화

수식 최대화 풀이

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

보석 쇼핑

보석 쇼핑 풀이

코드

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

동굴 탐험

동굴 탐험 풀이

코드 (by.김현우)

경주로 건설

코드