알고리즘 스터디
[프로그래머스] 탐욕법 3. 큰 수 만들기
문제 풀이 def solution(number, k): answer = '' result = [number[0]] idx = 1 while k > 0: if idx == (len(number)): result = result[:-k] break while result and number[idx] > result[-1] and k > 0: k -= 1 result.pop() result.append(number[idx]) idx += 1 if k == 0: for i in range(idx, len(number)): result.append(number[i]) return "".join(result) 앞자리 수가 커야 가장 큰 수가 만들어지기 때문에 수를 하나씩 추가하며 이전 수보다 큰 수가 들어오면 이전..
[프로그래머스] 탐욕법 2. 조이스틱
풀이 def solution(name): answer = len(name) - 1 for i in range(0, len(name)): nameASCII = ord(name[i]) if nameASCII > 78: answer += (90 - nameASCII + 1) else: answer += (13 - 78 + nameASCII) lenOfFrontA = 0 for i in range(1, len(name)): if name[i] == 'A': lenOfFrontA += 1 if name[i] != 'A': break lenOfBackA = 0 for i in range(len(name) - 1, -1, -1): if name[i] == 'A': lenOfBackA += 1 if name[i] !=..
[프로그래머스] 이분탐색 1. 입국심사
문제 풀이 일단 이분탐색이나 시간은 생각하지 않고 막 짜보기로 했다. 입국심사대에 다음 사람을 받아 걸리는 시간을 계산하여 가장 적은 쪽으로 이동하게 한다. def solution(n, times): curTime = [0 for i in range(n)] while(n > 0): curMin = curTime[0] + times[0] curIndex = 0 for i in range(1, len(times)): if curMin > curTime[i] + times[i]: curMin = curTime[i] + times[i] curIndex = i curTime[curIndex] += times[curIndex] n -= 1 return max(curTime) 4번 케이스부터 시간초과로 실패했다. d..
[프로그래머스] 깊이/너비우선탐색 1. 타겟 넘버
문제 깊이우선탐색(DFS)/ 너비우선탐색(BFS) DFS - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 어떤 노드를 방문했었는지 반드시 검사해야함 - 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함 * 인접 리스트로 표현된 그래프 : O(N+E) * 인접 행렬로 표현된 그래프 : O(N^2) BFS - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 - 어떤 노드를 방문했었는지 반드시 검사해야함 - 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함, 선입선출 - DFS와 동일한 시간복잡도이나 평균적으로 DFS보다 조금 빠르다고 함 출..
[프로그래머스] 힙 1. 더 맵게
문제 풀이 힙의 개념이 가물가물해서 먼저 힙이 무엇이었는지 찾아보았다. 힙은 완전이진트리의 일종으로 최댓값, 최솟값을 추출하기 쉬운 자료구조였다. 그냥 리스트로 처리하고 매번 정렬하는 방법도 생각해보았으나 일단 힙 먼저 사용해보기로 했다. 파이썬 모듈이 존재할 것 같아 찾아보고 적용하였다. import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while(scoville[0] < K): first = heapq.heappop(scoville) second = heapq.heappop(scoville) heapq.heappush(scoville, first + second * 2) answer += 1 return answer ..
[프로그래머스] 스택/큐 2. 주식가격
문제 풀이 이중포문을 활용해서 풀 수 있을테지만 효율성 테스트에서 걸릴 것 같았다. 스택을 사용해서 풀어보려고 했는데 문법도 잘 모르고 로직도 확실하지 않은데 풀다가 짜증날 것 같았다. 그래서 돌아가는 길이 가장 빠른 길이라고 먼저 이중포문으로 대강 풀어보았다. 그런데 웬일,, 효율성 테스트까지 그냥 통과해버림 def solution(prices): answer = [] for i in range(0, len(prices)): flag = False for j in range(i + 1, len(prices)): if prices[i] > prices[j]: answer.append(j - i) flag = True break; if flag == False: answer.append(len(prices..
[프로그래머스] 해시 2. 전화번호 목록
문제 풀이 처음 보자마자 생각난 방법은 이중포문으로 순회하며 비교하는 것이다. 효율성 테스트 통과 못할거라고 생각했지만 일단 해봄. def solution(phone_book): answer = True for i_idx, i in enumerate(phone_book): for j_idx in range(i_idx + 1, len(phone_book)): if i in phone_book[j_idx]: answer = False break return answer 역시나 통과 못함. 거기다가 정확성도 틀렸다. in이 하위 문자열을 포함하는 것을 찾는다 해서 사용했는데, 아마 접두어뿐만 아니라 내부에 있는 문자열까지도 찾아서 그런 것 같다. 다시 시도 def solution(phone_book): ans..
[프로그래머스] 정렬 2. 가장 큰 수
문제 풀이 레벨 2라고 벌써 어렵다.; 처음에 생각했던 방법은 다음과 같다. 만약 [3, 31, 375, 37, 370, 8]의 numbers가 주어진다면 다음과 같이 각 자릿수를 분리하여 이중배열을 만든다. 3 3 3 3 3 8 1 7 7 7 5 0 그 후 1. 첫 번째 자릿수의 숫자를 비교하여 정렬 2. 만약 같은 숫자일 경우, 두 번째 자리 수 중 큰 순서로 정렬 3. 만약 같은 숫자이며 두 번째 자리 수가 없는 경우, 첫 번째와 같은 숫자로 취급하여 비교 후 정렬 ex) 3 -> 33 4. 세 번째 자리 수도 같은 방법으로 비교 후 정렬 위의 방법으로 풀면, 내가 생각한 예외는 대강 잡힐 것 같았다. (이마저도 틀릴수도) 다만 문제는 그 다음이었다. 각 과정이 너무 복잡했고, 시간과 공간 활용도 ..