![[코드트리 조별과제] 5주차 (재귀함수, 정렬)](https://cdn.hashnode.com/res/hashnode/image/upload/v1723975719482/0772b7b9-a344-4adf-a59b-a422e606317f.png?w=1600&h=840&fit=crop&crop=entropy&auto=compress,format&format=webp)
Table of contents
[5주차 정리]
4주 차보다 많이 못 풀어서 아쉬웠던 5주 차.
후회 없는 6주 차가 되길 바라며 마지막까지 파이팅 하자.
[문제풀이]
[재귀함수] - 값을 반환하는 함수
- 재귀함수를 이용한 3n + 1 수열
import java.util.Scanner;
public class Main {
public static int oddEven (int n) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return oddEven(n / 2) + 1;
}else {
return oddEven(3 * n + 1) + 1;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(oddEven(n));
}
}
f(1)은 0이 되어야 하고 그 다음에 식이 하나씩 진행될때마다 1씩 더해주면 된다.
100으로 나눈 나머지의 수열
- 재귀함수로 푸는 수열은 규칙이 일정해서 재밌다.
import java.util.Scanner;
public class Main {
public static int divide100 (int n) {
if (n == 1) {
return 2;
}
if (n == 2) {
return 4;
}
return (divide100(n-1) * divide100(n-2)) % 100;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(divide100(n));
}
}
- 이상한 수열
import java.util.Scanner;
public class Main {
public static int sequence (int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return sequence(n / 3) + sequence (n - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print(sequence(n));
}
}
- 재귀함수를 이용한 최소공배수
import java.util.Scanner;
public class Main {
public static int [] arr = new int[10];
public static int gcd(int n, int m) {
int gcdNum = 0;
for (int i = 1; i <= Math.min(n, m) ; i++) {
if (n % i == 0 && m % i == 0){
gcdNum = i;
}
}
return gcdNum;
}
public static int lcm (int n) {
if (n == 1) {
return arr[0];
}
return (lcm(n-1) * arr[n-1]) / gcd(lcm(n-1),arr[n-1]);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.print(lcm(n));
}
}
[해설과 비교]
내가 푸는 방식과 비슷하지만 나는 최소공배수와 최대공약수를 구하는 함수를 따로 처리했고 최소공배수를 구하는 함수에서 재귀함수를 사용하고 있고 해설의 방식은 최소공배수를 구하는 함수만 따로 빼놓고 인덱스 값을 활용해 재귀함수를 활용하고 있다.
public static int lcm(int a, int b) {
int gcd = 1;
for(int i = 1; i <= Math.min(a, b); i++) {
if(a % i == 0 && b % i == 0)
gcd = i;
}
return a * b / gcd;
}
// index번째 까지 인덱스의 숫자 중에 가장 큰 값을 반환합니다.
public static int getLCMAll(int index) {
// 남은 원소가 1개라면 그 자신이 답이 됩니다.
if(index == 1)
return arr[1];
// 1번째 ~ index - 1번째 원소의 최소공배수를 구한 결과와
// 현재 index 원소의 최소공배수를 구하여 반환합니다.
return lcm(getLCMAll(index - 1), arr[index]);
}
[정렬] - 일반 정렬
- 오름차순 정렬
n개의 숫자가 주어졌을 때, 그 숫자들을 오름차순으로 정렬해보자.
Java에서는 배열 내 원소들을 오름차순으로 정렬하기 위해 Arrays.sort()라는 내장된 함수를 이용할 수 있다.
import java.util.Arrays;
Arrays.sort(arr) // 배열 전체 오름차순
Arrays.sort(arr, start, end) // arr start index부터 end - 1 까지 구간만 오름차순 정렬
Arrays.sort(arr)사용시
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{12, 41, 37, 81, 19, 25, 60, 20};
Arrays.sort(arr);
for(int i = 0; i < 8; i++) // 12, 19, 20, 25, 37, 41, 60, 81
System.out.print(arr[i] + " ");
}
}
Arrays.sort(arr, 시작 Index, 끝 Index + 1)사용시
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{12, 41, 37, 81, 19, 25, 60, 20};
Arrays.sort(arr, 2, 4); // index 2부터 3까지만 정렬
for(int i = 0; i < 8; i++) // 12, 41, 37, 81, 19, 25, 60, 20
System.out.print(arr[i] + " ");
}
}
- 내림차순 정렬
Java에서는 int (primitive tytpe)으로 구성된 배열을 한번에 내림차순 정렬할 수 있는 방법이 없다.
// Integer로 배열을 선언 후에
import java.util.Collections;
Collections.reverseOrder();
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Integer[] arr = new Integer[]{12, 41, 37, 81, 19, 25, 60, 20}; // Integer 배열
Arrays.sort(arr, Collections.reverseOrder());
for(int i = 0; i < 8; i++) // 81, 60, 41, 37, 25, 20, 19, 12 내림차순 정렬
System.out.print(arr[i] + " ");
}
}
Java8 버전부터는 Stream을 활용하여 int → Integer 변환 가능.
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{12, 41, 37, 81, 19, 25, 60, 20}; // int 배열
// Stream을 이용하여 int[]를 Integer[]로 편하게 변환
Integer[] arr2 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(arr2, Collections.reverseOrder());
for(int i = 0; i < 8; i++) // 81, 60, 41, 37, 25, 20, 19, 12
System.out.print(arr2[i] + " ");
}
}
- 오름 내림차순 정렬
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 오름차순 정렬
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
Integer[] arr2 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(arr2,Collections.reverseOrder()); // 내림차순 정렬
for (int num : arr2) {
System.out.print(num + " ");
}
}
}
- 문자열 정렬
문자열(String) 내의 문자들을 알파벳 순으로 정렬해보자.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char [] chars = str.toCharArray(); // 문자를 원소로 갖는 char[] 배열로 변환
Arrays.sort(chars); // 알파벳 순으로 정렬
String sortedStr = new String(chars); // 다시 배열을 문자열로 변환.
System.out.print(sortedStr);
}
}
- 문자열 리스트 정렬
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String [] strs = new String[n]; // 문자열 배열
for (int i = 0; i < n; i++) {
strs[i] = sc.next();
}
Arrays.sort(strs); // 사전순으로 앞선 단어부터 정렬
for (String str : strs) {
System.out.println(str);
}
}
}
- k번째 숫자 구하기
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int [] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
System.out.print(arr[k]);
}
}
- 두 개의 동일한 수열
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] arrOne = new int[n];
int [] arrTwo = new int[n];
for (int i = 0; i < n; i++) {
arrOne[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
arrTwo[i] = sc.nextInt();
}
Arrays.sort(arrOne);
Arrays.sort(arrTwo);
boolean result = true;
for (int i = 0; i < n; i++) {
if (arrOne[i] != arrTwo[i]) {
result = false;
}
}
if (result) {
System.out.print("Yes");
} else {
System.out.print("No");
}
}
}
- 2개씩 그룹짓기
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] arr = new int[2 * n];
for (int i = 0; i < 2*n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int groupMax = 0;
for(int i = 0; i < n; i++) {
int groupSum = arr[i] + arr[2*n - 1 - i];
if(groupSum > groupMax)
// 최댓값 갱신
groupMax = groupSum;
}
System.out.print(groupMax);
}
}
[해설과 비교]
M ≥ b , a ≥ m 으로 최댓값과 최솟값 (M,m)을 묶어주는 방식으로 모든 그룹을 만들었을 때 그룹의 합 최댓값이 최소가 된다. M + a ≥ m + b 이다. M+m 과 a+b를 하면 두 개의 값은 최댓값이 될 수 있다. 하지만 M+a의 값보다 작거나 같다. 최대값을 구한다면 M+a 한 값을 구하면 되겠지만 최댓값중 최솟값을 구하는 것이므로 [M,m], [a,b] 그룹을 구한다. 오름차순 정렬 후에 배열의 시작과 끝, 즉, arr[i] + arr[2*n - 1 - i] 를 사용해서 구한다.
- 순서를 바꾸었을 때 같은 단어인지 판별하기
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
char [] char1 = str1.toCharArray();
char [] char2 = str2.toCharArray();
Arrays.sort(char1);
Arrays.sort(char2);
String sortedStr1 = new String(char1);
String sortedStr2 = new String(char2);
if (sortedStr1.equals(sortedStr2)) {
System.out.print("Yes");
} else {
System.out.print("No");
}
}
}
- k번째로 신기한 문자열
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String pattern = sc.next();
String [] arr = new String[n];
String [] hasPattern = new String[n];
int idx = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.next();
}
for (int i = 0; i < n; i++) {
boolean result = true;
if (arr[i].length() >= pattern.length()) { // pattern의 길이가 더 길 수 없음
for (int j = 0; j < pattern.length(); j++) {
if (arr[i].charAt(j) != pattern.charAt(j)) {
result = false;
break;
}
}
if (result) {
hasPattern[idx++] = arr[i];
}
}
}
Arrays.sort(hasPattern,0,idx);
System.out.print(hasPattern[k-1]);
}
}
[해설과 비교]
같은 방식으로 구하지만 함수로 처리를 해서 더 간단하게 정리하였다.
// a가 b로 시작하는지를 확인합니다.
public static boolean startsWith(String a, String b) {
// b의 길이가 더 길 수는 없습니다.
if((int) a.length() < (int) b.length())
return false;
// b의 길이만큼 살펴보며, a와 문자열이 완벽히 동일한지 확인합니다.
for(int i = 0; i < (int) b.length(); i++)
if(a.charAt(i) != b.charAt(i))
return false;
// 전부 확인했는데도 오류가 없다면, prefix라 할 수 있습니다.
return true;
}
- 중앙값 계산 2
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
if (i % 2 != 0) {
Arrays.sort(arr,1,i+1); // 정렬 인덱스 체크하기
System.out.print(arr[i / 2 + 1] + " ");
}
}
}
}