Greedy algorithm
Task
3. μ‘°μ΄μ€ν± in Programmers (Level 2)
π Problem
https://programmers.co.kr/learn/courses/30/lessons/42860
π The point
- Use the greedy
- Check the condition
- Choose the best at each moment
- move up vs down
- compare the length of movement
- move left vs right
- compare the length of movement
- move up vs down
π Answer
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
class Solution {
public int solution(String name) {
int answer = 0;
int len = name.length();
// if name only consists of 'A'
// -> the minimum movement = just go right continuously
int min = len - 1;
for (int i = 0; i < len; i++) {
// get each char from String
char c = name.charAt(i);
// decide to move 'up or down'
// up : c - 'A'
// down : 'Z' - c + 1
int move = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1);
answer += move;
// decide to move 'right or left'
// 1. first, go right -> count index by using nextIndex
int nextIndex = i + 1;
while (nextIndex < len && name.charAt(nextIndex) == 'A')
nextIndex++;
// 2. compare which is the minimum value and update 'min'
// - go right : min
// - go back to left : (i * 2) + len - nextIndex
// -> i * 2 : go right + go back to left
// -> len - nextIndex : count from last index
min = Math.min(min, (i * 2) + len - nextIndex);
}
answer += min;
return answer;
}
}
The source : https://hellodavid.tistory.com/4a
It is not difficult code, but I think it takes long time to come up with the way to solve.
And I have a heavy stomachache these days, so I make a reservation on hostipal on next wednesday π₯² I hope Iβm fine.
Comments powered by Disqus.