[Java 기본 알고리즘] (2) 정렬 탐색

package Sorting_SearchingBasic;

public class Sorting_Searching1 {
	public static void main(String[] args) {
			
			//(1) 뒤에 0을 넣는 방법 -> 3,2,8,5,0,0
			
			//1. ds
			int[] nums= {0,3,2,0,8,5};
			
			//2. for
			//array를 앞으로 넘기기
			//Index를 구하기
			int n=nums.length; //6, 인덱스는 0부터 시작해서 -1를 해야한다.
			int index=0;
			
			//3,2,8,5
			for(int i=1; i<n; i++) {
				if(nums[i]!=0) {			//nums가 0이 아닐 떄
					nums[index]=nums[i]; 	//nums의 index에 nums의 i 넣기
					index++;				//nums가 0이 아닐 때 index에 i를 넣는다.
											//-> index++로 index는 0이 아닌 첫번째 순서가 된다.
				}
			}
			//3,2,8,5에 0붙이기
			while(index<n) //index는 -1이므로 5까지 간다.
			{
				nums[index]=0;
				index++;
			}

			System.out.println("뒤에 0을 붙이는 경우");
			for(int i: nums)
				System.out.println("i "+i);
			
			//(2) 앞에 0을 넣는 방법 -> 0,0,3,2,8,5
			//5->8->2->3순으로 채우면 된다.
			int n2=nums.length; //6, 인덱스는 0부터 시작해서 -1를 해야한다.
			int index2=n2-1; //끝방인 5번방
			
			//5번방 -> 4번방 -> 3번방 -> 2번방 -> 1번방 -> 0번방
			for(int i=n2-1; i>=0; i--) {
				if(nums[i]!=0) {			//nums가 0이 아닐 떄
					nums[index2]=nums[i]; 	//nums의 index에 nums의 i 넣기
					index2--;				//nums가 0이 아닐 때 index에 i를 넣는다.
											//-> index++로 index는 0이 아닌 첫번째 순서가 된다.
				}
			}
			//3,2,8,5 앞에 0붙이기
			while(index2>=0) //index는 -1이므로 5까지 간다.
			{
				nums[index2]=0;
				index2--;
			}

			System.out.println("앞에 0을 붙이는 경우");
			for(int i: nums)
				System.out.println("i "+i);
			
			}
	
		}
	//제로 이동
	//주어진 정수 배열에서 0이 아닌 값은 상대적 순서를 유지하고, 모든 0을 끝으로 이동
	
	//문제 해결
	//1. 값이 0이 아닌 값을 array에 담는다. -> for문
	//2. Index를 기억
	//3. 최초로 0이 나오는 해당 index에 0인 값을 넣는다.

 

 

package Sorting_SearchingBasic;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Sorting_Searching2 {
	public static void main(String[] args) {
		
		Sorting_Searching2 a = new Sorting_Searching2();
		int[] nums = {2,3,1,5,6,4};
		int k=2;
		
//		int[] nums= {3,2,3,1,2,4,5,5,6};
//		int k=4;
		System.out.println(a.solve(nums,k));
		System.out.println(a.solve_pq(nums,k));
		
		}
	//k번째 제일 큰 원소
	//배열에서 k번쨰로 큰 요소 반환
	//k번쨰로 큰 요소는 정렬 후 값에 대한 가장 큰 요소가 아닌 유일한 순서 요소
	
	//문제 해결 [방법 1-소팅]
	//1. 소팅
	//2. k번째로 큰 값 찾기
	
	//문제 해결 [방법 2-MIN HEAP]
	//1. 오름차순으로 만든 priority queue
	//2. pq를 이용해 사이즈를 유지 [항상 최상단을 제거해 사이즈 유지]
	 
	//[1]
	public int solve(int[] nums, int k) {
		Arrays.sort(nums); //1,2,3,4,5,6
		
		int n	=	nums.length; //6
		return nums[n-k]; //4번방을 찾아야한다.
	}
	
	//[2]
	public int solve_pq(int[] nums, int k) {
		
		//1. ds
		Queue<Integer> pq = new PriorityQueue<>(); //기본값 : asc minHeap / Queue<> - PriorityQueue<>()
		
		//2. for, while
		for(int i : nums) {
			pq.offer(i);
			if(pq.size()>k) {	//pq사이즈가 k보다 때
				pq.poll();		//최상단 제거
			}
		}
		return pq.peek();		//최상단 반환
		
	}
}

 

 

package Sorting_SearchingBasic;

import java.util.PriorityQueue;
import java.util.Queue;

