파고파고

✨해결포인트 1. '최단거리'를 구해야 하는 것이기 때문에 DFS보다 BFS가 유리한 문제였다. 2. 처음 시도에서 DFS(재귀함수)를 활용해 - 방문가능한 노드인 경우 방문한 노드를 0으로 바꿔주고 - 동서남북 방향으로 순차적으로/재귀적으로 길을 탐색하며 count를 늘려주며 - 더이상 방문할 수 없을 때 return 하도록 코드를 짰다. 결과, 테스트케이스는 통과하나 효율성테스트를 통과하지 못했다. 3. 논리는 같으나, queue를 활용하는 것으로(재귀함수x) 코드를 수정했다. - 시작지점을 enqueue해주고 - queue 가장 앞의 지점을 방문하며 dequeue - 방문지점을 기준으로 거리가 1인(동/서/남/북) 지점들 중 방문할 수 있는 지점들을 enqueue - queue가 빌때까지 반복 결과..

✨해결포인트 1. 일단 재귀로 짜는 아이디어를 내는 것이 어려웠고, 둘째는 자료의 primitive형과 reference형의 차이를 잘 모르고 있어 예상치 못한 에러를 만난 것에 당황했던 문제. 2. 각 리스트 요소의 부호의 경우의 수를 재귀로 탐색하고, 가장 마지막 depth에서 정답과 부합하는지 확인 후 return 하는 함수를 만들었다. 리스트 안에 두 개의 수가 들어있다면, 다음과 같은 DFS Tree가 만들어질 것이다. (탐색 순서는 노란 선을 따라 갈 것.) 3. 원래 answer = 0 으로 정수형 자료형으로 초기화해주었는데, 돌리니까 'local variable referenced before assignment' 에러가 났다. 이유를 살펴보니, 여기서 answer는 primitive 형으..

해결포인트✨ 1. 가장 무거운 사람이 보트를 탔다고 가정하고, 가장 가벼운 사람이 함께 탈 수 있는지 여부를 먼저 확인해 연산량을 줄이는 것이 핵심이었다. 2. 처음에 queue로 풀었는데, 가장 가볍지 않은 사람이 보트를 탈 수 있는 경우의 연산이 많아져 효율성테스트를 통과하지 못했었다. 3. pop 연산을 사용해 리스트를 변형하는 대신에, 리스트를 정렬한 후 인덱스가 '가장 가벼운 사람'과 '가장 무거운 사람'을 가리키도록 지정해 인덱스만 변경하면 되도록 코드를 바꿨더니 테스트를 통과했다. 시도 1 코드✨ 정답은 맞았으나 효율성테스트를 통과하지 못한 초기 코드다. def solution(people, limit): count=0 people.sort() while len(people)>0: first..

해결포인트✨ 1. 주어진 progress와 speeds를 queue로 두고, 이중 while문을 돌며 조건에 따라 queue 안의 요소를 없애주었다. 2. queue뒤의 기능이 개발 완료되더라도 앞의 기능이 완료되지 않으면 배포가 되지 않는 특징을 queue로 연결하는 것이 핵심인 문제. 코드✨ def solution(progress, speeds): answer=[] while len(progress)>0: progress = [progress[i]+speeds[i] for i in range(len(progress))] count = 0 while len(progress)>0 and progress[0]>=100: progress.pop(0) speeds.pop(0) count+=1 if count!..

해결포인트✨ 1. while 문을 돌며 큐 제일 앞의 요소를 꺼낸 후, 프린트 할 건지 말 건지 결정하고 프린트하거나 제일 뒤로 보냈다. 2. 프린트 여부를 결정할 때, 또 for문을 돌면서 확인하면 시간복잡도가 커지기 때문에 set을 활용해 tmp보다 priority가 높은 요소가 존재하는지 확인했다. 코드✨ def solution(priorities, location): printer = [i for i in range(len(priorities))] answer = 0 while (location in printer)==True: tmp = priorities.pop(0) if len(set(priorities)-set(range(tmp+1)))==0: # print("중요도 더 높은 요소 없음. ..

