728x90
📍 섹션 3.Two pointers, sliding window [효율성 O(n2) -> O(n)]
효율성[O(n2) -> O(n)] 섹션 - (1)
3-1. 두 배열 합치기 | Two Pointers 알고리즘 사용
/* 3-1. 두 배열 합치기
[설명] 효율성
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
*/
public class Main1 {
//솔루션 함수
public ArrayList<Integer> solution(int n, int m, int[]a, int[]b) {
ArrayList<Integer> answer = new ArrayList<>();
int p1 =0, p2 = 0; //두 개의 포인터 선언
//각각 지칭할 배열 크기 안에서만 돌도록 조건 넣고
while(p1 < n && p2 <m) {
if(a[p1] < b[p2]) {
answer.add(a[p1++]); //먼저 a[p1] 넣고 p1++ 된다.
}else{
answer.add(b[p2++]);
}
}
//어떤 지칭 p가 나왔으면. 이제 남은 애들 answer에 누적시키기 위해
//각각의 남은 경우 대비해서 add 처리
while(p1<n) answer.add(a[p1++]);
while(p2<m) answer.add(b[p2++]);
return answer;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Main1 T = new Main1();
Scanner kb = new Scanner(System.in);
//입력
int n = kb.nextInt();
int[] a = new int[n];
for(int i = 0; i<n; i++) {
a[i] = kb.nextInt();
}
int m = kb.nextInt();
int[] b = new int[m];
for(int i = 0; i<m; i++) {
b[i] = kb.nextInt();
}
//출력
for(int x : T.solution(n, m, a, b)) {
System.out.print(x + " ");
}
}
}
3-2.공통원소 구하기 | Two Pointers 알고리즘 사용
/* 3-2 공통원소 구하기 (교집합-> 오름차순)
A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
*/
public class Main2 {
//솔루션 함수
public ArrayList<Integer> solution(int n, int m, int[]a, int[]b){
ArrayList<Integer> answer = new ArrayList<>();
int p1 = 0, p2 = 0;
//1) 먼저 두 배열 오름차순 정렬 시킬 것
Arrays.sort(a);
Arrays.sort(b);
//2) 공통원소 담기 (한 배열 끝나면 끝. 교집합만 구하는 거기 때문)
while(p1 < n && p2 <m) {
if(a[p1] == b[p2]) {
answer.add(a[p1++]); //같은 애 둘 중 하나만 담음
p2++;
}else if(a[p1] < b[p2]) {
p1++; //더 작은 애의 포인터만++
}else {
p2++; //더 작은 애의 포인터만++
}
}
return answer;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Main2 T = new Main2();
Scanner kb = new Scanner(System.in);
//입력
int n = kb.nextInt();
int[] a = new int[n];
for(int i = 0; i<n; i++) {
a[i] = kb.nextInt();
}
int m = kb.nextInt();
int[] b = new int[m];
for(int i = 0; i<m; i++) {
b[i] = kb.nextInt();
}
//출력
for(int x : T.solution(n, m, a, b)) {
System.out.print(x + " ");
}
}
}
3-3. 최대 매출 | sliding window 알고리즘 사용
import java.util.Scanner;
/* 3-3. 최대 매출 (sliding window 알고리즘 사용)
[입력]
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력]
첫 줄에 최대 매출액 출력
*/
public class Main3 {
//솔루션 함수
public int solution(int n, int k, int[] arr) {
int answer = 0, sum = 0;
//최초의 연속3개 합 세팅해놈
for(int i =0; i < k; i++) {
sum += arr[i];
}
answer = sum; //일단 초기화 저장시켜놓고
//sliding window
//남은 뒷부분을 다시 for 돌면서 창 밀고 나가고 (민 만큼 앞 부분 빼고)
for(int i = k; i<n; i++) {
sum += (arr[i] - arr[i-k]); //민 만큼 더하고 (밀린 부분 빼고)
answer = Math.max(answer, sum); //더 큰 값으로 세팅
}
return answer;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Main3 T = new Main3();
Scanner kb = new Scanner(System.in);
//입력
int n = kb.nextInt();
int k = kb.nextInt();
int[] arr = new int[n];
for(int i = 0; i<n; i++) {
arr[i] = kb.nextInt();
}
//출력
System.out.println(T.solution(n, k, arr));
}
}
3-4. 연속 부분수열 | 복합적 문제 *어려움**
- lt, rt 두 개의 포인터로 (구간 찍음)
- 1) sum < m 작은 동안에는 구간 rt ++, sum에 누적시킴
- 2) sum >= m 크거나 같은 동안에는 구간 lt++ , 기존 lt 지칭 값은 sum에서 빼줌
import java.util.Scanner;
/* 3-4. 연속 부분수열
[입력]
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
[출력]
첫째 줄에 경우의 수를 출력한다.
*/
public class Main4 {
//솔루션 함수
public int solution(int n, int m, int[] arr) {
int answer = 0;
//lt = 0 찍어놓고
int lt = 0, sum = 0;
//rt 확장시키면서 그 구간의 sum을 비교 m과 비교함
for(int rt = 0; rt <n; rt++) {
sum += arr[rt];
if(sum == m) answer++;
//for이 아니라 while을 돌리는 이유
//[11115] 일 경우 sum==6될때까지 lt가 연속 증가 가능하도록
while(sum >= m) {
sum -= arr[lt++];
if(sum == m) answer++;
}
}
return answer;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Main4 T = new Main4();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n];
for(int i = 0; i<n; i++) {
arr[i] = kb.nextInt();
}
System.out.println(T.solution(n, m, arr));
}
}
728x90
'알고리즘 이론 [개념] > [개념] 코테 알고리즘 공부 - 시즌 1' 카테고리의 다른 글
HashMap, TreeSet - (1) (0) | 2023.03.06 |
---|---|
효율성[O(n2) -> O(n)] 섹션 - (2) (0) | 2023.03.03 |
배열(Array) 섹션 - (3) (0) | 2023.03.01 |
배열(Array) 섹션 - (2) (0) | 2023.02.28 |
배열(Array) 섹션 - (1) (0) | 2023.02.27 |