ok-lab

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 위 형태로 Triangle을 구성하면 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 가 된다. 먼저 문제를 풀기 전에 Index Error가 발생하지 않도록 각 행의 양 옆에 [0]을 P..

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000 자리 이하인 숫자입니다. k는 1이상, number의 자릿수 미만인 자연수입니다. 해당 문제는 탐욕법(Greedy) 방식으로 접근하는 문제다. d..

해당 문제는 Summer/Winter Codding(~2018)에 출제된 문제로 Level 2에 해당한다. 11 by 11 Matrix로 구성된 좌표 평면에서 캐릭터가 이동하고, 캐릭터가 지나간 길 중 처음 걸어본 길의 길이를 구하는 문제다. 입력이 'ULURRDLLU'로 주어졌다면, 아래와 같이 그려볼 수 있고, 8과 9에 해당하는 이동은 처음 걸어본 길이 아니기 때문에 빼고 값은 7이 된다. 두 번째 예시의 경우, 벽에 붙은 경우에는 이를 무시한다. 해당 문제는 좌표 평면 + 집합으로 계산하면 쉽게 해결이 가능하다. 집합을 통해 시작 지점과 끝 지점을 양방향 그래프, 무향 그래프로 표현하고 전체 길이에서 2를 나누게 되면 처음 방문한 거리가 나온다. 만약에 문제에서 방향 까지 고려한다고 했으면, 코드..

해당 문제는 DFS로 해결이 가능하다. DFS 는 깊이 우선 탐색으로, 한번에 던전을 갈 수 있는 끝까지 탐색한 후 이전 단계로 돌아가는 작업을하면 된다. 이때, 방문 여부와 방문 횟수를 초기화하고 다시 탐색을 하면 끝이다. answer = 0 def solution(k, dungeons): global answer def DFS(k, cnt, dungeons, visited): global answer answer = max(answer, cnt) # 최대 방문 횟수 for i in range(len(dungeons)): if visited[i] == 0 and k >= dungeons[i][0]: visited[i] = 1 # 방문 DFS(k-dungeons[i][1], cnt+1, dungeons,..

해당 문제는 Level 2에 해당하는 문제로, "해시"로 분류된 문제다. 조합 공식을 이용해 아래와 같이 쉽게 풀이할 수 있다. from collections import defaultdict def solution(clothes): inform = defaultdict(list) answer = 1 for cl in clothes: k, v = cl inform[v] += [k] for k in inform.keys(): n = len(inform[k]) answer *= (n + 1) return answer - 1 모든 의상에 대해서 가지고 온 후, 모든 조합을 계산한다. 이때 모든 조합이란, 옷을 아무것도 입지 않는 경우도 포함하는 것이다. 그렇기 때문에 마지막에 -1을 해주어서 값을 도출하면 된다.

프로그래머스 월간 코드 챌린지 3에 출제된 Level 2 난이도의 문제다. 초기 풀이는 extend를 활용해서 아래와 같이 작성하였다. def solution(n, left, right): ans = [] for i in range(n): l = list(range(i+1, n+1)) ans.extend([l[0]]*(n-len(l)) + l) return ans[left:right+1] 일부 케이스에서는 통과가 되었으나, 시간 초과가 발생한다. list를 생성하고 extend하는 과정에서 오래 걸리는 것으로 확인된다. 시간 복잡도를 줄이기 위해 몫, 나머지 개념을 도입했다. (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2) 1 2 3 2 2..

해당 문제는 프로그래머스 기준 Level 1에 해당하는 문제로 쉽게 해결할 수 있는 문제다. 문제의 핵심을 간략하게 살펴보면, skip에 해당하는 단어는 넘어가고, 단어가 있는 곳에서 index 만큼 떨어진 알파벳으로 변환하면 끝이다. def solution(s, skip, index): answer = '' alphabet = 'abcdefghijklmnopqrstuvwxyz' for sk in skip: alphabet = alphabet.replace(sk, '') for a in s: idx = (alphabet.index(a) + index ) % len(alphabet) answer += alphabet[idx] return answer 먼저, skip에 해당하는 단어를 replace한다. 그..

해당 문제는 프로그래머스 기준 Level 1에 해당하는 문제다. 풀이는 2중 for문을 통해서 먼저 딕셔너리를 생성한다. 이때 자판 패드가 가장 가까운 번호를 기준으로 key와 value를 지정하면 된다. from collections import defaultdict def solution(keymap, targets): answer = [] inform = defaultdict(list) for key in keymap: for i, k in enumerate(key): if inform[k] == []: inform[k] = i+1 elif inform[k] != [] and (i+1) < inform[k]: inform[k] = i+1 for target in targets: values = 0 ..

해당 문제는 2021 KAKAO BLIND RECRUITMENT에서 출제된 문제다. 프로그래머스 기준 Level 2에 해당한다. 이번 문제는 combinations 함수와 Counter 함수를 사용하면 쉽게 해결이 가능하다. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for n in course: candidates = [] for menu in orders: for l in combinations(menu, n): candidates.append(''.join(sorted(l))) candidates = Counter(candidates).most_co..

해당 문제는 2022 KAKAO TECH INTERNSHIP에 출제된 문제다. 프로그래머스 기준 Level 2에 해당한다. Queue를 통해 푸는 문제로 collections 내 queue를 사용하면 된다. from collections import deque def solution(queue1, queue2): answer = 0 q1 = deque(queue1) q2 = deque(queue2) _max = (len(queue1)) * 3 t1 = sum(q1) t2 = sum(q2) total = t1 + t2 if total % 2 != 0: return -1 queue에서는 popleft라는 함수가 있어서, 왼쪽에 있는 값을 빼는 형태로 진행한다. 문제에서 조건 자체가 왼쪽에 있는 값을 차례대로..