해결포인트✨ 1. 대기 중인 트럭, 다리를 건너고 있는 트럭 모두 선입선출 방식으로 다리를 건너기 때문에 queue를 활용하는 것이 이상적인 문제다. 2. 코드의 구성은 (1) 출발한 트럭이 다리를 완전히 건넜음을 확인하는 파트와 (2) 대기중인 트럭이 출발하게 하는 파트로 나눴다. 코드에 존재하는 queue는 총 3가지인데, '대기중인 트럭의 리스트 (truck_weights)', '다리를 건너고 있는 트럭의 리스트(ing)', '다리를 완전히 건너지 않은 트럭들의 출발시각 리스트(departing_time)' 이렇게 3가지를 생성해주었다. 3. 모든 트럭이 다리를 다 건너 done 리스트 안에 넣어질때까지, while 문 안에서 현재 흘러간 시간(time)을 1씩 늘려주었다. 4. (1)에서는 현재 ..

해결포인트✨ 1. 왜 스택 문제인지 몰라서 시간복잡도 때문에 고생했던 문제다. 2. 주식의 순서(인덱스)와 가격 리스트가 들어갈 스택에 순서대로 주식을 넣어주면서, 가격이 떨어졌을 경우에만 반복문을 돌며 스택을 pop하고, 최근 주식과 스택 안의 마지막 주식의 인덱스 차이(스택의 마지막 주식가격이 떨어지지 않은 기간)를 rising_count에 업데이트해주었다. (이 부분이 가장 어려웠다. 처음에는 rising_count 요소를 한 번에 업데이트 하지 않고, 주식이 오르거나 유지될때마다 count를 1 늘리고 / 떨어졌을때, count를 늘리는 것을 중단하도록 코드를 짰다. 모든 경우에 계산이 들어가, 주식 수가 많은 경우 시간이 매우 오래 걸렸다... 스택을 활용해 주식이 오르거나 가격이 유지될 경우의..

해결포인트✨ 1. stack을 만들어 순차적으로 괄호를 넣고, 짝이 맞춰질 때마다 괄호 짝을 pop해주는 것을 반복했다. 2. 비슷한 유형의 문제에서 stack을 활용하려는 아이디어를 떠올리는 것이 필요할 듯 하다. 코드✨ def solution(s): answer = True stack=[] for i in s: stack.append(i) if stack[-2:]==["(",")"]: stack.pop() stack.pop() if len(stack)!=0: answer = False return answer

해결포인트✨ 1. MinHeap의 기능들을 활용해, 반복문 안에서 스코빌지수가 작은 요소들을 빼내고 새로 계산해 heap에 넣는 것을 반복했다. 2. while문을 빠져나오는 조건 / 빠져나온 후에도 스코빌 지수가 k를 넘지 않았을 때의 처리에 유의했다. 코드✨ import heapq def solution(scoville,K): maximum_count = len(scoville) heapq.heapify(scoville) count = 0 while len(scoville)>=2 and scoville[0]

해결포인트✨ 1. 모든 경우를 구하는 것이 불가피하기 때문에, itertools.permutation을 사용해서 모든 순열을 구하고, 이후에 해당 수가 소수인지 일반적인 대수론을 활용해 확인해주었다. 2. 소수인지 확인하는 과정에서 반복문을 최대한 적게 돌도록, 반복범위를 해당 수의 절반으로 한정해주었다. (소수 관련 문제에서 시간복잡도를 줄이기 위해 반드시 필요한 단계.) 3. 단순 완전탐색 +소수확인 문제. 코드✨ import itertools def solution(numbers): lst = [] answer = [] cards = list(numbers) tmp = [] for i in range(1,len(cards)+1): tmp+=list(itertools.permutations(cards..