투포인터 문제 - 두 배열의 공통 원소 출력
- 공통 원소를 추출해서 오름차순 출력하기
- 배열들을 미리 오름차순 정렬한다.
- 같은 값일 경우 둘 중에 아무거나 값을 넣고 둘 다 포인터 index를 증가시킨다.
- 더 작은 배열의 포인터 index를 증가시킨다.
- 첫 번째 배열이 더 큰 경우에 두 번째 배열 포인터 index++
- 두 번째 배열이 더 큰 경우에 첫 번째 배열 포인터 index++
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public static ArrayList<Integer> solution(int[] arr1, int[] arr2){
ArrayList<Integer> answer = new ArrayList<>();
Arrays.sort(arr1);
Arrays.sort(arr2);
int p1=0;
int p2=0;
int n = arr1.length;
int m = arr2.length;
while(p1<n && p2<m){
if(arr1[p1]==arr2[p2]){ // 둘중에 값 아무거나 넣고, 둘다 idx증가
answer.add(arr1[p1++]);
p2++;
} else if(arr1[p1]>arr2[p2]){ // 1번째 배열이 더 큰 경우 -> 작은 쪽을 증가 시키기
p2++;
} else {
p1++;
}
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
int[] arr1 = {1,3,9,5,2};
int[] arr2 = {3,2,5,7,8};
System.out.println(T.solution(arr1,arr2));
}
}
슬라이딩윈도우 문제 - 연속된 K일의 최대 매출 구하기문제
- 수열에서 연속된 K개를 합했을 때, 합의 최대 값 구하기
- 일단 첫 번째부터 K번째 까지 값들을 다 더해줘서 max 값으로 지정한다.
- 그 이후로 k번째부터 배열의 마지막까지 반복문을 실행한다.
- sum = sum + 현재값 - 첫번째값
- 현재의 총합과 이전의 총합 중에서 최대 값으로 저장해준다.
- 배열을 종료 했을 때 나오는 최대 값이 수열에서 연속된 K개의 값들 중 최대 값이된다.
public class Solution {
public static int solution(int[] arr, int k){
int answer = 0;
int sum = 0;
// 일단 맨 첫번째부터 k번째 값들을 다 더해준다.
for(int i=0; i<k; i++){
sum += arr[i];
}
answer = sum;
// k부터 배열의 마지막까지 계산해본다.
for(int i=k; i<arr.length; i++){
sum+=(arr[i]-arr[i-k]); // 현재 값을 더해주고 맨 앞의 값을 지워준다.
answer = Math.max(answer, sum); // 이전의 총합과 현재의 총합을 비교해줘서 최대값을 저장
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
int[] arr = {12,15,11,20,25,10,20,19,13,15};
System.out.println(T.solution(arr, 3));
}
}
복합적 문제 - 특정 숫자가 되는 경우의 수 구하기
- 투포인터는 O(N^2)에서 O(N)으로 개선 가능하다.
- N개의 수열에서 특정 숫자 M이 되는 경우의 수를 구해라
- N=8, M=6
- 수열 : 1 2 1 3 1 1 1 2
// sum이 M보다 크면 lt를 빼주고 lt++
// sum이 M보다 작으면 rt++
for(int rt=0; rt<N; rt++){ // 1. 증가
sum+= arr[rt]; // 2. 더하기
if(sum==M) answer++; // 3. 확인
// sum이 M보다 커지면 삭제
while(sum>=M){
sum -= arr[lt++];
if(sum==M){
answer++;
}
}
}
복합적 문제 - 연속으로 1인 수열의 최대 길이 출력
public class Solution {
public static int solution(int[] arr, int k){
int N = arr.length; // 길이는 : rt - lt + 1
int count = 0, lt=0;
int answer = 0;
for(int rt=0; rt<arr.length; rt++){
if(arr[rt]==0) count++;
while(count>k){
if(arr[lt]==0) count--;
lt++;
}
answer = Math.max(answer, rt-lt+1);
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
int[] arr = {1,1,0,0,1,1,0,1,1,0,1,1,0,1};
System.out.println(T.solution(arr, 2));
}
}
Hash + 슬라이딩 윈도우 - N일 중에서 K일 동안 벌어들일 수 있는 매출액의 종류를 각 구간별로 구하기
public class Solution {
public static ArrayList<Integer> solution(int[] arr){
int n = 7;
int k = 4;
ArrayList<Integer> answer = new ArrayList<>();
HashMap<Integer, Integer> HM = new HashMap<>();
for(int i=0; i<k-1; i++){
HM.put(arr[i], HM.getOrDefault(arr[i],0)+1);
}
int lt = 0;
for(int rt=k-1; rt<n; rt++){
HM.put(arr[rt], HM.getOrDefault(arr[rt],0)+1);
answer.add(HM.size());
HM.put(arr[lt], HM.get(arr[lt])-1);
if(HM.get(arr[lt])==0) {
HM.remove(arr[lt]);
}
lt++;
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
int[] arr = {20,12,20,10,23,17,10};
System.out.println(T.solution(arr));
}
}
Hash + 슬라이딩 윈도우 - 모든 아나그램 찾기
import java.util.HashMap;
public class Solution {
public static int solution(String s, String t){
int answer = 0;
HashMap<Character, Integer> am = new HashMap<>();
HashMap<Character, Integer> bm = new HashMap<>();
for(char x : t.toCharArray()) bm.put(x, bm.getOrDefault(x,0)+1);
int L = t.length()-1;
for(int i=0; i<L; i++) am.put(s.charAt(i), am.getOrDefault(s.charAt(i), 0)+1);
int lt = 0;
for(int rt=L; rt<s.length(); rt++){
am.put(s.charAt(rt), am.getOrDefault(s.charAt(rt), 0)+1);
if(am.equals(bm)) answer++;
am.put(s.charAt(lt), am.get(s.charAt(lt))-1);
if(am.get(s.charAt(lt))==0) am.remove(s.charAt(lt));
lt++;
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
String s = "bacaAacbaa";
String t = "abca";
System.out.println(T.solution(s,t));
}
}'코딩테스트 > Java' 카테고리의 다른 글
| [Hackerrank] Big sorting (0) | 2022.10.18 |
|---|---|
| [JAVA] 정렬 - binary sort 이진 정렬 (0) | 2022.06.30 |
| [JAVA] 2차원 배열 - 현재 위치의 값보다 상하좌우에서 큰 값 확인하기 (0) | 2022.06.30 |
| [JAVA] DFS - 인접 행렬을 사용한 경로 탐색 (0) | 2022.06.29 |
| [JAVA] DFS, BFS - 루트 노드에서 말단 노드까지 가장 최단 경로 (0) | 2022.06.29 |
