프로그래머스 단어 변환(words) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 16. 10:28
난이도 ★★★★☆
힌트
|
전형적인 너비우선탐색(BFS) 문제입니다. 최소값을 찾는 문제이므로 전역(혹은 그런느낌)으로 최소값을 저장할 변수(minCountMap)를 잘 운용하셔야 해요.
구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요? |
이하는 코드입니다.
|
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
|
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
private Map<String, Integer> minCountMap;
private int MAX_COUNT;
public int solution(String start, String target, String[] words) {
minCountMap = new HashMap<>();
MAX_COUNT = words.length;
Set<Word> wordSet = new HashSet<>();
for (String word : words) {
Word wordObj = new Word();
wordObj.word = word;
wordObj.used = false;
wordSet.add(wordObj);
}
int answer = getMinCount(start, target, wordSet);
if (answer > MAX_COUNT) { // no way
return 0;
}
return answer;
}
private int getMinCount(String start, String target, Set<Word> words) {
Integer minCount = minCountMap.get(start);
if (minCount == null) {
minCount = MAX_COUNT + 1;
}
for (Word word : words) {
if (word.used || !isNext(start, word.word)) {
continue;
}
if (target.equals(word.word)) {
minCount = 1;
break;
}
word.used = true;
int count = getMinCount(word.word, target, words) + 1;
word.used = false;
if (count < minCount) {
minCount = count;
}
}
minCountMap.put(start, minCount);
return minCount;
}
private boolean isNext(String a, String b) {
int diffCount = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
diffCount++;
if (diffCount > 1) {
return false;
}
}
}
return true;
}
private class Word {
String word;
boolean used;
@Override
public int hashCode() {
return word.hashCode();
}
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 네트워크(computers) 정답 코드 (0) | 2019.04.17 |
|---|---|
| 프로그래머스 여행경로(tickets) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 타겟 넘버 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 프린터(priorities) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 쇠막대기(arrangement) 정답 코드 (0) | 2019.04.15 |
프로그래머스 타겟 넘버 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 16. 10:01
난이도 ★★★☆☆
힌트
|
반복문이 아닌 재귀로 풀었습니다. f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])
동적계획법(Dynamic Programming)도 사용하였는데, 이부분은 성능을 위한 것이므로 없어도 결과에는 영향이 없습니다. (헷갈릴시 cache 변수를 제거하시면 됩니다) |
이하는 코드입니다.
|
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
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
private Map<Integer, Integer>[] cache; // Dynamic Programming
private int[] numbers;
public int solution(int[] numbers, int target) {
this.numbers = numbers;
cache = new HashMap[numbers.length]; // TODO Remove the warning
for (int i = 0; i < numbers.length; i++) {
cache[i] = new HashMap<>();
}
int answer = getCount(0, target);
return answer;
}
// f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])
private int getCount(int startIdx, int target) {
if (startIdx >= numbers.length) {
return 0;
}
if (startIdx == numbers.length - 1) {
if (numbers[startIdx] == target || numbers[startIdx] == target * -1) { // Don't forget -1
return 1;
} else {
return 0;
}
}
Integer count = cache[startIdx].get(target);
if (count != null) {
return count;
}
count = getCount(startIdx + 1, target + numbers[startIdx]) + getCount(startIdx + 1, target - numbers[startIdx]);
cache[startIdx].put(target, count);
return count;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 여행경로(tickets) 정답 코드 (0) | 2019.04.16 |
|---|---|
| 프로그래머스 단어 변환(words) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 프린터(priorities) 정답 코드 (0) | 2019.04.16 |
| 프로그래머스 쇠막대기(arrangement) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 H-Index(citations) 정답 코드 (0) | 2019.04.15 |
프로그래머스 프린터(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 |
