이코테 0714 - 정렬, 이분탐색, DP

🔎 개념

배열 출력하기

그냥 System.out.print(arr)하면

[I@762efe5d

와 같이 메모리 주소가 출력됨 따라서 문자열로 변환해 출력하기

System.out.print(Arrays.toString(arr)); 

Integer 와 int의 차이

아래와 같이 배열의 내림차순 정렬시 Collections.reverseOrder() 메서드가 필요한데, 이때 int[] 배열이 아닌 Integer[] 배열이 요구된다.

Arrays.sort(arr2,Collections.reverseOrder());

---

📚 위에서 아래로 - 정렬

import java.util.*;

public class Java0714_2 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		Integer[] arr = new Integer[n];
		for(int i=0;i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr,Collections.reverseOrder());
		// 내림차순 정렬
		
		for(int i:arr) System.out.print(arr[i]+ " ");		
	}
	

}

📚 성적이 낮은 순으로 학생 출력하기 - 정렬

// <String, Integer>로 묶어 이차원 어레이리스트를 생성해 정렬하기 보다
// class를 만들어 동시에 값을 할당하고 접근하기 쉽도록 함!

package ThisIsCodingTest;

import java.util.*;

class Students implements Comparable<Students>{

	private String name;
	private int score;
	
	public Students(String name, int score) {
		this.name = name;
		this.score = score;
	}

	@Override
	public int compareTo(Students o) {
		if(this.score < o.score) return -1; // 오름차순 정렬
		return 1;
	}

	public String getName() {
		return this.name;
	}

}

public class Java0714_1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		// '홍길동 96' 을 입력받아 각각 이름,점수로 할당
		List<Students> students = new ArrayList<>();
		for (int i=0; i< n; i++) {
			String name = sc.next();
			int score = sc.nextInt();
			
			students.add(new Students(name,score));
		}
		
		Collections.sort(students);
		
		for(int i=0;i<students.size();i++) System.out.print(students.get(i).getName() + " ");
	}
}
// 결과 : 이순신 홍길동

📚 두 배열의 원소 교체 - 정렬

import java.util.*;

public class Java0714_3 {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		Integer[] arr1 = new Integer[n];
		Integer[] arr2 = new Integer[n]; 
		// Collections.reverseOrder 함수를 적용하기 위해 Wrapper 객체로 생성
		
		for(int i=0;i<n;i++) {
			arr1[i] = sc.nextInt();
		}
		for(int i=0;i<n;i++) {
			arr2[i] = sc.nextInt();
		}
		
		Arrays.sort(arr1);
		Arrays.sort(arr2,Collections.reverseOrder());
		
		for(int i=0;i<n;i++) {
			if(k>0&&arr1[i]<arr2[i]) {

				int temp=arr1[i];
				arr1[i] = arr2[i];
				arr2[i] = temp;
				
				k--;
			}
			else break;
		}
		
		int sum=0;
		for(int i:arr1) sum+=i;
		
		System.out.println(sum);
		//System.out.print(Arrays.toString(arr1)); // 배열 출력
	}

}

📚 재귀로 구현한 이진탐색 - 이진탐색

import java.util.Scanner;

public class Java0714_4 {
	public static void main(String[] args) {
		
		Scanner sc  = new Scanner(System.in);
		int n = sc.nextInt();
		int target = sc.nextInt();
		
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		
		int answer = binarySearch(arr,target,0,n-1);
		if(answer ==-1 )
			System.out.print("None");
		else
			System.out.print(answer+1);
	}

	public static int binarySearch(int[] arr, int target, int startIdx, int endIdx) {
		
		if(startIdx>endIdx) return -1;
		int mid = (startIdx+endIdx)/2;
		
		if(target>arr[mid])
			binarySearch(arr, target, mid+1, endIdx);
		if(target == arr[mid]) return mid;
		else
			binarySearch(arr, target, startIdx, mid-1);
		
		return -1;
	}
}

📚 부품 찾기 - 이진 탐색

방법1) 이진 탐색

public class Java0714_5 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		for(int i=0;i<n;i++) arr1[i] = sc.nextInt();
		
		Arrays.sort(arr1);
		// 이진 탐색을 위해 사전 정렬
		
		int m = sc.nextInt();
		int[] arr2 = new int[m];
		for(int i=0;i<m;i++) arr2[i] = sc.nextInt();
		
		for(int i:arr2) {
			if(binarySearch(arr1,i,0,n-1)==-1) System.out.print("no ");
			else System.out.print("yes ");
		}
	}

	public static int binarySearch(int[] arr,int target, int startIdx, int endIdx) {
		
        while (startIdx <= endIdx) {
            int mid = (startIdx + endIdx) / 2;
            
            if (arr[mid] == target) return mid;
            
            else if (arr[mid] > target) endIdx = mid - 1;
            
            else startIdx = mid + 1; 
        }
        return -1;
	}
}

방법2) 계수 정렬

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // N(가게의 부품 개수)
        int n = sc.nextInt();
        int[] arr = new int[1000001];
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            arr[x] = 1;
        }

        // M(손님이 확인 요청한 부품 개수)
        int m = sc.nextInt();
        int[] targets = new int[n];
        for (int i = 0; i < m; i++) {
            targets[i] = sc.nextInt();
        }

        // 손님이 확인 요청한 부품 번호를 하나씩 확인
        for (int i = 0; i < m; i++) {
            // 해당 부품이 존재하는지 확인
            if (arr[targets[i]] == 1) {
                System.out.print("yes ");
            }
            else {
                System.out.print("no ");
            }
        }
    }

}

