[리뷰] 해결 못한 알고리즘 다시 풀기 -4

1. 캐시 알고리즘

(1) 배열 이용

import java.util.Scanner;

public class Main {
	static int[] solution(int n, int[] arr) {
 		int[] answer = new int[n];
		// 캐시 히트, 캐시 미스 -> 위치를 -1로 지정후, pos으로 히트 유무 확인
		int pos = 0;
		for (int i = 0; i < arr.length; i++) {
			pos = -1;
			for (int j = 0; j < n; j++) {
				if (answer[j] == arr[i]) {
					pos = j;
					break;
				}
			}
			if (pos == -1) {
				for (int j = n-1; j > 0; j--) {
					answer[j]=answer[j-1];
				}
			} else {
				for (int j = pos; j > 0; j--) {
					answer[j]=answer[j-1];
				}
			}
			answer[0]=arr[i];
		}

		return answer;

	}

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[m];
		for (int i = 0; i < m; i++) {
			arr[i] = kb.nextInt();
		}

		for (int x : solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

(2) ArrayList 이용

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> list = new ArrayList<>();
		int pos = 0, i;

		// 길이는 5고정
		for (int x : arr) {
			pos = -1;
			for (i = 0; i <list.size(); i++) {
				if (list.get(i) == x) {
					pos = i;
				}
			}

			if (pos == -1) {
				list.add(0,x);
			} else {
				list.remove(pos);
				list.add(0, x);
			}
		}

		while (list.size() != n) {
			for (int z = n; z < list.size(); z++) {
				list.remove(z);
			}
		}

		return list;
	}

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[m];
		for (int i = 0; i < m; i++) {
			arr[i] = kb.nextInt();
		}

		for (int x : solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

2. 이분 탐색

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int solution(int n, int m, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 0;
		int rt = arr.length;
		int mid = 0;
		Arrays.sort(arr);

		while (mid != m) {
			mid = (lt + rt) / 2;
			if (arr[mid] == m)
				return answer = mid+1;
			
			else {
				if (arr[mid] > m) {
					rt = mid - 1;
				} else if (arr[mid] < m) {
					lt = mid + 1;
				}
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		System.out.println(solution(n, m, arr));
	}

}

 

3. 뮤직비디오 - 결정알고리즘

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public int count(int[] arr, int capacity) {
		// DVD장수와 DVD에 담는 곡들의 합 변수 선언
		int cnt = 1, sum = 0;
		for (int x : arr) {
			if (sum + x > capacity) {
				cnt++;
				sum = x;
			} else
				sum += x;
		}
		return cnt;

	}

	public int solution(int n, int m, int[] arr) {
		// 최소 용량 크기 결정
		// lt=0, rt=총합

		int answer = 0;
		int lt = Arrays.stream(arr).max().getAsInt();
		int rt = Arrays.stream(arr).sum();

		int mid = (lt + rt) / 2;

		// 종료 조건 -> lt는 항상 증가 rt는 감소 -> 범위를 줄인다.
		while (lt <= rt) {
			mid = (lt + rt) / 2;
			if (count(arr, mid) <= m) {
				answer = mid;
				rt = mid - 1;
				
			} else
				lt = mid + 1;

				

		}

		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();

		System.out.println(T.solution(n, m, arr));
	}
}

 

4. 마구간정하기 - 결정알고리즘

package sortsearch.ch06_2;

import java.util.Arrays;
import java.util.Scanner;

public class Sortsearch10_2 {
	public int count(int[] arr, int site) {
		int cnt=1;
		int ep=arr[0];
		for(int i=1;i<arr.length;i++) {
			if(arr[i]-ep<site) {
				cnt++;
				ep=arr[i];				
			}
		}
		
		return cnt;
	}
	public int solution(int m, int[]arr) {
		int answer=0;
		int lt=1;
		int rt=Arrays.stream(arr).max().getAsInt()-Arrays.stream(arr).min().getAsInt();
		
		while(lt<=rt) {
			int mid=(lt+rt)/2;
			if(count(arr, mid)>=m) {
				answer=mid;
				rt=mid-1;
			}
			else
				lt=mid+1;
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Sortsearch10_2 T = new Sortsearch10_2();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(T.solution(m,arr));
	}

}

 

1. for문을 이용한 최댓값과 sum 찾기

for(int i=0;i<n;i++) {
	lt=Math.max(lt, arr[i]);
}
for(int i=0;i<n;i++) {
	rt+=arr[i];
}

2. Arrays.stream을 이용한 최댓값과 sum찾기

int lt=Arrays.stream(arr).max().getAsint();
int rt=Arrays.stream(arr).max().sum();

arr에서의 반복자 [포인터 Iterator 개념 / Reduction 함수]

-> stream 메서드의 max()메서드는 리턴값이 int형이 아니므로, getAsint()를 이용해 int형으로 변환

-> 필터를 이용해 sum의 조건을 줄수도 있다.