728x90
반응형
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 자동정렬728x90
반응형
'Java > Java 알고리즘' 카테고리의 다른 글
| [Java 기본 알고리즘] (6) 큐&스택 (0) | 2022.01.06 |
|---|---|
| [Java 기본 알고리즘] (4) 투 포인터 (0) | 2022.01.04 |
| [Java 기본 알고리즘] (3) Array (0) | 2022.01.03 |
| [Java 기본 알고리즘] (1) String (0) | 2021.12.30 |
| [Java] String 메서드 (0) | 2021.12.30 |
