알고리즘 (52) 썸네일형 리스트형 [알고리즘] 프로그래머스 - 뒤에 있는 큰 수 찾기(Python) 문제 설명알고리즘 고민자기 자신보다 뒤에 있는 수 중에서 가장 가까운 수로 치환하는 문제이다. 처음에는 인덱싱을 이용해서 확인하는 인덱스와 그 뒤에있는 배열을 잘라 비교하면서 해결하려 했지만 이 방법은 이중 for문을 사용하는 꼴이 되어 시간 초과 문제가 발생하였다. 따라서 스택을 사용해서 큰 수를 저장하고 확인하는 값이 스택의 마지막 값보다 크면 큰 수를 현재 숫자로 업데이트하고 이전 수를 pop으로 제거하는 방법을 통해 해결하였다.코드def solution(numbers): stack = [] answer = [-1] * len(numbers) for i in range(len(numbers)): while stack and numbers[stack[-1]] [알고리즘] 프로그래머스 - 롤케이크 자르기(Python) 문제 설명알고리즘 고민처음에는 set을 이용해서 철수와 동생이 먹을 부분의 토핑 종류를 구하는 과정을 반복하여 길이를 비교하려고 했다. 하지만 시간 초과가 발생하였다. 그래서 여러 고민을 해봤는데 결국 해결하지 못했다. 다른 풀이를 보니 Counter를 이용해서 딕셔너리의 개수를 세기도 하고 담겨있는 값을 제거하는 과정을 깔끔하게 해결하였다.코드from collections import Counterdef solution(topping): dic = Counter(topping) set_dic = set() res = 0 for i in topping: dic[i] -= 1 set_dic.add(i) if dic[i] == 0: .. 프로그래머스 - 더 맵게(Python) 문제 설명알고리즘 고민가장 작은 두 값을 섞어 새로운 스코빌 지수를 가진 음식으로 만드는 것을 반복하는 문제이다. 작은 값 두 개를 찾는 것을 MIN으로 찾기에는 시간이 부족할 듯하여 heap을 사용하여 해결하였다. 18번 케이스에서 막혔는데 만약 처음부터 가장 작은 스코빌 지수의 음식이 K보다 높은 지수라면 굳이 while문을 돌릴 필요 없이 해결할 수 있다. 코드 import heapqdef solution(scoville, K): cnt = 0 heapq.heapify(scoville) if scoville[0] >=K : return 0 while len(scoville)>1: min_first = heapq.heappop(scoville) .. 프로그래머스 - 방문 길이(Python) 문제 설명알고리즘 고민좌표계에서 원하는 위치까지 이동한 후 새로운 곳을 이동한 횟수를 세는 문제이다. 일단 방향에 대한 정보를 딕셔너리 형태로 만들어 사용하고자 하였다. 그 후에 처음에는 robust하게 다음 위치와 현재 위치의 입력이 있는지 확인하고자 하였는데 이렇게 해서는 코드가 너무 복잡해진다고 생각이 들었다. 그래서 만약 중복된 길인 경우는 반대 방향에서 오는 것과 해당 방향으로 이동하는 두 가지 경우가 있는데 이 경우를 만약에 set에 없다면 두가지를 모두 추가하여 중복을 제거하고자 하였다. 마지막에 출력할 때는 set의 길이를 절반으로 만들어 주면 쉽게 해결할 수 있다.코드def solution(dirs): answer = 0 direction = {'U' : (1,0), 'R' :.. 프로그래머스 - 튜플(Python) 문제 설명알고리즘 고민입력으로 주어진 s가 모두 문자열이므로 양 끝을 제거하고 " },{ "를 기준으로 split하여 배열 형태로 만든다. 이후에는 각 각 배열 요소 안에 여러 요소가 쉼표로 구분되기에 쉼표로 나눈 값을 다시 배열로 넣고 Counter 모듈을 이용하여 개수 순서대로 정렬하고 순서대로 answer에 추가하여 해결하였다.코드from collections import Counterdef solution(s): s = s[2:-2] elements = s.split("},{") temp = [] for element in elements: temp.extend(element.split(",")) counter = Counter(temp) .. 프로그래머스 - [1차]캐시(Python) 문제 설명알고리즘 고민LRU(Least Recently Used) 알고리즘을 구현하는 문제이다. 먼저, 캐시 크기가 0인 경우는 cities 개수에 5를 곱한 값을 반환하도록 하여 처리한다. 대문자와 소문자를 구별하지 않는 조건에 맞도록 upper 함수를 적용하여 처리한다. 만약 캐시 안에 출력할 도시가 있으면 해당 도시를 출력하고 가장 앞으로 옮긴다. 없다면 만약 캐시가 꽉 채워져 있는지 확인하고 꽉 채워져있으면 마지막 요소를 pop하고 아니라면 굳이 pop할 필요가 없으므로 그냥 추가만 하도록 한다.코드def solution(cacheSize, cities): answer = 0 cache = [] if cacheSize == 0: return len(cities) * 5.. 프로그래머스 - 의상(Python) 문제 설명알고리즘 고민처음에는 각각을 딕셔너리로 만든 후에 조합을 이용해서 구해야 겠다고 생각했다. 그러나 아무리 해도 모든 경우를 조합으로 구한다는 것이 시간이 너무 오래 걸릴 것 같고 접근 자체가 robust하다고 생각해서 다른 방법을 생각해보았다. 결국 조합의 모든 경우의 수에서 아무 것도 입지 않는 경우를 제외한다면 모든 경우의 수 이므로 각 옷의 종류 별 개수를 구하고 하나 더한 값을 모두 곱한 후 하나를 빼서 해결하였다.코드def solution(clothes): closets = {} for i in clothes: if i[1] not in closets: closets[i[1]] = 1 else: closets[i.. 프로그래머스 - 영어 끝말잇기(Python) 문제 설명알고리즘 고민어릴 때 자주하던 영어 끝말잇기 놀이와 똑같다. 앞사람이 말한 마지막 단어로 시작하지 않으면 탈락, 나왔던 단어를 다시 말하면 탈락. 만약 주어진 words에 탈락하는 경우가 없다면 [0,0]을 반환하도록 한다. 쉽게 해결하였다.코드def solution(n, words): answer = [0,0] stack = [words[0]] for i in range(1,len(words)): if words[i] in stack or stack[-1][-1] != words[i][0]: answer[0] = (i)%n + 1 answer[1] = i//n + 1 break stack.app.. 이전 1 2 3 4 ··· 7 다음