public class Sorting_Searching3 {
	public static void main(String[] args) {
		Sorting_Searching3 a = new Sorting_Searching3();
//		int[][] points = { { 1, 3 }, { -2, 2 } };
//		int k = 1;
		int [][] points = {{3,3},{5,-1},{-2,4}};
		int k =2;

		int[][] result = a.solve(points, k);
		a.print(result);
	}
	// 원점과 가장 가까운 지점
	// 제일 가까운 좌표를 k개의 개수만큼 리턴

	// 문제 해결
	// 1. 원점으로부터의 거리를 구하기
	// 2. 원점에서 제일 작은 거리에 있는 값 구하기
	// 3. 제일 작은 값부터 저장 -> PriorityQueue 이용
	// -> Queue<> - PriorityQueue<>() 에서 ()에 조건식 전달
	// 4. K개만큼 큐에서 poll해서 int[][]타입으로 전달

	public int[][] solve(int[][] points, int k) {
		// 1. ds
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
		// 큐에 int[]를 이용한, 우선순위큐, MinHeap이용, a-b형태로 오름차순

		int[][] res = new int[k][2]; // 1*2행렬 필요 -> k==1

		// 2. for, while
		for (int[] p : points) { // points를 p로 받아서 for문 돌리기
			pq.offer(p); // k값에 따라 개수를 반환해주기 때문에
		}
		int index = 0;
		while (index < k) {// k개 만큼 빼내기
			res[index] = pq.poll(); // offer이후 pool 필수, res은 이차원배열로 index 배열의 0번방 1번방..
			// 맨 처음 8을 빼서 넣는다.
			index++;
		}
		return res;
	}

	public void print(int[][] result) {
		int m = result.length;
		int n = result[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(" [" + i + "][" + j + "] " + result[i][j]);
			}
			System.out.println();
		}
	}

}

 

 

package Sorting_SearchingBasic;

import java.util.Arrays;

public class Sorting_Searching4 {
	public static void main(String[] args) {
		
		Sorting_Searching4 a = new Sorting_Searching4();
//		int[][] intervals = {{5,10},{16,20,},{0,30}};
		int[][] intervals = {{7,10}, {2,4}};
		
		System.out.println(a.solve(intervals));
		
		}
	//미팅룸
	//미팅 시간 배열(intervals)을 이용해 회의 참석 가능여부 리턴
	//문제 해결
	//1. 시작 시간으로 정렬 								-> Arrays.sort( , ) [미팅 시간 배열, 소팅 조건]
	//2. for문에서 예약건별 start, end 시간 비교			-> 이차원 배열 이용해 첫번째 배열을 빼서 [비교 기준] 두번째부터 비교
	//3. 전.end > 현.start인 경우 회의실 필요 -> false 반환 -> end=interval[0][1]
	
	public boolean solve(int[][] intervals) {
		if (intervals == null || intervals.length==0)
			return true;
		
		//1. sorting
		//2차원 배열이므로
		print(intervals);
		Arrays.sort(intervals, (a,b)-> a[0]-b[0]);	// sort(이차원 배열, 배열 반환형), 오름차순;
		System.out.println("=========");
		print(intervals);
		
		//2. for,while
		//앞시간과 뒷시간을 비교하기 위해 앞 시간을 기준
		int end = intervals[0][1]; //0,30
		for(int i=1; i<intervals.length; i++) {
			//먼저 5,10부터 비교
			if(intervals[i][0]<end)	//앞.end와 뒤.start를 비교
			{
				return false;
			}
			end = intervals[i][1];	//처음 기준으로 비교 후 그 다음 1,1의 end인 10으로 비교
		}
		return true; 				//for문에 걸리지 않으면 true
	}
	public void print(int[][] intervals) {
		int m = intervals.length;
		int n = intervals[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(" [" + i + "][" + j + "] " + intervals[i][j]);
			}
			System.out.println();
		}
	}


}

 

 

 

