- Two Pointer Algorithm
1. 배열 또는 리스트에서 두 개의 포인터를 사용하여 원하는 조건을 만족하는 요소나 부분 배열을 찾는 데 사용되는 알고리즘이다. 이 알고리즘은 주로 정렬된 배열 또는 리스트에서 사용되며, 시간 복잡도를 개선하기 위한 효율적인 방법 중 하나이다.
- Sliding Window
1. 배열 또는 문자열과 같은 순차적인 데이터 구조를 처리하고 여러 데이터 포인트의 부분집합을 검사하거나 연산하는데 사용되는 알고리즘 기법이다.
3_1
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
- 방법 1
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2) {
ArrayList<Integer> answer = new ArrayList<>();
//포인터를 사용하여 푸는 알고리즘... 위치(포인터를 변수로 생성) 후 해당 위치 지정 후 비교
int p1 = 0, p2 = 0;
while (p1 < n && p2 < m) {
if (arr1[p1] < arr2[p2]) {
answer.add(arr1[p1]);
p1++;
} else {
answer.add(arr2[p2]);
p2++;
}
}
while (p1 < n) {
answer.add(arr1[p1]);
p1++;
}
while (p2 < m) {
answer.add(arr2[p2]);
p2++;
}
return answer;
}
public static void Main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr1 = new int[n];
for (int i = 0; i < n; i++) {
arr1[i] = scanner.nextInt();
}
int m = scanner.nextInt();
int[] arr2 = new int[m];
for (int i = 0; i < m; i++) {
arr2[i] = scanner.nextInt();
}
for (int x : main.solution(n, m, arr1, arr2)) {
System.out.print(x+ " ");
}
}
}* 현재 각 배열은 정렬이 되어 있는 상태다.
1. 포인터(즉, 위치를 나타내는 변수)를 2개 생성한다. 배열 2개의 위치를 해당 변수를 통해 지정한다.
2. 포인터 변수를 통해 배열의 각 위치의 숫자를 비교해 가며 작은 숫자를 ArrayList에 넣는다.
3. 하나의 배열이 끝나면 아직 끝나지 않은 배열을 순차적으로 ArrayList에 순차적으로 넣는다.
3_2
A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
- 방법 1
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2) {
ArrayList<Integer> answer = new ArrayList<>();
Arrays.sort(arr1);
Arrays.sort(arr2);
int p1=0,p2=0;
while (p1 < n && p2 < m) {
if (arr1[p1] == arr2[p2]) {
answer.add(arr1[p1]);
p1++;
p2++;
} else if (arr1[p1] < arr2[p2]) {
p1++;
} else {
p2++;
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr1 = new int[n];
for (int i = 0; i < n; i++) {
arr1[i] = scanner.nextInt();
}
int m = scanner.nextInt();
int[] arr2 = new int[m];
for (int i = 0; i < m; i++) {
arr2[i] = scanner.nextInt();
}
for (int x : main.solution(n, m, arr1, arr2)) {
System.out.print(x+ " ");
}
}
}- 3_1번 문제와 동일하게 포인터 변수를 생성하여 각 배열의 위치끼리 값을 비교하여 포인터 변수의 위치를 이동시킨다.
- 정렬의 경우 Arrays.sort 라이브러리를 사용하여 쉽게 정렬 할 수 있다.
- 각 배열을 정렬 후 if문을 활용하여 값을 도출하면 된다.
3_3
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
- 방법 1
import java.util.Scanner;
public class Main {
public int solution(int n, int m, int[] arr) {
int answer = 0;
int sum = 0;
//3개 크기의 window를 생성한다.
for (int k = 0; k < m; k++) {
sum += arr[k];
}
answer=sum;
//3 크기의 window를 옮기면서 우측에 새롭게 포함된 값은 더하고, 왼쪽에 이탈된 값은 빼준다.
for (int i = m; i < n; i++) {
sum += (arr[i] - arr[i - m]);
answer = Math.max(answer, sum);
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(main.solution(n,m,arr));
}
}1. 위 코드는 window 즉, 특정 배열의 원하는 갯수만큼 포함시키는 크기의 창을 만든다.
2. 3 크기의 window을 생성하게 되면 0,1,2 / 1,2,3 / 2,3,4 와 같이 해당 배열의 인덱스들을 포함시킨다.
3. 위 문제의 경우 연속된 3일(window의 크기 3)의 최대값을 구하는 것이기 때문에 1,2에서 말한 것과 같이 3크기의 창을 만들고 한칸씩 우측으로 옮기면서 창 크기를 계속해서 비교해 나가면 된다.
- 위 문제의 경우 기존에는 for문을 돌면서 3개씩 더하고 비교해 나가는 방법이나, 이중 for문을 사용하는 방법을 썼었는데 이렇게 되면, n^2의 시간이 걸리기 때문에 효율이 좋지 못하기 때문에 특정 배열의 값을 비교하는 방식은 위 방식 처럼 window를 만들어 비교하는 것이 좋다.
3_4
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
- 방법 1
import java.util.Scanner;
public class Main {
public int solution(int n, int m, int[] arr) {
int answer = 0, sum = 0, lt = 0;
for (int rt = 0; rt < n; rt++) {
sum += arr[rt];
if (sum == m) {
answer++;
}
while (sum >= 6) {
sum -= arr[lt++];
if (sum == m) {
answer++;
}
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(main.solution(n,m,arr));
}
}- 위 문제도 포인터 변수를 사용해서 해결하는 문제다.
1. 연속된 숫자의 합을 구하는 문제이기 때문에 좌측부터 조건에 맞는 합이 되는지 계속해서 비교해 나간다.
2. 우측 포인터 변수를 계속 더해 나가다가 조건과 일치하는 값이 나오게 되면 count를 증가 시키고, 만약 조건보다 큰 값이 나오게 되면, 가장 좌측의 값을 빼고 난 후 다시 합을 조건과 비교한다.
- 등호가 언제 어디서 들어가야 하는지 잘 생각해야 겠다. 추가로 조건문과 반복문의 순서를 잘 생각하면서 반복 조건을 유지하면서 조건을 확인하고 있는지 코드의 흐름을 잘 생각하면서 코드를 짜야겠다.
- 최초에 등호 조건과 조건문의 위치 때문에 정확한 답이 계속해서 안나온 것 같다.
3_5
N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.
- 방법 1
import java.util.Scanner;
public class Main {
public int solution(int n) {
int answer = 0, sum = 0, lt = 0;
int m = n / 2 + 1;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i+1;
}
for (int rt = 0; rt < m; rt++) {
sum += arr[rt];
if (sum == n) {
answer++;
}
while (sum >= n) {
sum -= arr[lt++];
if(sum==n) answer++;
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(main.solution(n));
}
}- 위 문제도 똑같이 포인터 변수를 만들어 값을 더해 조건과 비교하는 방식을 사용한다.
- 처음 풀 때 조건에 대한 값을 n/2하고 풀게되면 결과를 도출하기 위한 반복수가 훨씬 줄어든 다는 것을 생각해내지 못했다.
- 어차피 연속된 두 수의 합일 경우 최대 n/2 +1 이상의 값은 2개 이상 더했을 때 무조건 조건의 값을 초과해버리기 때문이다.
- 조건을 도출하기 위한 최적의 배열 수를 구성하는 것도 고려를 반드시 해야겠다.
- 방법 2
import java.util.Scanner;
public class Main {
public int solution(int n) {
int answer = 0, cnt = 1;
n--;
while (n > 0) {
cnt++;
n = n - cnt;
if (n % cnt == 0) {
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(main.solution(n));
}
}- 두번째 방법은 수학적으로 접근한 방법이다. (아예 생각지도 못했다...)
1. 2개 숫자 이상 연속된 숫자의 합을 구하는 문제였다. 즉, 연속된 숫자 (ex) 1,2,3...) 를 조건으로 주어진 숫자에서 뺀 다음 연속된 숫자의 갯수로 나눴을 때 나머지가 0이면 해당 연속된 숫자는 합쳐서 조건의 숫자가 된다는 얘기다
1.1. 예를 들어 조건의 숫자가 13이라고 주어졌을 때, 2개의 연속된 숫자(1,2)를 빼주고(13-(1+2)=10) 빼준 숫자를 숫자가 연속된 횟수만큼으로 나눴을때 나머지가 0이면(10%2=0) 조건을 만족하는 연속된 2개의 숫자가 존재한다는 뜻이다. (10/2=5 몫을 연속된 숫자 1,2에 더해주면 6,7이 되고, 해당 두 숫자를 더하면 13이 된다.)
2. 위와 같은 수학적 방법으로 연속된 숫자의 합을 구할 수도 있다.
- 방법을 보고 나면 당연하듯이 느껴지지만 혼자서 생각해내지 못한 것이기 때문에 위와 같은 수학적 방법도 익숙해져야겠다.
3_6
0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.
만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면
1 1 0 0 1 1 0 1 1 0 1 1 0 1
여러분이 만들 수 있는 1이 연속된 연속부분수열은
이며 그 길이는 8입니다.
- 방법 1
import java.util.Scanner;
public class Main {
public int solution(int n, int m, int[] arr) {
int answer = 0, lt = 0, cnt = 0;
for (int rt = 0; rt < n; rt++) {
if (arr[rt] == 0) {
cnt++;
}
while (cnt > m) {
if (arr[lt] == 0) {
cnt--;
}
lt++;
}
answer = Math.max(answer, rt - lt + 1);
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(main.solution(n, m, arr));
}
}- 처음에 아예 풀어내지 못했다... 값을 꼭 바꾸고 비교해야 한다고 생각해서 그런 것 같다.
- 위 문제를 보면 값을 변경하는 횟수가 주어졌고, 값을 굳이 바꿀 필요없이 변경 횟수가 증가하면 해당 인덱스의 값이 변경되었다고 가정하고 길이를 구하면 된다.
- 추가로 횟수를 넘었을때 기존의 바꾼 인덱스 값을 바꿨다고 가정한 부분을 인덱스의 값은 그대로 0이기 때문에 해당 위치를 찾아서 다시 길이를 구해주면 되는 문제였다.
- 풀이를 보면 항상 쉽다고 느껴지지만, 혼자서 생각해내지 못한 것은 절대 쉬운 것도, 내가 푼 문제도 아니기 때문에 반복해서 기억하고 넘어가야 겠다.
* 결국 위 문제도 포인터 변수를 사용하여 해결한 문제고, 꼭 인덱스 값을 변경하지 않더라도 변경되었다고 가정하고 풀면 되는 문제도 있다. (나중에 다시 풀어보자)
'Programming > CodingTest' 카테고리의 다른 글
| CodingTest - Sorting and Searching(정렬, 이분 검색과 결정 알고리즘) (0) | 2023.11.08 |
|---|---|
| CodingTest - HashMap, TreeSet (해쉬, 정렬지원 Set) (0) | 2023.11.01 |
| CodingTest - 퀵 정렬 (1) | 2023.10.17 |
| CodingTest - Array(1, 2차원 배열) / 2 (1) | 2023.10.17 |
| CodingTest - Array(1, 2차원 배열) / 1 (0) | 2023.10.16 |