파이문

더 맵게 programmers.co.kr/learn/courses/30/lessons/42626 숫자 목록이 주어지고 거기서 가장 낮은 숫자와, 그 다음 숫자 * 2를 더한 값을 다시 목록에 넣을 수 있는 횟수를 리턴하는 문제이다. 목록을 값에 추가하고, 나올 때 무조건 작은 값이 먼저 나와야 된다는 조건이 있기 때문에 min-heap 을 생각하면 그 다음엔 알맞은 자료구조를 선택하여 구현하면 된다. 파이썬에선 heap, 자바에선 PriorityQueue 를 사용할 수 있다. (만약 큰 수대로 나와야 한다면 값을 추가할 때 -1 을 곱해서 사용하면 된다.) heap 사용하여 풀이 (Python) from heapq import heappush, heappop def solution(scoville, K)..

가장 큰 수 programmers.co.kr/learn/courses/30/lessons/42746 number 배열이 주어졌을 때 원소 조합으로 가장 큰 숫자를 만들어 리턴하는 문제다. 비슷한 문제 / 풀이가 Geeks for Geeks 에 있다. 2가지 풀이 방법이 있는데 첫 번째는 숫자를 문자열로 바꾸는 custom compare 함수를 구현하여 언어에서 제공하는 정렬 함수를 사용하는 것이다. 두 번째는 가장 큰 숫자의 자릿 수 만큼 모든 숫자를 만든 다음에, 새롭게 만든 그 숫자들로 정렬하는 것이다. Custom compare 함수 만들어 풀이 www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-bigges..

주식가격 programmers.co.kr/learn/courses/30/lessons/42584 알고리즘 문제 풀이에 자주 보이는, next greater element 랑 비슷한 문제다. 주어진 배열에서 각 인덱스가 i < j 일때 A[i] 와 A[j] 간을 비교하여 j - i 만큼을 정답에 추가하는 문제다. 빠르게 하려고 파이썬으로 풀어보았다. (파이썬에서 list 는 스택과 동일하므로 list 를 사용하였다.) def solution(prices): # 정답의 전체 길이는 prices 와 동일하다. 그래서 prices 길이만큼 0 으로 초기화 시켜주었다. answer = [0 for _ in range(len(prices))] stack = list() # 0 번쨰 값은 미리 스택에 넣어두었다. s..

다리를 지나는 트럭 programmers.co.kr/learn/courses/30/lessons/42583?language=java 대기하는 트럭 리스트(값은 트럭의 무게)가 주어지고, 리스트에 있는 트럭이 다리를 모두 지나는 시간을 리턴하는 문제이다. 단, 다리를 지날 때 다리 위에 있는 트럭들의 무게 합산이 다리가 버틸 수 있는 무게(weight) 보다 적어야 하고 하나의 트럭이 다리를 지나는 시간은 bridge_length 와 같다. 큐와 스택 카테고리에 있어서, 큐로 풀었다. (구현체는 deque 쓰긴 함) import java.util.ArrayDeque; import java.util.Queue; class Solution { public int solution(int bridge_length..

전화 번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 HashMap 으로 풀이 모든 전화번호를 HashMap 에 넣고 2중으로 다시 순회해서 확인하는 식으로 했다. 조건에 phone_book의 길이는 1 이상 1,000,000 이하입니다. 라고 적혀 있어서 효율성 테스트에서 실패할 줄 알았는데, 생각보다 최대 사이즈가 크지 않은 모양이었다. (그래도 혹시 몰라서 주어진 phone_book 을 정렬했다.) 자기 자신 (같은 인덱스 참고) 을 보고 잘못 판단할 수 있기 때문에 HashSet 이 아닌 HashMap 으로 value 값엔 인덱스를 넣어 구현하였다. import java.util.*; class Solution { public boolean sol..

단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 DFS 풀이 begin 과 한 글자 차이가 나는 단어를 찾고 그 단어에서 부터 모든 words 와 (역시 한 글자 차이가 나는 ) 비교해 가며 구현한다. 이 때 정답은 가장 적은 변화로 target 을 찾는 경우의 수를 구하는 문제다. 우선 처음 for 문으로 모든 words 에 대해 비교한다. 즉 begin -> 1번 단어 -> .... -> 종료 와 begin -> 2번 단어 -> ... -> 종료 와 같이 begin 바로 다음에 비교할 단어를 words 의 모든 단어를 대상으로 하는 것이다. 이 구현대로 하면 1 번 단어 -> 2번 단어와 2번 단어 -> 1번 단어와 중복되는 계산이 있을..

네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 DFS 풀이 문제 설명이 길지만, 축약하자면 undirected graph 에서 연결 되지 않은 그룹이 몇개 있는지에 대한 문제다. DFS 로 그래프를 따라 가되, 이미 방문 했던 노드면 패스하고 방문하지 않았던 노드면 다시 계속 따라가게 구현하면 된다. 노드의 방문에 대한 여부는 미방문(0), 누군가가 방문 하고 있는 중 (1), 방문 완료(2) 로 확인할 수 있지만... 문제에선 사실 여기까진 필요없고 단순히 boolean 으로 확인하면 된다. (만약 directed graph 라면 이 알고리즘을 써야 한다. 참고) class Solution { public int dfs(int i, int..

타겟 넘버 숫자 배열이 주어지고, 각각을 더하거나 빼서 target 을 만들 수 있는 모든 경우의 수를 구하는 문제였다. 자바로 풀었다. https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 풀이 재귀로 모든 경우의 수(더하고, 빼고) 로 다 넣어서 구한다. 만들어진 최종 값이 target 과 동일할 경우 1을 리턴하고 이 값을 누적한 것이 결과 값이다. class Solution { public int dfs(int prev, int index, int[] numbers, int target) { if (index >= numbers.length) { if (target == prev) { return 1; } return 0; } int cur1..