Strong Root

난이도 

 

문제를 보시려면 여기를 클릭

 

 

 

틀리기 쉬운 입출력 예제

입력 출력

{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

 

난이도 

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

탑 문제와 완전히 동일한 로직으로 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

 

난이도 

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

주식가격 문제와 완전히 동일한 로직으로 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

 

난이도 

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

평이한 문제입니다. 그냥 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