순열 : 요소 n개 중에서 m개를 순서있게 뽑는 경우의 수
nPm = n! / (n - m)!
조합 : 요소 n개 중에서 m개를 순서에 상관없이 뽑는 경우의 수
nCm = nPm / m!
이 때 재귀를 활용해서 구현할 수 있다.
nCm = n-1Cm-1 + n-1Cm
(어떤 요소 el를 포함하고 나머지 n - 1개 중에서 m - 1개를 뽑을 경우) + (어떤 요소 el를 포함시키지 않고, 나머지 n - 1개 중에서 m개를 뽑을 경우)
멱집합 : 주어진 집합의 모든 부분 집합
순열의 모든 가능한 조합을 만드는 경우
public static ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
// TODO:
//리턴할 어레이리스트
ArrayList<Integer[]> ret = new ArrayList<>();
//문제 조건에 의해 stuffArr에서 "000"을 포함하지 않는 stuff들을 담아줄 stuffs를 선언했다.
int[] stuffs = new int[0];
for (int i = 0; i < stuffArr.length; i++) {
if (!Integer.toString(stuffArr[i]).contains("000")) {
stuffs = Arrays.copyOf(stuffs, stuffs.length + 1);
stuffs[stuffs.length - 1] = stuffArr[i];
}
}
//stuffs로 choiceNum개를 뽑을 수 없는 경우
if (stuffs.length < choiceNum) return null;
//문제 조건을 위해 stuffs를 정렬해줬다
Arrays.sort(stuffs);
//stuffs의 요소들이 사용되었는지 체크해줄 boolean 배열
boolean[] used = new boolean[stuffs.length];
return makeRecipe(ret, stuffs, used, choiceNum, new Integer[]{});
}
private static ArrayList<Integer[]> makeRecipe(ArrayList<Integer[]> ret, int[] stuffs, boolean[] used, int choiceNum, Integer[] recipe) {
//탈출 조건
//stuff를 recipe에 하나씩 넣을 때마다 choiceNum을 빼준다.
//choiceNum이 0이 되면 recipe는 완성
//완성된 recipe를 ret에 넣어준다
if (choiceNum == 0) {
ret.add(recipe);
return ret;
}
//반복문을 돌리며 recipe를 채워준다.
//i번째 stuff가 사용되었다면(used[i]가 true라면 고려하지 않고 패스하고
//사용되지 않은 경우라면 choiceNum을 하나 감소시켜 더 깊은 단계의 recipe를 완성한다.
//makeRecipe메서드 호출 후 빠져나온 경우는 이제 i번째 stuff가 사용된 경우를 빠져나온 이후이므로 다시 used[i]를 false로 초기화해준다.
for (int i = 0; i < stuffs.length; i++) {
if (used[i]) continue;
Integer[] nextRecipe = Arrays.copyOf(recipe, recipe.length + 1);
nextRecipe[nextRecipe.length - 1] = stuffs[i];
used[i] = true;
ret = makeRecipe(ret, stuffs, used, choiceNum - 1, nextRecipe);
used[i] = false;
}
return ret;
}멱집합 구하는 문제
null을 포함한 모든 부분집합을 정렬해야한다.
public static ArrayList<String[]> missHouseMeal(String[] sideDishes) {
// TODO:
//return 할 어레이리스트 ret 선언
ArrayList<String[]> ret = new ArrayList<>();
Arrays.sort(sideDishes);
//choice메서드를 호출해서 ret에 모든 부분집합을 추가해준다.
choice(sideDishes, ret, new String[0], -1);
//ret 정렬
ret.sort((a,b) -> Arrays.toString(a).compareTo(Arrays.toString(b)));
return ret;
}
private static void choice(String[] sideDishes, ArrayList<String[]> ret, String[] chosenDishes, int idx) {
//탈출 조건
//idx를 하나씩 늘려주다가 idx가 될 수 있는 최대값을 넘는 순간 여태 완성한 chosenDishes 배열을 ret에 추가해주고 탈출한다.
if (idx == sideDishes.length - 1) {
ret.add(chosenDishes);
return ;
}
//choice 메서드를 한 번 진행할 때마다 해당 idx번째의 sideDishes를 포함하는 경우, 포함하지 않는 경우를 분기시킨다.
//포함하지 않는 경우
choice(sideDishes, ret, chosenDishes, idx + 1);
String[] newChosenDishes = Arrays.copyOf(chosenDishes, chosenDishes.length + 1);
newChosenDishes[newChosenDishes.length - 1] = sideDishes[idx + 1];
//포함하는 경우
choice(sideDishes, ret, newChosenDishes, idx + 1);
}정규표현식
java.util.regex 패키지의 클래스들을 사용한다.
클래스는 Pattern과 Matcher가 있다.
Pattern에서 지원하는 정규표현식
[abc] : a, b, or c
[^abc] : ^는 except. except a, b, or c
[a-zA-Z] : a ~ z, A ~ Z inclusive
[a-z&&[^b-d]] : a, e ~ z. 즉, bcd를 제외한 a-z
^ : 시작
$ : 끝
. : 임의의 한 문자
- : 문자가 0번 이상 발생
- : 문자가 1번 이상 발생
? : 문자가 0번 혹은 1번 발생
[] : 문자의 집합 범위
{} : 횟수 혹은 범위
() : 소괄호 안의 문자를 하나의 문자로 인식
| : or
\d : 숫자. ==[0-9]
\D : 숫자를 제외한 문자
\w : 알파벳이나 숫자
\W : 알파벳이나 숫자를 제외한 문자
\s : 공백문자
\S : 공백문자를 제외한 문자
https://regex101.com/
정규표현식 테스트 사이트
다른 사람들이 작성해놓은 것도 참고할 수 있다.
int로 된 배열이 주어지고 배열의 요소 두 개를 더하여 target을 만들 수 있는 경우를 리턴하라
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == target) return new int[]{arr[i], arr[j]};
}
}
return null;문제가 주어졌을 때 별 고민없이 완성한 코드.
별 문제는 없긴 하다.
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(target - arr[i])) return new int[]{target - arr[i], arr[i]};
else {
map.put(arr[i], 0);
}
}
return null;오늘 강사 분께서 보여주신 방법.
시간 복잡도도 O(n^2)에서 O(n)으로 확 줄었다.
확실히 내가 코드를 별 생각없이 작성하긴 해.
그리디 프로그래밍? 그거 설명 듣자마자 어? 이거 걍 난데 생각들었으니까...
음... 문제 풀린다고 안주하지 말고 고민하자.
leetcode 풀면서 느낀게 easy까지는 쉽고 medium도 문제 풀리기는 하는데 항상 메모리 부족, 시간 부족이 문제니까.