package Sorting_SearchingBasic;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Sorting_Searching5 {
	public static void main(String[] args) {
		Sorting_Searching5 a = new Sorting_Searching5();
		int[][] intervals= { {5,10}, {16,20}, {0,30}};
		System.out.println(a.solve(intervals));
		
		}
	//미팅룸2
	//Intervals 배열을 이용해 사람들이 회의에 참석하려면 몇 개의 회의실
	//문제 해결
	//1. 시간 순으로 정렬 -> 컬렉션 프레임워크 확인 -> Arrays, Collections.sort()
	//2. 회의 끝시간이 가장 긴 경우 확인
	//3. 앞.end와 뒤.start 시간 비교 : priortyqueue - minheap이용
	//4. 회의실 하나로 합칠 경우 : 앞.end>뒷.start
	//->  큐에 추가 
	//5. 회의실 추가가 필요한 경우 :앞.end > 뒷.start 
	//-> 큐에 있는 걸 빼서 (poll) 합친 후 큐에 추가
	
	public int solve(int[][] intervals){
		//1. ds
		Arrays.sort(intervals, (a,b)-> a[0]-b[0]); //asc / sort(대상, 캐스팅 방법[기준설정]) 2차원배열을 1차원으로 캐스팅
		Queue<int[]> q = new PriorityQueue<>((a,b)-> a[1]-b[1]);
		//정렬한 배열을 가져와 큐에 넣는다. Queue <>- PriorityQueue<>()
		//end time 기준 오름차순으로 관리
		
		//2. for pq
		for(int[] arr : intervals) {
			if(q.isEmpty())q.offer(arr); //큐가 비어 있으면 큐에 삽입 //0,30 삽입
			else {
				// 앞.end와 뒤.start 시간 비교 -> 뒤.start 시간 : q.peek()[1], 앞.end 시간 :arr[0]
				if(q.peek()[1] <=arr[0]) { //5, 10과 16분을 비교
					//10=<16
					q.poll(); //큐에서 뺀다. 뒤.start부터 뒤.end까지 뺀다.
				}
				q.offer(arr); //큐에 합치기 위해 16,20 삽입
			}
			
		}
		return q.size(); 
	}

}

 

 

 

package Sorting_SearchingBasic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sorting_Searching6 {
	public static void main(String[] args) {
		Sorting_Searching6 a = new Sorting_Searching6();
		int[][] intervals= {
				{1,4},
				{8,10},
				{2,6},
				{15,18}
		};
		int[][] res=a.solve(intervals);
		for(int[] arr:res) {
			System.out.println("result");
			System.out.println(arr[0]+":"+arr[1]);
		}
	}
	//interval 병합
	//interval 배열이 주어지면 겹치는 구간을 병합해 배열을 반환
	//문제 해결
	//1. 겹치는 부분을 합친다.
	//-> 전.end와 현.start를 비교해 합치고, 앞.start와 뒤.end를 결과리스트에 저장
	//2. 합친 이후 전.end과 현.start을 비교 도출
	
	//전.end >= 현.start -> end=Math.max(전.end, 현.end)
	//전.end >= 현.start가 아니면, 현재 값을 결과값에 저장해서 다음 부분과 비교
	
	//이차원 배열
	//int [][] grid = new int[4][2]
	//00: 1 / 01: 4
	//10: 2 / 11: 6
	//20: 8 / 21: 10
	//30: 15/ 31: 18
	
	//int [][] grid = new int[3][4]
	//0,0 0,1 0,2 0,3
	//1,0 1,1 1,2 1,3
	//2,0 2,1 2,2 2,3
	//3,0 3,1 3,2 3,3
	
	public int[][] solve(int[][] intervals){
		List<int[]> res= new ArrayList<>(); //List<> -ArrayList<>(); 중복허용 중간 삽입,변경,삭제 가능
		if(intervals.length==0 || intervals==null)
			return res.toArray(new int[0][]); //인터벌이 null이거나 길이가 0이면 빈값 반환
		
		//1. ds
		//정렬부터 수행
		print(intervals);
		Arrays.sort(intervals, (a,b)-> a[0]-b[0]); //asc
		System.out.println("==after==");
		print(intervals);
		
		//2. for, while
		//첫 부분을 뽑아서 for문 돌리기
		//-> 0번방 제외 1번방부터 돌리기
		int start= intervals[0][0];
		int end= intervals[0][1];
		//start =1, end =4
		
		for(int i=1; i<intervals.length;i++) {
			System.out.println("i: "+i);
			// 다음부분과 비교하기 위해 추출
			if(end >=intervals[i][0]) { //전.end>=현.start인지 확인 -> 새롭게 만들기
				end = Math.max(end ,intervals[i][1]); //Math.max(전.end, 현.end)
			//2,6 -> 1,6으로 만들기
			}else {
				//1,6과 8,10이 겹치는지 확인하고 겹치지 않으니 그대로 저장
				
				res.add(new int[] {start, end}); //List안에 Integer 배열 저장 -> List<int[]> 형태
				//1,6 삽입
				
				start = intervals[i][0];//8
				end=intervals[i][1];	//10
				
			}
		}
		//15,18이 삽입이 아직 안되었으므로 삽입
		res.add(new int[] {start,end});
		
		//반환형이 int[][]이므로, 반환형 변환
		return res.toArray(new int[res.size()][]); //형변환 List<int[]> -> int[][]로
//		return res.toArray(new int[0][]); 		   //형변환 List<int[]> -> int[][]로
		
	}
	private void print(int[][] grid) {
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				System.out.print(grid[i][j] + "\t");
			}
			System.out.println();
		}
	}
}

 

 

 

package Sorting_SearchingBasic;

import java.util.Arrays;