방법3) HashSet 생성하여 contains() 활용

public class Main{
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		HashSet<Integer> set = new HashSet<>();
		for(int i=0; i<n;i++) {
			int x = sc.nextInt();
			set.add(x);
		}
		
        int m = sc.nextInt();
        int[] targets = new int[n];
        for (int i = 0; i < m; i++) {
            targets[i] = sc.nextInt();
        }
        
        for(int i:targets) {
        	if(set.contains(i)) System.out.print("no");
        	else System.out.print("yes");
        }
	}
}

📚 떡볶이 떡 만들기 - 이진 탐색

import java.util.*;

public class Java0714_6 {
	public static void main(String[] args) {
		
		int answer = 0;
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] arr = new int[n];
		for(int i=0;i<n;i++) arr[i] = sc.nextInt();
		
		int start = 0;
		
		Arrays.sort(arr);
		int end = arr[n-1];
		
		while (start<=end) {
			int mid = (start+end)/2;
			
			long sum=0; // 떡의 개수 n과 떡의 길이 m의 범위가 엄청 크기에
			for(int i:arr) {
				sum+= (i>mid)? i-mid:0;
			}
			
			if(sum>=m) { 
				start = mid+1;
				answer = mid;
			}
			else if(sum<m) end = mid-1;
		}
		
		System.out.print(answer);
	}
}

📚 피보나치 수열 - DP

보텀 업 : 반복문 이용

public class Java0714_7 {
	
	public static long[] d = new long[100];
	
	public static void main(String[] args) {
		
		d[1] = 1;
		d[2] = 2;
		int n = 50; // 50 번째 피보나치 수 계산
		
		for(int i=3; i<n;i++) d[i] = d[i-1]+d[i-2];
		
		System.out.print(d[n]);
	}
}

탑 다운 : 재귀함수 이용

public class Main{
	public static long[] d = new long[100];
	
	public static void main(String[] args) {
		
		System.out.print(fibo(50));
	}

	public static long fibo(int x) {
		
		if(x==1||x==2) return 1;
		
		// 이미 계산한 적 있다면 그대로 반환
		if(d[x] !=0) return d[x];
		
		d[x] = fibo(x-1) + fibo(x-2);
		return d[x];
	}
}

📚 1로 만들기 - DP

import java.util.*;

public class Java0714_8 {
	
	public static int[] d;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		d = new int[n+1];
		
		for(int i=2;i<=n;i++) {
			
			d[i] = d[i-1]+1; 
			
			if(d[i]%5==0) d[i] = Math.min(d[i], d[i/5]+1); 
			if(d[i]%3 ==0) d[i] = Math.min(d[i],d[i/3]+1);
			if(d[i]%2 ==0) d[i] = Math.min(d[i], d[i/2]+1);
			
		}
		
		System.out.print(d[n]);
	}
}

📚 개미 전사 - DP

import java.util.Scanner;

public class Java0714_9 {
	
	public static int[] d;
	public static int[] p;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		d = new int[n+1];
		p = new int[n+1];
		for(int i=1;i<=n;i++) p[i] = sc.nextInt();
		
		d[1] = p[1];
		d[2] = d[0] + p[2];
		for(int i=3;i<=n;i++) d[i] = Math.max(d[i-2]+p[i], d[i-3]+p[i]);
		
		System.out.print(d[n]);
	}
}

📚 바닥 공사 - DP

• 점화식 d[n]= 2*d[n-2]+d[n-1] (n개에서 타일을 채울수있는 방법의 수)
• n-2는 누워있는 타일2개 / n-1은 세워진 타일 하나를 뜻함
• 모든 경우의 수를 구하는 것이기에 21 ,22 타입으로 구성하는 경우 + 1*2 타입으로 구성하는 경우의 수 더해주기

import java.util.Scanner;

public class Java0714_10 {
	
	public static int[] d;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n=sc.nextInt();
		d = new int[n+1];
		
		d[1] = 1;
		d[2] = 3;
		for(int i=3;i<=n;i++) d[i] = (2*d[i-2]+d[i-1])%796796;
		
		System.out.print(d[n]);
	}
}

📚 효율적인 화폐구성 - DP

public class Java0714_11 {
	
	public static int[] d;
	public static int[] p;
	
	public static void main(String[] args) {
		
		Scanner sc= new Scanner(System.in);
		
		int n =sc.nextInt();
		int m = sc.nextInt();
		
		d = new int[m+1];
		p= new int[n]; // 화폐단위 배열
		
		for(int i=0;i<n;i++) {
			p[i] = sc.nextInt();
		}
		
		Arrays.fill(d, 10001); // 미리 초기화
		d[0] = 0;
		
		for(int i:p) { 
			for(int j=i;j<=m;j++) { 
				if(d[j-i]!=10001) d[j] = Math.min(d[j], d[j-i]+1);
				// d[2]=1,d[4]= 2,...
				// d[3] =1; d[6] =2 ...
				// d[5] = 2, d[7] = 3 ...
			}
			
		}
		
        
        if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
            System.out.println(-1);
        }
        else {
            System.out.println(d[m]);
        }
	}
}