프로그래머스 더 맵게(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 |
프로그래머스 다리를 지나는 트럭 정답 코드
뿌리튼튼 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 |
[추천] Set of Set 문제 및 Set.hashCode()고찰
뿌리튼튼 CS/Java2019. 4. 18. 15:38
문제
출력결과는 무엇일까요?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<Set<Integer>> sets = new HashSet<>();
Set<Integer> set1 = new HashSet<>();
set1.add(1);
set1.add(11);
sets.add(set1);
System.out.println(sets.size());
set1.add(111);
sets.remove(set1);
System.out.println(sets.size());
}
}
|
cs |
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
정답
해설
HashSet.remove() 소스코드를 계속 따라가보면 HashMap.removeEntryForKey() 까지 이어지고,
여기서 코드를 잘보면 hashCode() 값 비교를 통해 remove를 시도하고 있습니다.
그런데 현재 Set 의 멤버도 Set 이므로 HashSet.hashCode() 를 살펴봐야합니다.
해당 소스코드를 보면 충격적이게도,
반복문을 돌며 멤버 전체의 hashCode() 를 더해 리턴하고 있습니다.
따라서 Set 의 내용물(멤버)이 바뀌면 hashCode() 값도 바뀌게 됩니다.
문제로 돌아가보면,
16라인에서 set1 의 내용물이 바뀜과 동시에 set1 의 hashCode() 값도 변해버려서
17라인에서 remove() 가 set1 을 찾지못해 지우는데 실패하게된 것입니다.
'뿌리튼튼 CS > Java' 카테고리의 다른 글
| 심심풀이 문제6 - 상속과 오버라이딩 (Heritage & Overriding) (0) | 2016.10.04 |
|---|---|
| 심심풀이 문제5 - 예외 처리 흐름 (Exception handling flow) (0) | 2016.10.04 |
| 심심풀이 문제4 - Object Assign (객체 대입) (0) | 2016.10.04 |
| 심심풀이 문제3 - Call by Value vs Call by Reference (0) | 2016.10.04 |
| 심심풀이 문제2 - String (0) | 2016.08.02 |
프로그래머스 네트워크(computers) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 17. 16:41
난이도 ★★★★☆
틀리기 쉬운 입출력 예제
| 입력 | 출력 |
|
3, {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}} 1, {{1}} 4, {{1,1,1,1}, {1,1,1,0}, {1,1,1,0}, {1,0,0,1}} |
3 1 1 |
힌트
|
그래프, DFS, BFS로 어렵게 풀지않고, 탐색을 효율적으로 잘하는 방법으로 풀었습니다.
1. computers[i][j] == computers[j][i] 인 점을 이용해 한 방향으로만 서치한다. 2. Set 을 차곡차곡 만들어나가며, 합칠 일이 있으면 효율적으로 잘(?) 합친다.
※
해결하였고, 코드를 아래에 추가 첨부하였습니다. 해결한 원리는 내용이 길어 별도 글로 작성하였습니다. (링크. 한마디로 요약하면 hashCode() 때문) |
이하는 코드 및 성능입니다.
|
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
|
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class Solution {
private List<Set<Integer>> sets; // TODO List -> Set
public int solution(int n, int[][] computers) {
sets = new LinkedList<>();
for (int i = 0; i < n - 1; i++) {
Set<Integer> iSet = getSet(i);
if (iSet == null) {
iSet = new HashSet<>();
iSet.add(i);
sets.add(iSet);
}
for (int j = i + 1; j < n; j++) {
if (computers[i][j] == 1) {
Set<Integer> jSet = getSet(j);
if (iSet == jSet) { // i, j are already in the same set
continue;
}
if (jSet == null) {
iSet.add(j);
} else {
// Merge iSet, jSet
iSet.addAll(jSet);
sets.remove(jSet); // TODO O(n) -> O(1)
}
}
}
}
int answer = sets.size();
if (getSet(n - 1) == null) { // 위 서치에서 누락되기 때문에 체크해줌
answer++;
}
return answer;
}
/**
* @return A set which contains the num, or null
*/
private Set<Integer> getSet(int num) {
for (Set<Integer> set : sets) {
if (set.contains(num)) {
return set;
}
}
return null;
}
}
|
cs |
↓↓↓ List 를 Set 으로 바꾼 개선코드 및 성능 ↓↓↓
|
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
|
import java.util.HashSet;
import java.util.Set;
public class Solution {
private Set<Set<Integer>> sets;
public int solution(int n, int[][] computers) {
sets = new HashSet<>();
for (int i = 0; i < n - 1; i++) {
Set<Integer> iSet = getSet(i);
if (iSet == null) {
iSet = new MySet<>();
iSet.add(i);
sets.add(iSet);
}
for (int j = i + 1; j < n; j++) {
if (computers[i][j] == 1) {
Set<Integer> jSet = getSet(j);
if (iSet == jSet) { // i, j are already in the same set
continue;
}
if (jSet == null) {
iSet.add(j);
} else {
// Merge iSet, jSet
iSet.addAll(jSet);
sets.remove(jSet);
}
}
}
}
int answer = sets.size();
if (getSet(n - 1) == null) { // 위 서치에서 누락되기 때문에 체크해줌
answer++;
}
return answer;
}
/**
* @return A set which contains the num, or null
*/
private Set<Integer> getSet(int num) {
for (Set<Integer> set : sets) {
if (set.contains(num)) {
return set;
}
}
return null;
}
private class MySet<E> extends HashSet<E> {
@Override
public int hashCode() {
return System.identityHashCode(this); // equivalent to Object.hashCode()
}
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 기능개발(progresses) 정답 코드 (0) | 2019.04.25 |
|---|---|
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
| 프로그래머스 여행경로(tickets) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 단어 변환(words) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 타겟 넘버 정답 코드 (0) | 2019.04.16 |
프로그래머스 여행경로(tickets) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 16. 16:30
난이도 ★★★★☆
틀리기 쉬운 입출력 예제
| 입력 | 출력 |
| {{"ICN", "JFK"}, {"JFK", "ICN"}, {"ICN", "JFK"}, {"JFK", "ICN"}} | [ICN, JFK, ICN, JFK, ICN] |
힌트
|
전형적인 너비우선탐색(BFS) 문제이지만 구현이 어렵습니다.
1. 위 입출력 예시처럼 동일한 티켓이 여러장 입력될 수도 있다는 점 2. 반드시 모든 티켓을 다 사용해야한다는 점 3. 정렬이 필요한 점
구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요? 별도 배열을 두지마시고 저처럼 객체(Ticket.count)로 만드시길 추천드립니다. 익숙치 않아도 노력해보시길!
※ String[][] tickets 를 한번 서치하여 ticketSet 을 만들고 싶었는데 count 값을 넣어줄 방법을 못찾아서 tmpCountMap 을 거쳐야만 했습니다. 안거치고 넣을 수 있는 방법이 있을까요? |
이하는 코드입니다.
|
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class Solution {
public String[] solution(String[][] tickets) {
Map<Ticket, Integer> tmpCountMap = new HashMap<>(); // 표별 개수 세는 용도로 임시
for (String[] ticketStr : tickets) {
Ticket ticket = new Ticket();
ticket.start = ticketStr[0];
ticket.end = ticketStr[1];
Integer count = tmpCountMap.get(ticket);
if (count == null) {
tmpCountMap.put(ticket, 1);
} else {
tmpCountMap.put(ticket, count + 1);
}
}
Set<Ticket> ticketSet = new TreeSet<>();
for (Ticket ticket : tmpCountMap.keySet()) {
int count = tmpCountMap.get(ticket);
ticket.count = count; // 위에서 tmpCountMap으로 측정한 count
ticketSet.add(ticket);
}
String[] answer = new String[tickets.length + 1];
List<String> path = getPath("ICN", ticketSet);
path.toArray(answer);
return answer;
}
private LinkedList<String> getPath(String start, Set<Ticket> tickets) {
LinkedList<String> path = null;
if (allUsed(tickets)) {
path = new LinkedList<>();
path.add(start);
return path;
}
for (Ticket ticket : tickets) {
if (ticket.count < 1 || !ticket.start.equals(start)) {
continue;
}
ticket.count--;
path = getPath(ticket.end, tickets);
ticket.count++;
if (path != null) {
path.addFirst(start); // This is why use LinkedList
break;
}
}
return path;
}
private boolean allUsed(Set<Ticket> tickets) {
for (Ticket ticket : tickets) {
if (ticket.count > 0) {
return false;
}
}
return true;
}
private class Ticket implements Comparable<Ticket> {
String start;
String end;
int count;
@Override
public int compareTo(Ticket that) {
int startComp = this.start.compareTo(that.start);
if (startComp != 0) {
return startComp;
}
return this.end.compareTo(that.end);
}
@Override
public boolean equals(Object arg0) {
if (!(arg0 instanceof Ticket)) {
return false;
}
Ticket that = (Ticket) arg0;
return this.start.equals(that.start) && this.end.equals(that.end);
}
@Override
public int hashCode() {
return (start + "," + end).hashCode();
}
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 다리를 지나는 트럭 정답 코드 (0) | 2019.04.23 |
|---|---|
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
| 프로그래머스 단어 변환(words) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 타겟 넘버 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 프린터(priorities) 정답 코드 (0) | 2019.04.16 |
