python

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 출발지, 도착지가 적힌 ticket이 주어질 때, 모든 여행지를 방문하는 여행 경로를 반환한다. 💻Solution from collections import defaultdict def solution(tickets): answer = [] # ticket 도착지 내림차순 정렬 tickets = sorted(tickets, key=lambda x: x[1], reverse=True) # 티켓 그래프 생성 tickets_dict = defaultdict(list) f..

LIS(Longest Increase Sequence)란? LIS 알고리즘은, 주어진 수열에서 숫자를 제외시켜 최장 길이의 오름차순 수열을 만드는 알고리즘이다. LIS 구현 1. 이중 반복문을 통한 구현 (O(N^2)) 해당 구간까지의 '최장 증가 부분수열'의 크기를 저장하는 별도의 list를 생성하고 이를 업데이트한다. array의 모든 값에 대해, 해당 값 이전까지(0 ~ i-1) 자신보다 큰 값들의(array[j] > array[i]) 개수를 dp[i]에 저장한다. 모든 과정이 끝나면, dp의 가장 큰 값이 array에서 만들 수 있는 '최장 증가 부분수열'의 크기 이다. array = [3,4,1,2,6,4,3,1] dp = [1] * len(array) for i in range(1, len(a..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 한 글자를 의미하는 '?'를 포함하는 쿼리가 여러개 주어질 때, 각 쿼리가 words의 몇 단어와 매치되는지를 반환한다. 💻Solution 1. 이진탐색을 활용한 풀이 from bisect import bisect_left, bisect_right def solution(words, queries): answer = [] word_list = [[] for _ in range(100001)] word_list_reversed = [[] for _ in range(1..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking '균형잡힌 괄호 문자열' p가 주어질 때, '올바른 괄호 문자열'로 변환한 결과를 반환한다. '균형잡힌 괄호 문자열'은 '('와 ')'의 개수가 같은 문자열이다. '올바른 괄호 문자열'은 '균형잡힌 괄호 문자열'이면서 '('와 ')' 짝이 모두 맞는 문자열이다. 💻Solution def bracket_check(s): cnt = 0 for char in s: if cnt < 0: return False cnt += 1 if char == '(' else -1 if ..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking key와 lock이 주어질 때, key를 상하좌우, 회전하여 lock의 홈에 끼워넣을 수 있는지를 반환한다. 💻Solution def right_rotate_90_degree(key): new_key = [] for i in zip(*key): new_key.append(list(reversed(i))) return new_key def check(new_lock): n = len(new_lock) // 3 for i in range(n, n*2): for j in..

🔗 Problem Link 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net ❔Thinking NxN 크기의 공간이 주어질 때, (0,0)에서 출발해 (N-1, N-1)로 이동하는 최소 비용을 반환한다. 💻Solution import heapq INF = int(1e9) dx = [-1,1,0,0] dy = [0,0,-1,1] def dijkstra(x, y, graph): q = [] n = len(graph) heapq.heappush(q, (graph[x][y], x, y)) while ..