네발로 코딩하는 포메라니안

1. 문제 2. 풀이 과정 개인적으로 테스트 케이스들을 생각해보는 게 알고리즘을 떠올리기가 좋았다. [CASE1] 두 수 비교부터 생각해보면, [35, 3443]이 있다고 가정하자. 참고로, 숫자와 달리 문자열은 아스키코드에 따라 인덱스 0번째부터 비교해간다. 오름차순으로 정렬하면 [3443, 35]가 되며 큰 수부터 나열하면 정답인 "353443"을 반환한다. [CASE2] 그러면 [34, 3421]인 경우를 생각해보자. 이미 정렬된 상태로 정답인 "343421"과 다른 "342134"를 반환한다. 여기 문제는 34의 자릿수가 적어서 발생한다. 문자열 정렬과 위 문제는 이 부분에서 차이가 난다. 결론 CASE1)처럼 자릿수가 끝나기 전에 그 자릿수까지의 숫자가 달라서 정렬이 되면 상관없지만, 그 자릿수..

1. 문제 2. 풀이과정 방법 1) heapq 내장 모듈 활용 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0] < K: if len(scoville) == 1: return -1 answer += 1 #가장 안매운거, 두 번째 안매운거 heap에서 빼서 연산 a = heapq.heappop(scoville) + heapq.heappop(scoville)*2 #섞은거 넣기 heapq.heappush(scoville, a) return answer 방법 2) heapq대신 deque만 이용하였다. 섞은 결과는 새로운 배열 mix에 따로 저장하여 scoville와 mix의 맨 앞 원소만 비교하..

1. 문제 2. 풀이 과정 방법 1) 직관적으로 생각나는 방법, 자신보다 뒤에 있는 값을 하나씩 확인해서 계산한다. 시간복잡도 O(%{n}^2%) def solution(prices): answer = [] for i in range(len(prices)): for j in range(i+1, len(prices)): if prices[i] > prices[j]: answer.append(j-i) break if len(answer)-1 < i: answer.append(len(prices)-1-i) return answer 방법 2) stack을 이용해서 더 빨리 계산한다. 코드 실행 과정 예시 입력 : [1, 2, 3, 2, 1] stack [(1, 0)] [(1, 0), (2, 1)] [(1, 0)..

1. 문제 2. 풀이과정 방법 1) 큐에 [트럭 무게, 위치]를 넣고, 반복문 한 번 돌 때마다 위치를 1 감소시켜서 위치 값이 1이 되면 트럭이 다리에서 나간다. 변수 c는 다음에 기다리는 트럭의 truck_weights에서의 인덱스 값을 나타낸다. from collections import deque def solution(bridge_length, weight, truck_weights): answer = 1 Q = deque() #다리 Q.append([truck_weights[0], bridge_length]) sum = truck_weights[0] c = 1 while Q: answer += 1 if Q[0][1] == 1:#다리 출발(bridge_length)에서 끝(1)까지 도착하면 po..

1. collections 라이브러리 함수 1) Counter - 리스트에서 각 요소별 개수를 사전형으로 반환 - 뺄셈 연산 가능 from collections import Counter counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue']) print(counter['blue'])#'blue'가 등장한 횟수 출력 print(dict(counter)) #3 #{'red': 2, 'blue': 3, 'green': 1} 뺄셈 연산을 활용하는 방법은 아래 발행 글의 방법 2)를 참고 [Python] 완주하지 못한 선수 1. 문제 2. 풀이 과정 방법 1) 아스키코드를 기준으로 정렬한 후, 앞에서부터 순차 탐색한다. def solution(par..

1. 문제 2. 풀이 과정 방법 1) 큐에서 하나 꺼낼 때마다 location을 1 감소시켜서 현재 위치를 업데이트한다. from collections import deque def solution(priorities, location): Q = deque() for i in priorities: Q.append(i) count = 0 while Q: a = Q.popleft() if Q and a < max(Q): Q.append(a) else: count += 1 if location == 0: return count location -= 1 if location < 0 : location = len(Q)-1 return count 방법 2) 큐에 처음 인덱스 정보와 데이터를 함께 저장하고, any를..

1. 문제 2. 풀이 과정 방법 1) 남은 날짜 계산할 때, 나머지가 있으면 올리도록 한다. 최대 날짜가 갱신되면 바로 출력한다. def solution(progresses, speeds): answer = [] max_day = 0 pre_idx = 0 for i in range(len(progresses)): temp = 100 - progresses[i] day = temp//speeds[i] if temp % speeds[i] != 0: day += 1 if max_day < day: #최대 걸리는 날보다 크면 그 앞의 기능들 먼저 배포 max_day = day if i != 0: answer.append(i-pre_idx) pre_idx = i if i==len(progresses)-1: #마지..

1. 문제 2. 풀이 과정 방법 1) hash 자료구조를 이용해서 옷 종류별로 몇 개씩 있는지 count한 후, 특정 종류는 선택 안 할 경우도 있으니 각 종류별로 안 입을 경우를 1씩 더해서 조합의 개수를 count한다. 여기서 모두 선택 안 할 경우 1가지를 빼주면 결과값이 된다. def solution(clothes): answer = 1 hash_map = {} #종류별로 개수 count for i in clothes: if i[1] in hash_map: hash_map[i[1]] += 1 else: hash_map[i[1]] = 1 #결과 계산 arr = list(hash_map.values()) for i in arr: answer *= (i+1) return answer-1 방법 2) 논리..

1. 문제 2. 풀이 과정 방법 1) 정렬해서 인접한 요소만 비교하기 *str.starts.with("접두어") : 특정 문자열로 시작하는지 확인하는 함수 def solution(phone_book): phone_book.sort() for i in range(len(phone_book)-1): if phone_book[i+1].startswith(phone_book[i]): return False return True 방법 2) 해쉬 맵 사용하기 리스트에서 특정 요소가 있는지 확인하는 것보다 set, dict에서 확인하는 것이 더 빠르다. number in phone_book으로 해도 답은 나오지만, number in hash_map을 사용하는 이유이다. def solution(phone_book): ..

1. 문제 2. 풀이 과정 방법 1) sorted 함수를 써서 정렬된 결과를 반환받음 def solution(array, commands): answer = [] for command in commands: i, j, k = command temp = sorted(array[i-1:j]) answer.append(temp[k-1]) return answer 방법 2) 방법1과 같은 원리이며 사용한 함수만 다르다. 아래는 map, lambda 함수를 이용하여 더 짧게 표현하였다. def solution(array, commands): answer = [*(map(lambda x : sorted(array[x[0]-1:x[1]])[x[2]-1], commands))] return answer