프로그래머스 타겟 넘버 정답 코드
뿌리튼튼 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 |
프로그래머스 H-Index(citations) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 17:37
난이도 ★★☆☆☆
틀리기 쉬운 입출력 예제
| 입력 | 출력 |
|
{0} {0, 0} {2, 0} |
0 0 1 |
힌트
|
잘 생각해보시면 정렬 1번 + 서치 1번이면 끝납니다. |
이하는 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import java.util.Arrays;
public class Solution {
public int solution(int[] citations) {
int answer = 0;
Arrays.sort(citations);
for (int i = 0; i < citations.length; i++) {
int h = citations.length - i;
if (citations[i] >= h) {
answer = h;
break;
}
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 프린터(priorities) 정답 코드 (0) | 2019.04.16 |
|---|---|
| 프로그래머스 쇠막대기(arrangement) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 가장 큰 수(numbers) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 K번째수(commands) 정답 코드 (1) | 2019.04.15 |
| 프로그래머스 베스트앨범(genres) 정답 코드 (0) | 2019.04.15 |
프로그래머스 가장 큰 수(numbers) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 17:30
난이도 ★★★☆☆
틀리기 쉬운 입출력 예제 (출처 : 고건희님)
| 입력 | 출력 |
| {40, 403} {40, 405} {40, 404} {12, 121} {2, 22, 223} {21, 212} {41, 415} {2, 22} {70, 0, 0, 0} {0, 0, 0, 0} {0, 0, 0, 1000} {12, 1213} |
40403 40540 40440 12121 223222 21221 41541 222 70000 0 1000000 121312 |
힌트
|
평범한 정렬문제이지만 설명 및 테스트케이스가 부족하여 잘못생각하기 쉬운 문제입니다. 매우 헤맸습니다.
1. 동일한 숫자가 입력될 수 있다는 점 2. "0000" → "0" 으로 출력해야하는 점 꼭 기억하세요. |
이하는 코드입니다.
|
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
|
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String solution(int[] numbers) {
String[] nums = new String[numbers.length];
for (int i = 0; i < numbers.length; i++) {
nums[i] = String.valueOf(numbers[i]);
}
Arrays.sort(nums, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length()) { // simple case
return o2.compareTo(o1); // order by num desc
}
String sum = o1 + o2;
String reverseSum = o2 + o1;
return reverseSum.compareTo(sum);
}
});
String answer;
if (nums.length > 0 && "0".equals(nums[0])) { // means "0000"
answer = "0";
} else {
StringBuilder sb = new StringBuilder();
for (String num : nums) {
sb.append(num);
}
answer = sb.toString();
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 쇠막대기(arrangement) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 H-Index(citations) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 K번째수(commands) 정답 코드 (1) | 2019.04.15 |
| 프로그래머스 베스트앨범(genres) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 위장(clothes) 정답 코드 (0) | 2019.04.15 |
프로그래머스 K번째수(commands) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 17:11
난이도 ★☆☆☆☆
힌트
|
Java 내장 sort를 이용하면 쉽게 풀리는 기초문제 |
이하는 코드입니다.
|
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
|
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for (int i = 0; i < commands.length; i++) {
List<Integer> list = new ArrayList<>();
int start = commands[i][0] - 1;
int end = commands[i][1] - 1;
int pick = commands[i][2] - 1;
for (int j = start; j <= end; j++) {
list.add(array[j]);
}
Collections.sort(list);
answer[i] = list.get(pick);
}
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 H-Index(citations) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 가장 큰 수(numbers) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 베스트앨범(genres) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 위장(clothes) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 전화번호 목록(phone_book) 정답 코드 (0) | 2019.04.15 |
프로그래머스 베스트앨범(genres) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 16:54
난이도 ★★★☆☆
힌트
|
Java 자료구조 및 Comparable 을 잘 이용하면 쉽게 구현할 수 있습니다. 해시문제인지 정렬문제인지 헷갈리네요. |
이하는 코드입니다.
|
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
|
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution {
public int[] solution(String[] genres, int[] plays) {
Map<String, Integer> indexMap = new HashMap<>();
List<Genre> genreList = new ArrayList<>();
for (int i = 0; i < genres.length; i++) {
Genre genre;
Integer index = indexMap.get(genres[i]);
if (index == null) {
genre = new Genre();
genreList.add(genre);
indexMap.put(genres[i], genreList.size() - 1);
}
else {
genre = genreList.get(index);
}
Song song = new Song();
song.id = i;
song.play = plays[i];
genre.songs.add(song);
genre.sum += plays[i];
}
Collections.sort(genreList);
int count = 0;
for (Genre genre : genreList) {
Collections.sort(genre.songs);
if (genre.songs.size() > 1) {
count += 2;
} else {
count += 1;
}
}
int[] answer = new int[count];
int answerIdx = 0;
for (Genre genre : genreList) {
for (int i = 0; i < genre.songs.size() && i < 2; i++) {
answer[answerIdx] = genre.songs.get(i).id;
answerIdx++;
}
}
return answer;
}
private class Genre implements Comparable<Genre> {
int sum;
List<Song> songs;
public Genre() {
sum = 0;
songs = new ArrayList<>();
}
@Override
public int compareTo(Genre that) {
return Integer.compare(that.sum, this.sum); // order by sum desc
}
}
private class Song implements Comparable<Song> {
int id;
int play;
@Override
public int compareTo(Song that) {
if (this.play == that.play) {
return Integer.compare(this.id, that.id); // order by id asc
}
return Integer.compare(that.play, this.play); // order by play desc
}
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 가장 큰 수(numbers) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 K번째수(commands) 정답 코드 (1) | 2019.04.15 |
| 프로그래머스 위장(clothes) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 전화번호 목록(phone_book) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 완주하지 못한 선수(participant) 정답 코드 (0) | 2019.04.15 |
프로그래머스 위장(clothes) 정답 코드
뿌리튼튼 CS/Algorithm2019. 4. 15. 16:43
난이도 ★★★☆☆
힌트
|
이거 해시 문제가 아니고 수학문제(경우의수)입니다 ;;; 해시인줄 알고 낚여서 한참 걸렸네요. 만약 고딩으로 돌아간다면 5분 안으로 풀었을 것 같아요. 팩토리얼, 콤비네이션, 퍼무테이션 이런거 쓰는거 아니고 순수 경우의 수 문제입니다. |
이하는 코드입니다.
|
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
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int solution(String[][] clothes) {
int answer = 1;
Map<String, Integer> clothesMap = new HashMap<>();
for (String[] cloth : clothes) {
Integer count = clothesMap.get(cloth[1]);
if (count == null) {
clothesMap.put(cloth[1], 1);
} else {
clothesMap.put(cloth[1], count + 1);
}
}
for (String cloth : clothesMap.keySet()) {
int count = clothesMap.get(cloth);
answer *= (count + 1);
}
answer--;
return answer;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 K번째수(commands) 정답 코드 (1) | 2019.04.15 |
|---|---|
| 프로그래머스 베스트앨범(genres) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 전화번호 목록(phone_book) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 완주하지 못한 선수(participant) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 팰린드롬(Palindrome) 정답 코드 (0) | 2018.06.11 |
