자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 3. Two pointers, Sliding window(1)

 

1. 두 배열 합치기

 

<나의 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine()); //1<=n<=100
		String s=br.readLine();
		
		StringTokenizer st=new StringTokenizer(s);
		List<Integer> nList=new ArrayList<>();
		
		while(st.hasMoreTokens()) {
			nList.add(Integer.parseInt(st.nextToken()));
		}

		int m=Integer.parseInt(br.readLine()); //1<=m<=100
		s=br.readLine();
		st=new StringTokenizer(s);
		
		while(st.hasMoreTokens()) {
			nList.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(nList);
		
		StringBuilder sb=new StringBuilder();
		for(int num:nList) {
			sb.append(num+" ");
		}
		
		System.out.println(sb.toString().trim());
		
	}

}

 

<해설>

- 정렬해서 풀수 있지만 출제자의 의도는 Two Pointer 알고리즘이다.

- a배열과 a배열 포인터 p1, b배열과 b배열 포인터 p2를 사용

import java.util.*;

class Main {	
	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++]);
			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){
		Main T = new Main();
		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+" ");
	}
}

 

---

 

2. 공통원소 구하기

 

<나의 풀이>

-time limit

: 1000ms 제한인데, 최대 input수로 테스트 했을 때 1400ms 정도 걸림

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine()); //1<=n<=30000
		String s=br.readLine();
		
		StringTokenizer st=new StringTokenizer(s);
		List<Integer> nList=new ArrayList<>();
		
		while(st.hasMoreTokens()) {
			nList.add(Integer.parseInt(st.nextToken()));
		}

		int m=Integer.parseInt(br.readLine()); //1<=m<=30000
		s=br.readLine();
		st=new StringTokenizer(s);
		List<Integer> mList=new ArrayList<>();
		
		while(st.hasMoreTokens()) {
			int mNum=Integer.parseInt(st.nextToken());
			if(nList.contains(mNum)){
				mList.add(mNum);
			}
		}
		
		Collections.sort(mList);
		
		StringBuilder sb=new StringBuilder();
		for(int num:mList) {
			sb.append(num+" ");
		}
		
		System.out.println(sb.toString().trim());
	}

}

 

<해설>

- 오름차순으로 해야 투포인터 알고리즘 사용가능

import java.util.*;
class Main {	
	public ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
		ArrayList<Integer> answer = new ArrayList<>();
		Arrays.sort(a);
		Arrays.sort(b);
		int p1=0, p2=0;
		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){
		Main T = new Main();
		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. 최대 매출

 

<나의 풀이>

- 이중 반복하면 시간복잡도가 O(N^2) 

최대 N,M=100,000 이기 때문에 1초가 넘어감 -> TIME OVER

=> Sliding Window를 사용하여 시간복잡도 O(N)로 해결 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s=br.readLine();
		StringTokenizer st=new StringTokenizer(s);
		
		int n=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		
		s=br.readLine();
		st=new StringTokenizer(s);
		
		int[] nums=new int[n];
		
		for(int i=0;i<n;i++) {
			nums[i]=Integer.parseInt(st.nextToken());
		}
		
		int lIdx=0;
		int rIdx=k-1;
		
		int sum=0;
		
		//초기 sum
		for(int i=0;i<k;i++) {
			sum+=nums[i];
		}
		
		//초기 maxSum
		int maxSum=sum;
			
		while(rIdx<n-1) {
			sum-=nums[lIdx];
			sum+=nums[rIdx+1];
			
			if(sum>maxSum) maxSum=sum;
			
			lIdx++;
			rIdx++;
		}
		
		System.out.println(maxSum);
	}

}

 

<해설>

import java.util.*;
class Main {	
	public int solution(int n, int k, int[] arr){
		int answer, 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){
		Main T = new Main();
		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.print(T.solution(n, k, arr));
	}
}