프로그래머스 주식가격(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 |
프로그래머스 다리를 지나는 트럭 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 23. 15:08
난이도 ★★★★☆
틀리기 쉬운 입출력 예제
| 입력 | 출력 |
|
2, 4, {1, 2, 1, 2} |
6 |
힌트
|
쉬운 듯하면서도 저는 좀 어려웠습니다. (고려해야할 상황이 많더라구요) 특별한 아이디어는 없고 그냥 문제 그대로 차근차근 구현했어요.
기본적으로 Queue 두개는 꼭 필요하실거에요. 1. 아직 다리에 진입안한 트럭 Queue (제 코드의 trucks) 2. 다리를 건너는 중인 트럭 Queue (제 코드의 ingTrucks) |
이하는 코드입니다.
|
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
|
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Truck> trucks = new LinkedList<>(); // 아직 다리에 진입하지 않은 트럭들
Queue<Truck> ingTrucks = new LinkedList<>(); // 다리를 건너는 중인 트럭들
for (int w : truck_weights) {
Truck truck = new Truck();
truck.weight = w;
truck.position = 0;
trucks.add(truck);
}
int sec = 0;
while (!trucks.isEmpty() || !ingTrucks.isEmpty()) { // Until both are empty
sec++;
Truck doneTruck = null;
int sum = 0;
for (Truck truck : ingTrucks) {
sum += truck.weight;
truck.position++;
if (truck.position > bridge_length) {
doneTruck = truck;
}
}
if (doneTruck != null) {
ingTrucks.remove(doneTruck);
sum -= doneTruck.weight;
}
if (!trucks.isEmpty() && (ingTrucks.size() < bridge_length)) {
Truck truck = trucks.peek();
if (truck.weight + sum <= weight) {
trucks.remove(truck);
ingTrucks.add(truck);
truck.position++;
}
}
}
return sec;
}
private class Truck {
int weight;
int position;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 탑(heights) 정답 코드 (0) | 2019.05.08 |
|---|---|
| 프로그래머스 기능개발(progresses) 정답 코드 (0) | 2019.04.25 |
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
| 프로그래머스 여행경로(tickets) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 단어 변환(words) 정답 코드 (0) | 2019.04.16 |
