프로그래머스 주식가격(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 |
프로그래머스 다리를 지나는 트럭 정답 코드
뿌리튼튼 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 |
프로그래머스 프린터(priorities) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 16. 09:24
난이도 ★★★☆☆
힌트
|
문제에서 설명하는 그대로, 사람이 생각하는 그대로를 코딩으로 옮겼습니다. (Stack 을 쓰지 않음) 다만 자료구조를 TreeMap, LinkedList 로 써서 성능을 많이 향상시켰습니다. |
이하는 코드입니다.
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 63 64 65 66 67 68 69 70 | import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.TreeMap; public class Solution { public int solution(int[] priorities, int location) { TreeMap<Integer, Integer> countMap = new TreeMap<>(); // 뒤에 나보다 큰 녀석이 있는지 확인용 LinkedList<Doc> remains = new LinkedList<>(); for (int i = 0; i < priorities.length; i++) { int priority = priorities[i]; Integer count = countMap.get(priority); if (count == null) { countMap.put(priority, 1); } else { countMap.put(priority, count + 1); } Doc doc = new Doc(); doc.id = i; doc.priority = priority; remains.add(doc); } List<Doc> results = new ArrayList<>(); // 최종 결과 while (!remains.isEmpty()) { Doc doc = remains.getFirst(); Integer higherPriority = countMap.higherKey(doc.priority); // TreeMap을 쓴 이유임 if (higherPriority == null) { // 나보다 큰 녀석이 뒤에 없음 results.add(doc); remains.removeFirst(); int count = countMap.get(doc.priority); if (count > 1) { countMap.put(doc.priority, count - 1); } else { countMap.remove(doc.priority); } } else { // 맨앞의 녀석을 맨뒤로 보냄. LinkedList를 쓴 이유임 remains.removeFirst(); remains.addLast(doc); } } int answer = 0; for (int i = 0; i < results.size(); i++) { Doc doc = results.get(i); if (doc.id == location) { answer = i + 1; break; } } return answer; } private class Doc { int id; int priority; } } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 단어 변환(words) 정답 코드 (0) | 2019.04.16 |
|---|---|
| 프로그래머스 타겟 넘버 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 쇠막대기(arrangement) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 H-Index(citations) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 가장 큰 수(numbers) 정답 코드 (0) | 2019.04.15 |
프로그래머스 쇠막대기(arrangement) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 17:44
난이도 ★★☆☆☆
힌트
|
풀이는 어렵지 않은데 문제가 매우 아름답네요. 레이져로 자르는 것을 괄호 여닫는 것으로 모델링하다니 ㄷㄷ
1. 귀찮은 녀석들은 replaceAll 로 치환해버리자 (특수문자 escape 주의) 2. 단순 count 를 위한 stack 이므로 int 변수만으로도 충분함. 굳이 Stack 자료구조 불필요. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Solution {
public int solution(String arrangement) {
int stack = 0;
int answer = 0;
String replacedArrangement = arrangement.replaceAll("\\(\\)", "L"); // escape (, )
for (int i = 0; i < replacedArrangement.length(); i++) {
char c = replacedArrangement.charAt(i);
if (c == '(') {
stack++;
answer++;
} else if (c == ')') {
stack--;
} else if (c == 'L') {
answer += stack;
}
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 타겟 넘버 정답 코드 (0) | 2019.04.16 |
|---|---|
| 프로그래머스 프린터(priorities) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 H-Index(citations) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 가장 큰 수(numbers) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 K번째수(commands) 정답 코드 (1) | 2019.04.15 |
