유형
1.두 배열 합치기
//문제
두 배열을 오름차순으로 합치는 문제
//입력
3
1 3 5
5
2 3 6 7 9
//출력
1 2 3 3 5 6 7 9public class TS1 {
public static 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++]);
else if(a[p1]>b[p2]) answer.add(b[p2++]);
else answer.add(b[p2++]);
}
while(p1<n) answer.add(a[p1++]);
while(p2<m) answer.add(b[p2++]);
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
int n2 = sc.nextInt();
int[] arr2 = new int[n2];
for(int i=0; i<n2; i++){
arr2[i] = sc.nextInt();
}
for(int x:solution(n,n2,arr,arr2)){
System.out.print(x + " ");
}
}
}풀이
1.쉬운 문제를 풀더라도 입력값에 의해서 런타임 날 수가 있다.
2.시간 복잡도를 고려해서 for문으로 다 도는게 아닌, while문으로 필요한 조건에서만 반복하는게 좋다.
3.p1,p2 투 포인터를 이용해 비교해가면서 값을 저장한다.
[ 주요 기능 ]
Arrays.sort() : 배열을 정렬한다.
Collections.sort() : 리스트나 동적 배열을 정렬한다.
2.공통 원소 구하기
//문제
두 배열의 공통원소를 추출하는 문제
//입력
5
1 3 9 5 2
5
3 2 5 7 8
//출력
2 3 5public class TS2 {
public static ArrayList<Integer> solution(int n, int n2, int[] arr, int[] arr2){
ArrayList<Integer> answer = new ArrayList<>();
int p1=0,p2=0;
Arrays.sort(arr);
Arrays.sort(arr2);
while(p1<n && p2<n2){
if(arr[p1] == arr2[p2]){
answer.add(arr[p1]);
p1++;
p2++;
}
else if(arr[p1] < arr2[p2]) p1++;
else if(arr[p1] > arr2[p2]) p2++;
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
int n2 = sc.nextInt();
int[] arr2 = new int[n2];
for(int i=0; i<n2; i++){
arr2[i] = sc.nextInt();
}
for(int x:solution(n,n2,arr,arr2)){
System.out.print(x + " ");
}
}
}풀이
1.p1,p2변수를 선언한다. 그리고 입력받은 배열을 오름차순 정렬한다.
2.while문을 이용해서 p1,p2를 증가하면서 비교하면서 값을 answer에 저장한다. 이때 배열의 크기는 모르기 때문에 동적 배열이다.
[ 주요 기능 ]
Arrays.sort() : 정렬
while문 : 시간 복잡도 상 for문 보다는 while문이 좋다.
3.최대 매출
//문제
k일 동안의 최고 매출을 구하는 문제
//입력
10 3
12 15 11 20 25 10 20 19 13 15
//출력
56public class TS3 {
public static int solution(int n, int k, int[] arr){
int answer =0;
int sum=0;
for(int i=0; i<k; i++) sum+=arr[i];
answer = sum;
//핵심 로직
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) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.println(solution(n,k,arr));
}
}풀이
1.k일의 최대값을 찾아야하는데 슬라이딩 윈도우 방식을 이용한다.
2.k개의 값씩 for문을 도는데 sum+=(arr[i]-arr[i-k])를 해준다.
3.Math.max()를 이용해서 더 큰 sum을 answer에 저장한다.
[ 주요 기능 ]
슬라이딩 윈도우 방식이 중요하다.
4.연속 부분 수열
//문제
입력되는 값이 만들어지는 부분 수열의 수를 구하라.
//입력
8 6
1 2 1 3 1 1 1 2
//출력
3public class TS4 {
public static int solution(int n, int m, int[] arr){
int answer =0;
int sum=0,lt=0;
for(int rt=0; rt<arr.length; rt++){
sum+=arr[rt];
if(sum==m) answer++;
while(sum>=m){
sum-=arr[lt];
lt++;
if(sum==m) answer++;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.println(solution(n,m,arr));
}
}풀이
1.배열의 lt rt를 둬서 입력된 값을 sum으로 두고 rt를 증가시키면서 sum을 더한다.
2.sum==m이면 answer++ 하고 아니면 while문을 이용해서 뒤에있던 lt를 sum에서 빼고 lt++ 해줘서 계속 rt를 쫓아가게 한다. 그러면서 계속 sum이 m인지 아닌지 체크한다.
5.연속된 자연수의 합
//문제
자연수 n이 주어지면 그 n을 연속된 2개 이상의 숫자로 만들 수 있는 경우의 수
//입력
15
//출력
3public class ex5 {
public static int solution(int n){
int answer =0;
int lt=0,rt=0;
int sum=0;
int arr[] = new int[n];
for(int i=0; i<n; i++) arr[i]=i+1;
//인덱스 0번 값은 1부터 시작이기 때문에 n-1까지만 돌아야
//자기 자신 값을 제외할 수 있다.
for(rt=0; rt<n-1; rt++){
sum+=arr[rt];
if(sum == n) answer++;
while(sum >= n){
sum-=arr[lt];
lt++;
if(sum==n) answer++;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(solution(n));
}
}풀이
1.arr배열에 n길이 만큼의 배열을 만들어 준다. 0번 인덱스는 1부터 시작
2.rt를 돌리고 lt가 rt를 쫓아가는 Sliding 알고리즘 방식
3.for문으로 n자기 자신을 제외하기 위해서 n-1까지 돌려준다.
4.sum에 계속 더하면서 n보다 더 크면 lt를 빼고 lt++하면서 계속 진행한다.
6.최대 길이 연속 부분 수열
//문제
주어진 0과 1로 이루어진 배열에서 k번 만큼의 0->1 로
숫자 변화를 통해서 만들 수 있는 가장 긴 1의 길이
//입력
14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1
//출력
8public class ex6 {
public static int solution(int n, int k, int[] arr){
int answer =0;
int cnt=0,rt=0,lt=0;
for(rt=0; rt<arr.length; rt++){
if(arr[rt] == 0) cnt++;
while(cnt>k){
if(arr[lt]==0) cnt--;
lt++;
}
answer = Math.max(answer, rt-lt+1);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.println(solution(n,k,arr));
}
}풀이
1.연속된 1의 길이가 긴 최대 길이를 찾는문제
2.lt,rt를 이용해서 쭉 가다가 rt가 0을 만나면 cnt++
3.while문으로 cnt>k 이면 cnt를 감소시켜야한다 -> lt를 이용한다.
4.lt가 0인 부분을 지나면 다시 cnt-- 를 해준다.
5.이러한 원리로 Math.max()를 이용해 최대 길이를 구한다.
