[JAVA] 알고리즘 문제풀이 기초 - Two pointers, Sliding window
Two pointers, Sliding window
두 배열 합치기(3-1)
-
설명 : 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다. 세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다. 각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
-
출력 : 오름차순으로 정렬된 배열을 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int sa = scan.nextInt();
int[] a = new int[sa];
for(int i=0; i<sa; i++){
a[i] = scan.nextInt();
}
int sb = scan.nextInt();
int[] b = new int[sb];
for(int i=0; i<sb; i++){
b[i] = scan.nextInt();
}
for (Integer integer : t.solution(a,b)) {
System.out.print(integer+" ");
}
}
public List<Integer> solution(int[] a, int[] b){
List<Integer> result = new ArrayList<>();
for (int i : a) {
result.add(i);
}
for (int i : b) {
result.add(i);
}
Collections.sort(result);
return result;
}
}
- 풀이 답변
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int sa = scan.nextInt();
int[] a = new int[sa];
for(int i=0; i<sa; i++){
a[i] = scan.nextInt();
}
int sb = scan.nextInt();
int[] b = new int[sb];
for(int i=0; i<sb; i++){
b[i] = scan.nextInt();
}
for (Integer integer : t.solution(a,b)) {
System.out.print(integer+" ");
}
}
public List<Integer> solution(int[] a, int[] b){
List<Integer> result = new ArrayList<>();
int sa = 0;
int sb = 0;
while (sa<a.length && sb<b.length){
if(a[sa]<b[sb]){
result.add(a[sa]);
sa++;
} else {
result.add(b[sb]);
sb++;
}
}
while (sa<a.length){
result.add(sa);
sa++;
}
while (sb<b.length){
result.add(sb);
sb++;
}
return result;
}
}
- 특징
- 내 풀이의 경우는 두 내용 모두 리스트에 담은 다음 Collections.sort()를 이용해서 일괄 정렬
- 코드가 짧아지기는 하나 코딩테스트시 원하는 알고리즘 보는 방식은 아니라고 함
- 두 배열 모두 길이가 끝나지 않을때까지 루프를 돌되, 두 배열을 비교해서 포인트가 작으면 리스트에 추가. 그리고 추가한 배열만 포인트를 뒷칸으로 넘김. 그리고 다시 비교
- 루프가 끝나면(하나의 배열의 사이즈가 끝나면) 남은 배열의 원소를 모두 리스트에 추가해줌
- 내 풀이의 경우는 두 내용 모두 리스트에 담은 다음 Collections.sort()를 이용해서 일괄 정렬
공통원소 구하기 (3-2)
-
설명 : A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다. 두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다. 네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 각 집합의 원소는 1,000,000,000이하의 자연수입니다.
-
출력 : 두 집합의 공통원소를 오름차순 정렬하여 출력합니다.
-
풀이 답변
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int sa = scan.nextInt();
int[] a = new int[sa];
for(int i=0; i<sa; i++){
a[i] = scan.nextInt();
}
int sb = scan.nextInt();
int[] b = new int[sb];
for(int i=0; i<sb; i++){
b[i] = scan.nextInt();
}
for (Integer integer : t.solution(a,b)) {
System.out.print(integer+" ");
}
}
public List<Integer> solution(int[] a, int[] b){
List<Integer> result = new ArrayList<>();
Arrays.sort(a);
Arrays.sort(b);
int sa = 0;
int sb = 0;
while (sa<a.length && sb<b.length){
if(a[sa]<b[sb]) sa++;
else if(a[sa]>b[sb]) sb++;
else {
result.add(a[sa++]);
sb++;
}
}
return result;
}
}
- 특징
- 내가 작성한 답변은 시간초과로 fail처리되어 풀이답변만 첨부함
- 지난 문제의 영향으로 Arrays.sort는 쓰면 안되는건줄 알고 수동으로 정렬하려던 것이 패착
- 두 배열을 미리 오름차순으로 정렬해두고 2포인트로 각각의 배열을 흝으며 동일할때에만 리스트에 추가해주는 방식
- 내가 작성한 답변은 시간초과로 fail처리되어 풀이답변만 첨부함
최대 매출 (3-3)
-
설명 : 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 12 1511 20 2510 20 19 13 15 연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.
-
입력 : 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다. 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
-
출력 : 첫 줄에 최대 매출액을 출력합니다.
-
작성 답안 (시간초과로 실패)
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int day = scan.nextInt();
int cnt = scan.nextInt();
int[] a = new int[day];
for(int i=0; i<day; i++){
a[i] = scan.nextInt();
}
System.out.print(t.solution(a,cnt));
}
public int solution(int[] a, int b){
int result = 0;
int sp = 0;
for (int i=0; i<a.length-b; i++){
int sum = 0;
for(int j=i; j<i+b; j++){
sum += a[j];
}
result = Math.max(result, sum);
}
return result;
}
}
- 특징
- 매번 루프를 도는 경우 더해야하는 범위가 커지거나, 배열 사이즈의 크기가 클수록 시간의 낭비가 어마어마해짐
- 매번 루프를 도는 경우 더해야하는 범위가 커지거나, 배열 사이즈의 크기가 클수록 시간의 낭비가 어마어마해짐
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int day = scan.nextInt();
int cnt = scan.nextInt();
int[] a = new int[day];
for(int i=0; i<day; i++){
a[i] = scan.nextInt();
}
System.out.print(t.solution(a,cnt));
}
public int solution(int[] a, int b){
int result = 0;
int sum = 0;
for (int i=0; i<b; i++){
sum += a[i];
}
int sp=0, ep=sp+b;
result = sum;
while(ep<a.length){
sum = sum-a[sp++]+a[ep++];
result = Math.max(result, sum);
}
return result;
}
}
- 특징
- 최초에 0부터 지정범위만큼의 합을 구해놓음
- 시작포인트와 끝포인트를 정해서 배열이 끝나기전까지 이전 합계에서 기존시작점은 빼고, 새로운끝점은 더하는 식으로 연산
- 새로 집계한 합계와 기존 최대값을 비교
- 최초에 0부터 지정범위만큼의 합을 구해놓음
연속 부분수열 (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가지입니다.
-
입력 : 첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다. 수열의 원소값은 1,000을 넘지 않는 자연수이다.
-
출력 : 첫째 줄에 경우의 수를 출력한다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int sum = scan.nextInt();
int[] a = new int[num];
for(int i=0; i<num; i++){
a[i] = scan.nextInt();
}
System.out.print(t.solution(a,sum));
}
public int solution(int[] a, int b){
int result = 0;
int sum;
for (int i=0; i<a.length; i++){
sum=a[i];
if(sum==b) result++;
if(sum<b){
for(int j=i+1; j<a.length; j++){
sum += a[j];
if(sum>b) break;
if(sum==b) {
result++;
break;
}
}
}
}
return result;
}
}
- 특징
- O(N^2^)의 시간소요가 되며 굉장히 비효율적임
- O(N^2^)의 시간소요가 되며 굉장히 비효율적임
- 풀이 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int sum = scan.nextInt();
int[] a = new int[num];
for(int i=0; i<num; i++){
a[i] = scan.nextInt();
}
System.out.print(t.solution(a,sum));
}
public int solution(int[] a, int b){
int result = 0;
int sum=0, lt=0;
for(int rt=0; rt<a.length; rt++){
sum += a[rt];
if(sum==b) result++;
while(sum>=b) {
sum -= a[lt++];
if(sum==b) result++;
}
}
return result;
}
}
- 특징
- 시작점과 끝점을 포인트로 잡고
- 시작과 동시에 끝점 0을 추가
- 목표값과 같으면 카운트 추가
- 목표값보다 현재 수가 크면 while문 반복 (여러개를 빼야할수도 있으니 while임)
- 시작점을 한칸씩 빼고, 새로 계산 할때마다 조건문 체크도 같이 진행
- while문을 벗어나면 다시 끝점 추가 반복
- 시작점과 끝점을 포인트로 잡고