유형
1.선택정렬
//문제
선택 정렬 알고리즘 방식으로 문제 풀이.
//입력
6
13 5 11 7 23 15
//출력
5 7 11 13 15 23public class ex1 {
public static int[] solution(int n,int[] arr){
int[] answer = new int[n];
for(int i=0; i<arr.length; i++){
for(int j=i+1; j<arr.length; j++){
if(arr[i]>arr[j]){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
public static void main(String[] args) throws IOException {
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
for(int x: solution(n,arr)){
System.out.print(x+" ");
}
}
}풀이
2중 for문으로 배열의 요소 하나하나를 비교해가면서 최댓값 알고리즘 적용.
2.버블정렬
//문제
버블 정렬 알고리즘 방식으로 문제 풀이.
//입력
6
13 5 11 7 23 15
//출력
5 7 11 13 15 23public class ex2 {
public static int[] solution(int n,int[] arr){
int[] answer = new int[n];
for(int i=0; i <arr.length ; i++) { //i=라운드 횟수
for(int j=0; j <arr.length-1-i; j++) {
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1] =temp;
}
}
}
return arr;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
for(int x: solution(n,arr)){
System.out.print(x+" ");
}
}
}
풀이
1.i는 라운드 횟수이다.
2.j와j+1을 비교하면서 i가 증가할때마다 최댓값이 젤뒤로 가니까 -i를 해준다. j+1과 비교하기 때문에 -1도 해준다.
3.삽입정렬
//문제
삽입 정렬 알고리즘 방식으로 문제 풀이.
//입력
6
11 7 5 6 10 9
//출력
5 6 7 9 10 11public class ex3 {
public static int[] solution(int n,int[] arr){
for(int i=1; i<n; i++){
int tmp=arr[i]; int j;
for(j=i-1; j>=0; j--){
//한칸씩 오른쪽으로 민다.
if(arr[j]>tmp) arr[j+1]=arr[j];
else break;
}
//for문이 멈춘 j의 바로 뒤에 tmp값 삽입.
arr[j+1]=tmp;
}
return arr;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
for(int x: solution(n,arr)){
System.out.print(x+" ");
}
}
}풀이
arr[i]를 tmp라는 변수로 두고, j를 i-1지점에서 부터 0까지 줄어들면서 arr[j] > tmp 이면 arr[j+1] = arr[j]로 둔다. 그리고 tmp가 더 크면 break걸고 그 arr[j]의 한칸 뒤인 arr[j-1]에 tmp를 넣어놓는다.
4.LRU (캐시,카카오 변형)
//문제
n크기 만큼의 메모리가 생성되고 , k만큼의 작업이 주어진다.
메모리에 남아있는 작업을 출력하라.
//입력
5 9
1 2 3 2 6 2 3 5 7
//출력
7 5 3 2 61.스택을 이용한 풀이
public class ex4 {
public static int[] solution(int n, int k, int[] arr){
Stack<Integer> stack = new Stack<>();
int[] array = new int[n];
for(int x: arr){
if(stack.contains(x)){
stack.remove(stack.indexOf(x));
stack.push(x);
}
else{
stack.push(x);
if (stack.size() > n) {
stack.remove(0);
}
}
}
for(int i=0; i<n; i++){
array[i] = stack.pop();
}
return array;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[k];
for(int i=0; i<k; i++){
arr[i] = sc.nextInt();
}
for(int x : solution(n,k,arr)) System.out.print(x + " ");
}
}풀이
1.해당하는 작업이 stack에 있으면 .indexOf()를 이용해서 스택에서 빼고 stack에 다시 push한다.
2.해당하는 작업이 stack에 없으면 그냥 push하는데 stack.size가 입력받은 n보다 커지게 되면 stack의 젤 안에있는 0번 인덱스를 remove한다.
[ 주요 기능 ]
stack.contains()
stack.indexOf(x) : 스택의 x의 index 반환
stack.remove(x) : 해당 요소 제거
2.정렬을 이용한 풀이
public class ex4_2 {
public static int[] solution(int n, int k, int[] arr){
int[] array = new int[n];
for(int x: arr){
//미스
int pos=0;
//히트
for(int i=0; i<n; i++) {
if(x==array[i]) pos=i; //히트면 pos인덱스가 바뀜
}
//미스
if(pos==0){
for(int i=n-1; i>=1; i--){
array[i] = array[i-1];
}
array[0]=x;
}
//히트
else{
for(int i=pos; i>=1; i--){
array[i]=array[i-1];
}
array[0]=x;
}
}
return array;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[k];
for(int i=0; i<k; i++){
arr[i] = sc.nextInt();
}
for(int x : solution(n,k,arr)) System.out.print(x + " ");
}
}1.해당 배열에 값이 있는경우 , 없는경우로 나눈다. pos라는 변수 선언.
2.값이 있는 경우 pos=i로 해당하는 인덱스 위치로 바꾼다.
3.값이 없는 경우(pos==0)에는 그냥 for문으로 array[i]=arr[i-1]로 array[1]의 위치까지 i-- 하면서 앞의 값을 복사한다. 그리고 array[0]에 해당 작업을 삽입한다.
4.값이 있는 경우(pos!=0)이 아닐 때 pos인덱스 부터 1까지를 복사한다.
그리고 array[0]에 해당 작업을 삽입한다.
5.중복 확인
//문제
하나라도 중복되는 수가 있으면 D를 출력, 없으면 U를 출력.
//입력
8
20 25 52 30 39 33 43 33
//출력
Dpublic class ex5 {
public static String solution(int n,int[] arr){
String answer = "U";
for(int i=0; i<arr.length; i++){
for(int j=i+1; j<arr.length; j++){
if(arr[i]==arr[j]) return "D";
}
}
return answer;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
System.out.println(solution(n,arr));
}
}풀이
1.2중 for문으로 다 돌면서 겹치는 경우를 검사한다.
6.장난 꾸러기
//문제
키 오름차순으로 번호를 지정한다. 서로 바껴있는 위치의 두명의 번호를 출력하라.
//입력
9
120 125 152 130 135 135 143 127 160
//출력
3 8public class ex6 {
public static ArrayList<Integer> solution(int n,int[] arr){
ArrayList<Integer> answer = new ArrayList<>();
int[] tmp=arr.clone();
Arrays.sort(tmp);
for(int i=0; i<n; i++){
if(arr[i]!=tmp[i]) answer.add(i+1);
}
return answer;
}
public static void main(String[] args){
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i]=kb.nextInt();
}
for(int x: solution(n,arr)){
System.out.print(x + " ");
}
}
}풀이
1.입력받은 배열을 .clone()을 이용해서 복사한다.
2.복사한 배열을 sort한다.
3.for문을 이용해서 값이 다른 위치를 answer.add(i+1)한다.
[ 주요 기능 ]
.clone() : 배열 복제
7.💥 좌표 정렬 (잘 모르겠음)
//문제
N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬
//입력
5
2 7
1 3
1 2
2 5
3 6
//출력
1 2
1 3
2 5
2 7
3 6class Point implements Comparable<Point>{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
@Override
public int compareTo(Point o){
if(this.x==o.x) return this.y-o.y;
else return this.x-o.x;
}
}
class ex7 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
ArrayList<Point> arr=new ArrayList<>();
for(int i=0; i<n; i++){
int x=sc.nextInt();
int y=sc.nextInt();
arr.add(new Point(x,y));
}
Collections.sort(arr);
for(Point o : arr) System.out.println(o.x + " " + o.y);
}
}풀이
1.x,y값을 담을 수 있는 Point클래스 생성.
2.Comparable을 상속받아서 sort에 기준을 정의할 수 있다.
3.@Override해서 compareTo 메서드 호출.
4.비교대상인 Point o를 파라미터로 넣어서 두 수를 비교한다.5.this객체에 o객체를 빼면 오름차순이다. 기본 sort인데, 여기에 x가 같을 경우 y로 정렬하는 기준을 넣는다.
[ 주요 기능 ]
x,y값을 받을 수 있는 Point 객체 생성 후 Comparable 상속 받기
오버라이드해서 메서드를 받아서 sort에 if(this.x==o.x) 조건 추가.
8.이분검색
//문제
//입력
8 32
23 87 65 12 57 32 99 81
//출력
3public class ex8 {
public static int solution(int n,int k, int[] arr){
int answer =0;
Arrays.sort(arr);
int lt=0,rt=0;
while(lt<=rt){
int mid=(lt+rt)/2;
if(arr[mid] == k){
answer = mid + 1;
}
if(arr[mid] > k) rt=mid-1;
else lt=mid+1;
}
return answer;
}
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];
for(int i=0; i<n; i++){
arr[i]=sc.nextInt();
}
System.out.println(solution(n,k,arr));
}
}풀이
흔히 아는 선택정렬방식으로 하면 쉽게 풀수있지만, 시간복잡도를 조금이라도 더 줄이기 위해서 선택정렬방식을 사용한다. lt,rt를 선언해서 mid를 찾고 해당하는 값과 비교하면서 mid를 좁혀나가는 방식.
[ 선택정렬의 조건 ]
1.무조건 오름차순 정렬이 되어야한다.
2.값이 무조건 기준으로하는 lt,rt 내에 있어야 한다.
9.뮤직 비디오(결정 알고리즘)
//문제
곡은 무조건 연달아 저장해야한다. 입력되는 k개의 DVD는 모두 같은 크기여야한다.
k개의 DVD를 사용해서 곡을 저장할 때 사용되는 최소 크기.
//입력
9 3
1 2 3 4 5 6 7 8 9
//출력
17public class ex9 {
public static int solution(int n,int k, int[] arr){
int answer =0;
int lt=arr[n-1]; int rt=0;
for(int i=0; i<n; i++) rt += arr[i];
while(lt<=rt){
int mid=(lt+rt)/2;
if(count(arr,mid) <= k){
answer=mid;
rt=mid-1;
}
else lt=mid+1;
}
return answer;
}
public static int count(int[] arr,int mid){
int cnt=1, sum=0;
for(int x : arr){
if(sum+x > mid){
cnt++;
sum=x;
}
else sum+=x;
}
return cnt;
}
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];
for(int i=0; i<n; i++){
arr[i]=sc.nextInt();
}
System.out.println(solution(n,k,arr));
}
}풀이
1.문제를 보고 이분검색이라는 것을 파악해야한다. 이분 검색-> 이 문제에서의 mid값은 DVD한장의 용량을 뜻한다. 9~45까지의 lt,rt에서 mid값을 이용해 DVD를 구성하는 최소크기를 구해야한다.
2.count함수를 만들어서 현재 mid의 저장공간을 가질 때 DVD의 갯수를 구한다.이 때 DVD가 2개가 리턴이되도 이 2개로 된다면, 같은크기고 3개로도 된다는뜻이다.
문제에서 요구하는 값이 오름차순 정렬되어있는 lt~rt사이에 있으면 무조건 결정알고리즘!!!!!!!!!
9.마구간 구하기(결정 알고리즘)
//문제
x좌표가 주어지고 말의 마리수가 주어지면 두 말사이의 거리의 최대 거리를 구하라.
//입력
5 3
1 2 8 4 9
//출력
3public class ex10 {
public static int solution(int n,int k, int[] arr){
int answer =0;
Arrays.sort(arr);
int lt=1;
int rt=arr[n-1];
while(lt<=rt){
int mid=(lt+rt)/2;
if(count(arr,mid) >= k){
answer=mid;
lt=mid+1; //거리의 최댓값을 찾아야하기 때문에 더 큰값으로 간다.
}
else rt=mid-1;
}
return answer;
}
public static int count(int[] arr,int mid){
int cnt=1;
int ep=arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i]-ep>=mid){
cnt++;
ep=arr[i];
}
}
return cnt;
}
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];
for(int i=0; i<n; i++){
arr[i]=sc.nextInt();
}
System.out.println(solution(n,k,arr));
}
}풀이
1.배열을 우선 정렬하고, lt,rt를 선언하고 이분검색 알고리즘 형태로 식 작성한다.
2.말의 마리 수를 count함수를 작성한다. mid(=거리)보다 큰 차이나게 뒀을 때 말의 마리수가 입력되는 k값과 일치하는지 아닌지 판단해서 rt,lt값을 조절하고 값을 정한다.
[ 주요 기능 ]
이분검색,결정 알고리즘
