프로그래머스 전화번호 목록(phone_book) 정답 코드
난이도 ★★★☆☆
힌트
|
저는 빅오를 최대한 낮춰보려고 모든 prefix 를 hash map 에 담아서 체크했습니다. 친구는 이렇게까지 안했는데도 통과되네요. 입력크기가 작아서 그런듯합니다. |
이하는 코드입니다.
|
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
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
public boolean solution(String[] phone_book) {
Map<String, Integer> prefixMap = new HashMap<>();
for (String phoneNo : phone_book) {
for (int i = 1; i <= phoneNo.length(); i++) {
String prefix = phoneNo.substring(0, i);
Integer count = prefixMap.get(prefix);
if (count == null) {
prefixMap.put(prefix, 1);
} else {
prefixMap.put(prefix, count + 1);
}
}
}
for (String phoneNo : phone_book) {
Integer count = prefixMap.get(phoneNo);
if (count > 1) {
return false;
}
}
return true;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 베스트앨범(genres) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 위장(clothes) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 완주하지 못한 선수(participant) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 팰린드롬(Palindrome) 정답 코드 (0) | 2018.06.11 |
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
프로그래머스 완주하지 못한 선수(participant) 정답 코드
난이도 ★☆☆☆☆
힌트
| 동명이인에 주의할 것. 그래서 Set 대신 Map 을 써야한다. |
이하는 코드입니다.
|
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
|
import java.util.HashMap;
import java.util.Map;
public class Solution {
public String solution(String[] participant, String[] completion) {
Map<String, Integer> completionSet = new HashMap<>();
for (String name : completion) {
Integer count = completionSet.get(name);
if (count == null) {
completionSet.put(name, 1);
} else {
completionSet.put(name, count + 1);
}
}
for (String name : participant) {
Integer count = completionSet.get(name);
if (count == null) {
return name;
}
if (count < 2) {
completionSet.remove(name);
} else {
completionSet.put(name, count - 1);
}
}
return null;
}
}
|
cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 위장(clothes) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 전화번호 목록(phone_book) 정답 코드 (0) | 2019.04.15 |
| 프로그래머스 팰린드롬(Palindrome) 정답 코드 (0) | 2018.06.11 |
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
프로그래머스 팰린드롬(Palindrome) 정답 코드
난이도 ★★☆☆☆
틀리기 쉬운 입출력 예제
입력 | 출력 |
"abcdba" "a" | 1 1 |
힌트
무려 n 세제곱의 풀서치를 하는 수밖에 없다. 대신 가지치기를 잘해야한다. 1. 최대 길이를 구하는 것이므로 최대부터 서치할 것. 2. 길이 1은 서치하지 말것. |
이하는 코드입니다.
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 | public int solution(String s) { for (int answer = s.length(); answer > 1; answer--) { int start = 0; int end = 0 + answer - 1; while (end < s.length()) { if (isPalindrome(s, start, end)) { return answer; } start++; end++; } } return 1; } private boolean isPalindrome(String s, int start, int end) { int diffBy2 = (end - start + 1) / 2 - 1; for (int i = 0; i <= diffBy2; i++) { char c1 = s.charAt(start + i); char c2 = s.charAt(end - i); if (c1 != c2) { return false; } } return true; } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 전화번호 목록(phone_book) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 완주하지 못한 선수(participant) 정답 코드 (0) | 2019.04.15 |
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
codility - Fish 정답 및 해설
난이도 ★★★☆☆
문제 요약
최종적으로 몇 마리의 물고기가 살아남는지 리턴하기 1. A.length 가 물고기의 숫자이다. 2. index 가 각 물고기 번호인데, index 가 작을수록 강의 상류에 있다. 3. A[index] 는 각 물고기의 크기이며, 큰 녀석이 작은 녀석을 만나면 잡아먹는다. 4. B[index] 는 각 물고기의 방향이며, 0 은 상류로 가는 방향, 1 은 하류로 가는 방향이다. 5. 모든 물고기의 속도는 같다. (즉, 같은 방향끼리는 못 만난다) |
힌트
Stack 을 써야한다. 왜 써야하는지 깨달으면 절반 이상은 푼 것이다. (B[index] == 1 인 녀석들을 Stack 에 넣자) |
이하는 코드입니다.
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 | public int solution(int[] A, int[] B) { int aliveCount = 0; Stack<Integer> downFishes = new Stack<>(); for (int i = 0; i < A.length; i++) { if (B[i] == 0) { // up fish aliveCount++; if (downFishes.isEmpty()) { continue; } int downFish = downFishes.peek(); while (true) { aliveCount--; if (A[downFish] < A[i]) { downFishes.pop(); if (downFishes.isEmpty()) { break; } downFish = downFishes.peek(); } else { break; } } } else { // down fish downFishes.add(i); aliveCount++; } } return aliveCount; } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 완주하지 못한 선수(participant) 정답 코드 (0) | 2019.04.15 |
|---|---|
| 프로그래머스 팰린드롬(Palindrome) 정답 코드 (0) | 2018.06.11 |
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
codility - Brackets 정답 및 해설
난이도 ★★☆☆☆
문제 요약
괄호의 짝이 정상적으로 맞는지를 리턴. 단, 빈 문자열 입력시에도 정상이라고 리턴할 것 |
힌트
Stack 을 이용하는 전형적인 문제 1. 여는 괄호 (, {, [ 는 push 2. 닫는 괄호 ), }, ] 는 pop 3. stack 이 비어있을 때 pop 하면 에러 발생함. 주의할 것 |
이하는 코드입니다.
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 | public int solution(String S) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < S.length(); i++) { char c = S.charAt(i); if (c == '(' || c == '{' || c == '[') { stack.push(c); } else { if (stack.isEmpty()) { return 0; } char lastC = stack.pop(); if (c == ')' && lastC != '(') { return 0; } if (c == '}' && lastC != '{') { return 0; } if (c == ']' && lastC != '[') { return 0; } } } if (!stack.isEmpty()) { return 0; } return 1; } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 프로그래머스 팰린드롬(Palindrome) 정답 코드 (0) | 2018.06.11 |
|---|---|
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (1. 공간 복잡도) (0) | 2017.07.28 |
알고리즘의 복잡도란? (3. 빅오 표기법)
1. 공간 복잡도 (Space complexity)
2. 시간 복잡도 (Time complexity)
3. 빅오 표기법 (Big-O notation)
복잡도를 표현하는 단위입니다.
거리의 단위에 km 가 있고, 무게의 단위에 kg 이 있듯
복잡도의 단위로는 O 가 있습니다.
공간 복잡도와 시간 복잡도 둘 다에 사용되며
최악의 경우를 가정하여 나타냅니다.
최악이 무슨 말인지 아래 예시를 보여드리겠습니다.
1 2 3 4 5 6 7 8 9 | public boolean contains(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { if (arr[i] == num) { return true; } } return false; } | cs |
위 함수의 경우, 운이 좋으면 한번만에 찾아서 return true가 될 수도 있고,
운이 최악이면 arr 전체를 다 뒤져야할수도 있습니다.
Big-O 는 이 최악을 가정하여 나타내므로
O(n) 이 위 함수의 시간 복잡도입니다.
n 은 뭐냐면 입력받은 배열의 길이를 뜻합니다.
또 특이한 점은 상수는 간소화한다는 것입니다.
O(k * 1) => O(1)
O(k * n) => O(n)
O(n + k) => O(n)
O(k * n제곱) => O(n제곱)
아래 함수를 예로 들겠습니다. (함수 내용 이해할 필요 없음)
시간 복잡도는 "2n + 2" 이지만 (n + n + 2)
Big-O 표기법으로는 O(n) 입니다.
공간 복잡도는 "n + 3" 이지만 (checked, i => n + 2 + 1)
Big-O 표기법으로는 O(n) 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public int solution(int[] A) { boolean[] checked = new boolean[A.length + 2]; for (int i = 0; i < A.length; i++) { checked[A[i]] = true; } for (int i = 1; i < checked.length; i++) { if (!checked[i]) { return i; } } return -1; } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
|---|---|
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (1. 공간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
알고리즘의 복잡도란? (2. 시간 복잡도)
1. 공간 복잡도 (Space complexity)
2. 시간 복잡도 (Time complexity)
반복문을 총 몇번 도는지를 의미합니다.
아래는 1부터 n까지의 합을 구하는 함수입니다.
시간 복잡도는 "n" 입니다.
1 2 3 4 5 6 7 8 9 | public int solution(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } return sum; } | cs |
같은 함수를 수학공식을 이용해 아래와 같이 바꾸면 시간 복잡도는 "1" 이 됩니다.
(수학을 잘하면 알고리즘에 유리합니다)
1 2 3 | public int solution(int n) { return (1 + n) * n / 2; } | cs |
API 사용시에는 주의해야합니다.
아래 함수의 시간 복잡도는 얼마일까요? "A.length" 일까요?
(함수 내용은 이해할 필요 없음)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public int solution(int[] A) { List<Integer> marks = new ArrayList<>(); for (int i = 0; i < A.length; i++) { if (A[i] > A.length) { return 0; } if (marks.contains(A[i])) { return 0; } marks.add(A[i]); } return 1; } | cs |
답은 "A.length X A.length" 입니다. "A.length" 의 제곱이지요.
왜냐하면 ArrayList.contains() 함수의 시간 복잡도가 "해당 list의 길이" 이기 때문입니다.
(내부적으로 list 전체를 반복문을 돌면서 인자로 던져준 객체가 있는지 확인합니다)
위 함수에서 ArrayList 대신 HashSet 을 사용하면 어떨까요?
출력은 같지만 복잡도는 "A.length" 가 됩니다.
HashSet.contains() 함수의 시간 복잡도는 "1" 이기 때문입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public int solution(int[] A) { Set<Integer> marks = new HashSet<>(); for (int i = 0; i < A.length; i++) { if (A[i] > A.length) { return 0; } if (marks.contains(A[i])) { return 0; } marks.add(A[i]); } return 1; } | cs |
3. 빅오 표기법 (Big-O notation)
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
|---|---|
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (1. 공간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
| codility - MaxProductOfThree 정답 및 해설 (0) | 2017.07.12 |
알고리즘의 복잡도란? (1. 공간 복잡도)
복잡도가 낮을 수록 성능이 뛰어난 알고리즘입니다.
알고리즘의 복잡도(Complexity)는 두 가지 요소로 측정합니다.
1. 공간 복잡도 (Space complexity)
간단합니다. 사용되는 변수의 개수를 의미합니다.
단, 인자 변수들은 일반적으로 제외하고 카운트합니다.
예를들어 아래와 같은 함수의 경우, 공간 복잡도는 "2" 입니다. (sum, i)
(함수 내용은 이해할 필요 없음)
1 2 3 4 5 6 7 8 9 | public int solution(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } return sum; } | cs |
또 하나의 예시를 들어보면, 아래 함수의 경우 공간 복잡도는 "N + 3" 입니다. (counter, tmpMaxCounter, doneMaxCounter, i)
(마찬가지로 함수 내용은 이해할 필요 없음)
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 | public int[] solution(int N, int[] A) { int[] counter = new int[N]; int tmpMaxCounter = 0; int doneMaxCounter = 0; for (int i = 0; i < A.length; i++) { if (A[i] > N) { doneMaxCounter = tmpMaxCounter; } else { if (counter[A[i] - 1] < doneMaxCounter) { counter[A[i] - 1] = doneMaxCounter; } counter[A[i] - 1]++; if (counter[A[i] - 1] > tmpMaxCounter) { tmpMaxCounter = counter[A[i] - 1]; } } } if (doneMaxCounter > 0) { for (int i = 0; i < counter.length; i++) { if (counter[i] < doneMaxCounter) { counter[i] = doneMaxCounter; } } } return counter; } | cs |
2. 시간 복잡도 (Time complexity)
3. 빅오 표기법 (Big-O notation)
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
|---|---|
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
| codility - MaxProductOfThree 정답 및 해설 (0) | 2017.07.12 |
| codility - Distinct 정답 및 해설 (0) | 2017.07.12 |