public class Sorting_Searching7 {
	public static void main(String[] args) {
		String [] input = {"dig1 8 2 3 1", "let1 abc cat", "dig1 2 5", "let2 good dog book", "let3 abc cat"};
		
		Sorting_Searching7 a = new Sorting_Searching7();
		String [] result = a.reorderLogFiles_1(input);
		for(String s : result)
			System.out.println("s: " + s);
		

	}
	// 로그 파일의 데이터 재정렬
	// 배열로 logs가 주어지고, 공백으로 구분된 문자열로 첫번쨰 단어가 식별자

	// 식별자는 문자열 이후 숫자가 나온다.
	// 같은 경우 식별자로 정렬

	// 문제 해결 [1] Identifier와 나누기
	// 1. split이용 -> 0번방은 식별자, 1번방은 문자열이나 숫자
	// 2. 값들을 비교하면서 정렬하는데 같을 경우 식별자를 기준으로 정렬

	// 문제 해결 [2] 두번째 문자열 판단
	// 1. Char 값이 숫자인지 문자인지 판단 -> isDigit과 isLetter 이용
	// 2. Character.isDigit(split[].charAt())

	// 문제 해결 [3] Comparator 적용하기
	// 1. 모두 문자 / 모두 숫자 return 0;
	// 2. 첫번째는 숫자, 두번쨰는 문자 return 1;/ 첫번째는 문자, 두번째는 숫자 -> 오름차순 return -1;

	// Sort 개념
	// public int compareTo(){
	// return A.compareTo(B);
	// }

	// 1. A와 B가 같으면 0
	// 2. A>B이면 1
	// 3. A<B이면 -1 오름차순 (123인경우 2-3은 -1 음수) -> 오름마 : 오른쪽이 크면 마이너스

	// 문제 해결 [4] Comparator 모두 문자인 경우
	// 1. split[1]과 split2[1] 오름차순으로 비교
	// 2. 같은 경우 (0인 경우) split1[0].compareTo(split2[0]); 적용
	// -> 즉, 식별자에 대해 오름차순 정렬

	// 문제 해결 [5] Comparator 나머지 비교

	/*
	 * 1. 기본 조건을 사용하는 간단한 방법 -> 오름차순 정렬 Collections.sort(intervals, (a,b)->
	 * a.start-b.start);
	 * 
	 * =========================================================
	 * 
	 * 2. 직접 조건을 지정하는 방식 [내부를 분리]
	 * 
	 * Collections.sort(intervals, comp2);
	 * 
	 * Comparator<Interval> comp2 = new Comparator<Interval>() {
	 * 
	 * @OVerride public int compare (Interval o1, Interval o2) { if(o1.start>
	 * o2.start) { return 1;
	 * 
	 * }else if(o1.start <o2.start) { return -1;
	 * 
	 * }else { return 0; } };
	 * 
	 * =========================================================
	 * 
	 * 3. Comparator comp= new Comparator<Interval>() { public int compare(Interval
	 * a, Interval b) { return a.start - b.start; }};
	 * 
	 */

	// 문제 해결 [1] Identifier와 나누기
	// 1. split이용 -> 0번방은 식별자, 1번방은 문자열이나 숫자
	// 2. 값들을 비교하면서 정렬하는데 같을 경우 식별자를 기준으로 정렬
	public String[] reorderLogFiles_1(String[] logs) {
		Arrays.sort(logs, (s1, s2) -> {
			String[] split1 = s1.split(" ", 2);
			String[] split2 = s2.split(" ", 2);

			// 문제 해결 [2] 두번째 문자열 판단
			// 1. Char 값이 숫자인지 문자인지 판단 -> isDigit과 isLetter 이용
			// 2. Character.isDigit(split[].charAt())
			boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
			boolean isDigit2 = Character.isDigit(split2[1].charAt(0));

			if (!isDigit1 && !isDigit2) {
				// 1. 모두 문자 (2) 정렬된걸로 수행할때 let1 abc cat let3 abc cat처럼 같을 때
				
				int comp = split1[1].compareTo(split2[1]); // 오름차순 마-1 [식별자가 아닌 값에 대해 오름차순 정렬]
				
				if (comp == 0) {
					return split1[0].compareTo(split2[0]); //(3) 식별자 비교해 오름차순 정렬
				}
				else {
					return comp;
				}
				
			} else if (isDigit1 && isDigit2) {
				// 2. 모두 숫자
				return 0;
			} else if (isDigit1 && !isDigit2) {
				// 3. 첫번째는 숫자, 두번째는 문자
				return 1;
			} else {
				// 4. 첫번째는 문자, 두번째는 숫자
				return -1; //(1) 오름차순으로 정렬
			}
		});
		return logs;
	}
}//ctrl + shift + f 자동정렬