알고리즘 문제풀이/프로그래머스
-
프로그래머스 라면 공장 자바(java) 풀이 Level 2 힙 라면 공장 문제 정리 공장에서 하루에 밀가루 1톤씩 사용한다. 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다. 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다. 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다. 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라 stock: 현재 남아있는 밀가루 양 dates[]: 밀가루 공급 일정 supplies[]: 해당 시점에 공급 가능한 수량 K: 원래 공장으로부터 공급받을 수 있는 시점 stock에 있는 밀가루는 오늘(0일)부터 사용된다. k일 째에는..
[우선순위 큐, comparable] 프로그래머스 level2 라면공장 자바 풀이프로그래머스 라면 공장 자바(java) 풀이 Level 2 힙 라면 공장 문제 정리 공장에서 하루에 밀가루 1톤씩 사용한다. 앞으로 K일 후에야 밀가루를 공급 받을 수 있어서 해외 공장에서 밀가루를 수입해야 한다. 해외 공장에서는 밀가루를 공급할 수 있는 날짜와 수량을 알려주었다. 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받으려고 한다. 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지 구해라 stock: 현재 남아있는 밀가루 양 dates[]: 밀가루 공급 일정 supplies[]: 해당 시점에 공급 가능한 수량 K: 원래 공장으로부터 공급받을 수 있는 시점 stock에 있는 밀가루는 오늘(0일)부터 사용된다. k일 째에는..
2020.05.15 -
프로그래머스 더 맵게 자바(java) 풀이 Level 2 힙 H-Index 문제 정리 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라. 힙, 우선순위 큐 이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(..
[우선순위 큐] 프로그래머스 level2 더 맵게 자바 풀이프로그래머스 더 맵게 자바(java) 풀이 Level 2 힙 H-Index 문제 정리 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라. 힙, 우선순위 큐 이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(..
2020.05.12 -
프로그래머스 단어 변환 자바(java) 풀이 Level 3 BFS/DFS 단어 변환 문제 정리 두 개의 단어 begin, target과 단어의 집합이 있다. 다음 규칙을 이용하여 begin에서 target으로 단어를 변환하는 가장 짧은 변환을 찾으려 한다. 규칙1: 한 번에 한 개의 알파벳만 바꿀 수 있다. 규칙2: words에 있는 단어로만 변환할 수 있다. 최소 몇 단계의 과정을 거쳐 target으로 바꿀 수 있는지 찾아라. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있습니다. 변환할 수 없는 경우에는 0을 return 합니다. 문제 풀이 이 문제는 bfs의 개념을 이용하면 생각보다 간단히 풀 수 있습니다. 하지만 그것까지 떠..
[BFS] 프로그래머스 level3 단어 변환 자바 풀이(아주 상세한 설명 포함)프로그래머스 단어 변환 자바(java) 풀이 Level 3 BFS/DFS 단어 변환 문제 정리 두 개의 단어 begin, target과 단어의 집합이 있다. 다음 규칙을 이용하여 begin에서 target으로 단어를 변환하는 가장 짧은 변환을 찾으려 한다. 규칙1: 한 번에 한 개의 알파벳만 바꿀 수 있다. 규칙2: words에 있는 단어로만 변환할 수 있다. 최소 몇 단계의 과정을 거쳐 target으로 바꿀 수 있는지 찾아라. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있습니다. 변환할 수 없는 경우에는 0을 return 합니다. 문제 풀이 이 문제는 bfs의 개념을 이용하면 생각보다 간단히 풀 수 있습니다. 하지만 그것까지 떠..
2020.05.11 -
프로그래머스 네트워크 자바(java) 풀이 Level 3 BFS/DFS 네트워크 문제 정리 컴퓨터A와 컴퓨터 B가 연결되있고, 컴퓨터 B와 컴퓨터 C가 연결되있으면 A와 C도 간접적으로 연결되 정보를 주고 받을 수 있다. 따라서 A,B,C는 같은 네트워크 상에 있다고 볼 수 있다. 각 컴퓨터는 0부터 n-1인 정수로 표현된다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]=1 이다. computers[i][i]는 항상 1이다. 문제 풀이 이 문제는 그래프로 바꿔서 생각하면 쉬운 문제입니다. level2에 놔도 될것 같네요 그래프 형태로 생각해서 bfs나 dfs를 이용해 탐색합니다. 저는 bfs를 이용했습니다. 방문하지 않은 경우 bfs를 이용해 탐색합니다. bfs로 이어져 있는..
[BFS] 프로그래머스 level3 네트워크 자바 풀이 (자세한 설명)프로그래머스 네트워크 자바(java) 풀이 Level 3 BFS/DFS 네트워크 문제 정리 컴퓨터A와 컴퓨터 B가 연결되있고, 컴퓨터 B와 컴퓨터 C가 연결되있으면 A와 C도 간접적으로 연결되 정보를 주고 받을 수 있다. 따라서 A,B,C는 같은 네트워크 상에 있다고 볼 수 있다. 각 컴퓨터는 0부터 n-1인 정수로 표현된다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]=1 이다. computers[i][i]는 항상 1이다. 문제 풀이 이 문제는 그래프로 바꿔서 생각하면 쉬운 문제입니다. level2에 놔도 될것 같네요 그래프 형태로 생각해서 bfs나 dfs를 이용해 탐색합니다. 저는 bfs를 이용했습니다. 방문하지 않은 경우 bfs를 이용해 탐색합니다. bfs로 이어져 있는..
2020.05.10 -
프로그래머스 베스트앨범 자바(java) 풀이 Level 3 해시(Hash) 베스트앨범 문제 풀이 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두개씩 모아 베스트 앨범을 출시하려고 한다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다. 장르 종류는 100개 미만이다. 장르에 속한 곡이 하나라면, 하나의 곡만 선택한다. 모든 장르는 재생된 횟수가 다르다. => 같은 재생횟수를 가지지 않는다 문제 풀이 HashMap 자료구조를 이용하여 문제를 풀 수 있습니다. 이 자료구조는 순서가 없으며 key, value로 저장합니다. 중복도 없습니다 key값으로 장르이름을 이..
[HashMap] 프로그래머스 level3 베스트앨범 자바 풀이프로그래머스 베스트앨범 자바(java) 풀이 Level 3 해시(Hash) 베스트앨범 문제 풀이 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두개씩 모아 베스트 앨범을 출시하려고 한다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다. 장르 종류는 100개 미만이다. 장르에 속한 곡이 하나라면, 하나의 곡만 선택한다. 모든 장르는 재생된 횟수가 다르다. => 같은 재생횟수를 가지지 않는다 문제 풀이 HashMap 자료구조를 이용하여 문제를 풀 수 있습니다. 이 자료구조는 순서가 없으며 key, value로 저장합니다. 중복도 없습니다 key값으로 장르이름을 이..
2020.05.10 -
프로그래머스 H-Index 자바(java) 풀이 Level 2 정렬 H-Index 문제 정리 어떤 과학자의 H-Index: 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 논문별 인용 횟수는 0회 이상 10,000회 이하이다. 문제 설명 h-index의 정의를 잘 이해하셔야 합니다. 예를들어 {7.8.9.9}가 주어졌다고 합시다. 그러면 여기서 h-index는 몇이 될까요??? 답이 없다고 생각한다면 잘 못 이해하셨습니다. 답은 4 입니다. h값이 인용횟수 안에 있으라는 법은 없습니다. 4번 이상 인용된게 4개 있고 나머지 논문이 4번 이하(0번) 인용되었으므로 최대 h는 4가 맞습니다 문제 풀이 문제 그대로 풀이 하면됩니다. 쉽게 풀이하기..
[정렬] 프로그래머스 level2 H-Index 자바 풀이프로그래머스 H-Index 자바(java) 풀이 Level 2 정렬 H-Index 문제 정리 어떤 과학자의 H-Index: 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 논문별 인용 횟수는 0회 이상 10,000회 이하이다. 문제 설명 h-index의 정의를 잘 이해하셔야 합니다. 예를들어 {7.8.9.9}가 주어졌다고 합시다. 그러면 여기서 h-index는 몇이 될까요??? 답이 없다고 생각한다면 잘 못 이해하셨습니다. 답은 4 입니다. h값이 인용횟수 안에 있으라는 법은 없습니다. 4번 이상 인용된게 4개 있고 나머지 논문이 4번 이하(0번) 인용되었으므로 최대 h는 4가 맞습니다 문제 풀이 문제 그대로 풀이 하면됩니다. 쉽게 풀이하기..
2020.05.09