프로그래머스 더 맵게(scoville) 정답 코드
뿌리튼튼 CS/Algorithm2019. 5. 13. 23:34
난이도 ★★★☆☆
틀리기 쉬운 입출력 예제
| 입력 | 출력 |
|
{0}, 0 {0}, 1 {1, 1, 1}, 7 {1, 1, 1}, 8 |
0 -1 2 -1 |
힌트
|
정렬대신 TreeMap을 꼭 써야합니다.
매번 정렬하면 그때마다 O(N logN)이 들어가지만, TreeMap을 이용하면 그때마다 O(logN)만 들어갑니다. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import java.util.TreeMap;
public class Solution {
public int solution(int[] scoville, int K) {
TreeMap<Integer, Integer> scovilleCountMap = new TreeMap<>(); // 중복입력에 대응하기 위해 Set이 아닌 Map
for (int num : scoville) {
push(num, scovilleCountMap);
}
int answer = 0;
while (true) {
int min = popMin(scovilleCountMap);
if (min >= K) {
break;
}
Integer nextMin = popMin(scovilleCountMap);
if (nextMin == null) {
answer = -1;
break;
}
int newNum = min + (nextMin * 2);
push(newNum, scovilleCountMap);
answer++;
}
return answer;
}
private Integer popMin(TreeMap<Integer, Integer> countMap) {
if (countMap.isEmpty()) {
return null;
}
int min = countMap.firstKey();
int count = countMap.get(min);
if (count > 1) {
countMap.put(min, count - 1);
} else {
countMap.remove(min);
}
return min;
}
private void push(int num, TreeMap<Integer, Integer> countMap) {
Integer count = countMap.get(num);
if (count == null) {
countMap.put(num, 1);
} else {
countMap.put(num, count + 1);
}
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 주식가격(prices) 정답 코드 (0) | 2019.05.08 |
|---|---|
| 프로그래머스 탑(heights) 정답 코드 (0) | 2019.05.08 |
| 프로그래머스 기능개발(progresses) 정답 코드 (0) | 2019.04.25 |
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
프로그래머스 주식가격(prices) 정답 코드
뿌리튼튼 CS/Algorithm2019. 5. 8. 22:29
난이도 ★★☆☆☆
힌트
|
탑 문제와 완전히 동일한 로직으로 Queue를 쓰지 않고 구현했습니다. 왜 필요한지 잘 모르겠네요...?;; 코드 짧게 빠르게 풀긴 했는데 O(n^2)이라 찝찝합니다. 더 좋은 로직 아시는 분은 공유 부탁드립니다. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
answer[answer.length - 1] = 0; // always 0
for (int i = 0; i < prices.length - 1; i++) {
int sec = 1;
for (int j = i + 1; j < prices.length - 1; j++) {
if (prices[j] >= prices[i]) {
sec++;
} else {
break;
}
}
answer[i] = sec;
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 더 맵게(scoville) 정답 코드 (1) | 2019.05.13 |
|---|---|
| 프로그래머스 탑(heights) 정답 코드 (0) | 2019.05.08 |
| 프로그래머스 기능개발(progresses) 정답 코드 (0) | 2019.04.25 |
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
프로그래머스 탑(heights) 정답 코드
뿌리튼튼 CS/Algorithm2019. 5. 8. 22:26
난이도 ★★☆☆☆
힌트
|
주식가격 문제와 완전히 동일한 로직으로 Queue를 쓰지 않고 구현했습니다. 왜 필요한지 잘 모르겠네요...?;; 코드 짧게 빠르게 풀긴 했는데 O(n^2)이라 찝찝합니다. 더 좋은 로직 아시는 분은 공유 부탁드립니다. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class Solution {
public int[] solution(int[] heights) {
int[] answer = new int[heights.length];
answer[0] = 0; // always 0
// O(n^2)
for (int i = heights.length - 1; i > 0; i--) {
int answerPos = 0;
for (int j = i - 1; j >= 0; j--) {
if (heights[j] > heights[i]) {
answerPos = j + 1;
break;
}
}
answer[i] = answerPos;
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 더 맵게(scoville) 정답 코드 (1) | 2019.05.13 |
|---|---|
| 프로그래머스 주식가격(prices) 정답 코드 (0) | 2019.05.08 |
| 프로그래머스 기능개발(progresses) 정답 코드 (0) | 2019.04.25 |
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
프로그래머스 기능개발(progresses) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 25. 08:54
난이도 ★★☆☆☆
힌트
|
평이한 문제입니다. 그냥 Queue 하나 만들어서 문제 그대로 차근차근 구현했어요. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public int[] solution(int[] progresses, int[] speeds) {
Queue<Job> jobs = new LinkedList<>();
for (int i = 0; i < progresses.length; i++) {
Job job = new Job();
job.progress = progresses[i];
job.speed = speeds[i];
jobs.add(job);
}
List<Integer> doneCountList = new ArrayList<>();
while (!jobs.isEmpty()) {
int doneCount = 0;
boolean lastJobIsDone = true; // for the first job
for (Job job : jobs) {
job.progress += job.speed;
if (lastJobIsDone && job.progress >= 100) {
doneCount++;
} else {
lastJobIsDone = false;
}
}
if (doneCount > 0) {
for (int i = 0; i < doneCount; i++) {
jobs.remove();
}
doneCountList.add(doneCount);
}
}
int[] answer = new int[doneCountList.size()];
for (int i = 0; i < doneCountList.size(); i++) {
answer[i] = doneCountList.get(i);
}
return answer;
}
private class Job {
int progress;
int speed;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 주식가격(prices) 정답 코드 (0) | 2019.05.08 |
|---|---|
| 프로그래머스 탑(heights) 정답 코드 (0) | 2019.05.08 |
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
| 프로그래머스 여행경로(tickets) 정답 코드 (0) | 2019.04.16 |
