🔎 개념
소수 판별 ( 에라토스테네스의 체)
- 인덱스 숫자가 소수인지 판별하는 함수
public void isPrime() {
// true로 초기화
for (int i = 2; i <= 3000; i++) {
sieve[i] = true;
}
for (int i = 2; i <= (int) Math.sqrt(3000); i++) {
for (int j = i * i; j <= 3000; j += i) { // i*i 미만은 이미 소수판단이 되었음
sieve[j] = false;
}
}
}
- 소수로만 이루어진 ArrayList
List<Integer> sieve = new ArrayList<Integer>();
int num =1000;
int err=0;
for(int i=2;i<num;i++){
for(int j=2;j<i;j++){
if(i%j==0){ err++;break; }
}
if ( !err ) {
sieve.add(i);
}else{
err=0;
}
}
조합 구현 (dfs) : 배열에서 특정 원소 3개를 더한값 구하기
public void dfs(int[] arr, int depth, int start, int sum) {
if (depth == 3) {
if (sieve[sum])
answer++;
return;
}
for (int i = start; i < arr.length; i++) {
dfs(arr, depth + 1, i + 1, sum + arr[i]);
}
}
배열에서 특정 값이 있는 지 확인
Arrays.asList(리스트).contains(값)
HashMap
HashMap<Integer,String> map = new HashMap<>(); // 선언
map.put(1,"사과"); // 값 추가
map.put(2,"바나나");
map.get(1); // key값 1의 value얻기
map.put(1,map.getOrDefault(1,0)+1);
// map.get(key) 에 값이 있다면 map.get(key)+1, 값이 없었다면 디폴트로 0 +1
// 해시맵값을 수정하고 싶을 경우
map.put(1, map.get(1)-1);
map.containKey(1); // key중에 1이 있는지 bool 반환
map.remove(1); // key값으로 1인 요소 제거
map.clear(); // 모든 요소 제거
//for문
for (String key : map.keySet()) {}
배열 특정 부분 자르기
//인덱스 start부터 end 까지만 남긴다면
int[] arr = Arrays.copyOfRange(array,start-1,end);
배열의 오름차순/내림차순 정렬
int arr[] = {4, 33, 24, 15, 17, 21};
Arrays.sort(arr); // 배열 오름차순 정렬
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순 정렬
Arrays.sort(arr, 0, 4); // 인덱스 0부터 4까지 부분정렬
배열 내 최댓값 찾기
int max=Arrays.stream(answer).max().getAsInt();
📚 소수 만들기 - DFS
class java0703_6 {
public int answer = 0; // 클래스 내의 어느 함수에서도 접근가능하도록
public boolean[] sieve; // 주의)
//여기서 = new boolean[n] 하면 안됨 main에서 해야함
public int solution(int[] nums) {
sieve = new boolean[3001];
// 각 원소의 최댓값이 1000, 근데 3개 조합이기에 3000까지 소수 판별 해놔야 함
isPrime(); // sieve 인덱스 숫자의 소수 여부 판별
dfs(nums, 0, 0, 0);
// 조합한 뒤 그 수의 인덱스가 소수이면 answer에 1증가
return answer;
}
public void isPrime() {
// true로 초기화
for (int i = 2; i <= 3000; i++) {
sieve[i] = true;
}
for (int i = 2; i <= (int) Math.sqrt(3000); i++) {
for (int j = i * i; j <= 3000; j += i) {
// i*i 미만은 이미 소수판단이 되었음
sieve[j] = false;
}
}
}
public void dfs(int[] arr, int depth, int start, int sum) {
if (depth == 3) {
if (sieve[sum])
answer++;
return;
}
for (int i = start; i < arr.length; i++) {
dfs(arr, depth + 1, i + 1, sum + arr[i]);
}
}
}
📚 완주하지 못한 선수 - Hash
import java.util.HashMap;
public class java0704_1 {
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap<String,Integer> map = new HashMap<>();
// 초기화
for(String c: participant)
map.put(c,map.getOrDefault(c, 0)+1);
// map.get(c) 에 값이 있다면 기존값, 값이 없었다면 디폴트로 0
for(String c: completion) {
map.put(c, map.get(c)-1);
}
for(String key:map.keySet()) {
if(map.get(key)>0)
answer=key;
}
return answer;
}
📚 K번째 수
import java.util.Arrays;
public class java0704_2 {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int i=0; i<commands.length;i++) {
int[] arr = Arrays.copyOfRange(array,commands[i][0]-1,commands[i][1]);
// 인덱스 commands[i][0]부터 commands[i][1] 까지만 남기기
Arrays.sort(arr); // 배열 오름차순 정렬
answer[i] = arr[commands[i][2]-1]; // 이런식으로 추가하는게..?
}
return answer;
}
}
📚 모의고사
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class java0704_3 {
public List<Integer> solution(int[] answers) {
int[] answer = {0,0,0};
int[] stu1 = {1,2,3,4,5};
int[] stu2 = {2,1,2,3,2,4,2,5};
int[] stu3 = {3,3,1,1,2,2,4,4,5,5};
for(int i=0;i<answers.length;i++) {
if(answers[i]==stu1[i%stu1.length]) answer[0]+=1;
if(answers[i]==stu2[i%stu2.length]) answer[1]+=1;
if(answers[i]==stu3[i%stu3.length]) answer[2]+=1;
}
int max=Arrays.stream(answer).max().getAsInt(); // 배열 내 최댓값 찾기
List<Integer> ans = new ArrayList<Integer>();
for(int i=0;i<answer.length;i++) {
if(answer[i]==max) ans.add(i+1); // 순서가 1부터 시작
}
return ans;
}
}
