Java 정렬, 이분검색과 결정알고리즘 2

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제 4 :

캐시메모리 사용 규칙이 LRU 알고리즘(Least Recently Used)을 따른다.

만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면,

(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)

 

1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번 작업은 캐시의 맨 앞에 위치한다.

5 2 3 1 6

(7번 작업은 캐시에서 삭제한다.)

 

2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면

Cache Hit가 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.

5 2 3 1 6  ---> 3 5 2 1 6

캐시의 크기가 주어지고, 캐시가 비어있는 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후

캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

 

입력설명 

첫 번째 줄에 캐시 크기인 S(3<=S<=10) , 작업의 개수 N(5<=N<=1,000) 입력된다.

두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~ 100 이다.

 

출력설명

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

 

입력예제

5 9

1 2 3 2 6 2 3 5 7

출력예제

7 5 3 2 6

 

 

풀이 :

해야할 작업이 캐시에 없는 경우 모든 작업 뒤로 미루고,

해야할 작업이 캐시에 있는 경우 해당 작업 맨 앞으로 가져오고

해당 작업이 있던 자리의 앞에 있던 작업들을 뒤로 한 칸씩 이동시킨다.

따라서 삽입 정렬을 이용하여 문제를 해결할 수 있다.

 

 

소스코드 :

import java.util.*;
class Main {
	public int[] solution(int s, int n, int[] arr) {
		int[] cache = new int[s];
		for(int i=0; i<n; i++) {
			// Cache Miss일 경우 pos는 그대로 -1 이다.
			int pos = -1;
			// Cache Hit일 경우 pos에 j가 저장된다.
			for(int j=s-1; j>=0; j--) {
				if (cache[j] == arr[i]) pos = j;
			}
			// Cache Miss일 경우(pos가 -1일 경우) 모든 작업을 뒤로 미룬다.
			if (pos == -1) {
				for(int j=s-1; j>=1; j--) {
					cache[j] = cache[j-1];
				}
			}
			// Cache Hit일 경우 해당 작업이 있던 자리(pos에 저장되어 있음)의
			// 앞에 있던 작업들을 뒤로 한 칸씩 이동시킨다
			else {
				for(int j=pos; j>=1; j--) {
					cache[j] = cache[j-1];
				}
			}
			// Cache Miss, Cache Hit 모두 마지막엔 맨 앞에 입력된 작업이 위치한다.
			cache[0] = arr[i];
		}
		return cache;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = sc.nextInt();
		for(int x : T.solution(s, n, arr)) System.out.print(x+" ");
	}
}

 

 

 

문제 5 :

첫 번째 줄에 자연수 n 주어지고, 두 번째 줄에 학생들이 적어낸 n개의 자연수가 주어진다.

중복된 숫자가 존재하면 D, 모두 다른 숫자면 U를 출력하는 프로그램을 사용하시오.

 

풀이 :

1번 방법 O(nlogn~) : n개의 자연수를 정렬시키고 앞 뒤와 같은 숫자가 있을 경우 D, 아니면 U를 출력한다.

2번 방법 O(n) : HashMap 이용해 같은 수가 2번 들어갈 경우 D 출력, 아니면 U 출력

소스코드는 간단하니 생략하겠다.

 

 

 

문제 6 :

키가 가장 작은 학생부터 일렬로 정렬되어있는데 두 학생이 자리를 바꾸었다.

첫 번째 줄에 자연수 n이 주어지고 두 번째 줄에 앞서 말한 두 학생이 자리를 바꾼 상태의 정렬된 수들이 주어진다.

자리를 바꾼 두 학생의 반 번호를 출력하시오.

입력예제

9

120 125 152 130 135 135 143 127 160

출력예제

3 8

 

풀이 :

두 번째 줄에 주어진 수들을 복사한 새로운 int 배열을 만들고

두 번째 줄에 주어진 수들의 배열과 비교해서 다른 곳의 인덱스+1을 출력한다.

소스코드는 간단하니 생략하겠다.

 

 

 

문제 7 :

n개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하시오.

정렬기준은 x값에 의해 정렬하고 x값이 같을 경우 y값에 의해 정렬한다.

입력예제

5

2 7

1 3

1 2

2 5

3 6

출력예제

1 2

1 3

2 5

2 7

3 6

 

풀이 :

Point 클래스와 Comparable 인터페이스를 이용해서 문제를 해결한다.

Point 클래스는 x좌표와 y좌표 두 개의 값을 가지는 클래스이다.

Comparable 인터페이스는 정렬 수행 시 기본적으로 적용되는 정렬 기준이 되는 메소드를 정의하는 인터페이스이다.

( 참고자료 : https://st-lab.tistory.com/243 )

( Comparable 인터페이스의 자세한 정보는 위의 링크에서 찾아보면 좋다! )

 

인터페이스이기 때문에 사용하기 위해서 인터페이스 내에 선언된 메소드를 반드시 구현해야 한다.

Comparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언되어 있다.

Comparable을 사용하고자 한다면 compareTo 메소드를 재정의(Override/구현)을 해주어야 한다는 것이다.

 

Comparable 인터페이스를 사용하는 이유는

만약 두 객체가 주어질 경우 사용자가 기준을 정해주지 않으면

어떤 객체가 더 높은 우선순위를 가지는지 판단할 수 없기 때문이다.

Comparable 인터페이스는 이를 해결해준다. 기준을 정해주는 것이다.

Comparable은 자기 자신과 매개변수 객체를 비교한다.

 

compareTo는 현재 멤버 변수의 값이 파라미터로 넘어온 값보다

작으면 음수를 리턴, 같으면 0을 리턴, 크면 양수를 리턴하도록 작성하면 된다.

즉, 파라미터로 넘어온 값이 현재 멤버 변수 값보다 크면(오름차순) 음수를 리턴하면 된다.

 

소스코드 :

import java.util.*;
// Point라는 클래스의 객체를 정렬한다.
class Point implements Comparable<Point> {
	public int x, y;
	// 객체의 생성과 동시에 인스턴스 변수를 원하는 값으로 초기화할 수 있는 생성자
	Point(int x, int y) {
		this.x=x;
		this.y=y;
	}
	// 필수 구현 부분
	@Override
	public int compareTo(Point point) { // Point 객체를 받는다.
		// this -> point (point가 매개변수로 넘어온 객체)
		// 오름차순으로 this point 순서대로 있게하려면 음수가 리턴되어야 한다. (ex 10 20)
		if (this.x == point.x) return this.y - point.y;
		else return this.x-point.x;
	}
}

class Main {
	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 p : arr) {
			System.out.println(p.x+" "+p.y);
		}
	}
}