본문 바로가기
Java/Java 알고리즘 인프런

[Ch.03 - 투 포인터] 2. 공통원소 구하기 (+하나씩 확인하는 방법)

앤 썸 2022. 5. 9. 14:27
728x90
반응형

2.공통원소 구하기
두 개의 집합에서 공통 원소를 추출하여 오름차순으로 출력

 

입력값

5
1 3 9 5 2
5
3 2 5 7 8

 

출력값

2 3 5 

 

import java.util.*;
  
public class Main {
  public ArrayList<Integer> solution(int[] arr1, int[] arr2){
    ArrayList <Integer> list = new ArrayList<>();
    for(int i=0;i<arr1.length;i++){
      for(int j=0;j<arr2.length;j++){
        if(arr1[i]==arr2[j]){
          list.add(arr1[i]);
        }
      }
    }
    Collections.sort(list);
    return list;
    
  }
  public static void main(String[] args){
    Main T=new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int [] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=kb.nextInt();
    }
    int m=kb.nextInt();
    int [] arr2 = new int[m];
    for(int i=0;i<n;i++){
      arr2[i]=kb.nextInt();
    }
    for(int x: T.solution(arr1, arr2)){
      System.out.print(x +" ");
    }
  }
}

-> 타임리밋 발생

 

 

#타임리밋 방지 -> 포인터를 사용해 케이스 분류

1. 각 배열을 정렬 시킨다. -> Arrays.sort();

2. while(p1<n && p2<m)

포인터가 모두 범위 안일 경우 계속 반복

3. if(a[p1]<b[p2])

p2가 p1보다 가리키는 값이 크면 p1을 증가시킨다.

4. if(a[p1]>b[p2])

p1이 p2보다 가리키는 값이 크면 p2를 증가시킨다.

5. if(a[p1]==b[p2])

p1와 p2가 가리키는 값이 같으면, 결과 리스트에 추가하고, p1와 p2를 증가시킨다.

package twopointer.ch03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Twopointer02_1 {

	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]) {
				p1++;
				continue;
			}
			if(a[p1]>b[p2]) {
				p2++;
				continue;
			}
			if(a[p1]==b[p2]) {
				answer.add(a[p1]);
				p1++;
				p2++;
				continue;
			}
		}
		
		return answer;
		
	}

	public static void main(String[] args) {
		Twopointer02_1 T= new Twopointer02_1();
		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+" ");
		}
		

	}

}

 

+) 세련된 풀이

-> 지그재그로 하나씩 검사하면서, 배열을 확인하고, 같은 경우 리스트에 넣는다.

 

1. 각 배열을 정렬 시킨다. -> Arrays.sort();

2. while(p1<n && p2<m)

포인터가 모두 범위 안 일 경우 계속 반복

3. if(a[p1]==b[p2]) {

배열의 값이 같을 경우, p1의 배열의 값을 넣고, p1, p2포인터 증가

4. else if(a[p1]<b[p2])

p2의 배열의 값이 크면, p1포인터 증가

5. else

p1의 배열의 값이 크면, p2포인터 증가 

package twopointer.ch03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Twopointer02 {
	//공통원소 구하기
	//두 개의 집합에서 공통 원소를 추출하여 오름차순으로 출력
	public static void main(String[] args) {
		Twopointer02 T = new Twopointer02();
		Scanner kb = new Scanner(System.in);
		
		//집합 1
		int n=kb.nextInt();
		int[] a=new int[n];
		
		for(int i=0;i<n;i++)
			a[i]=kb.nextInt();
		
		//집합 2
		int m=kb.nextInt();
		int[] b= new int[m];
		
		for(int i=0;i<m;i++)
			b[i]=kb.nextInt();
		kb.close();
		System.out.println(T.solution(n,m,a,b));
	}
	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;
		//집합 1 포인터, 집합2 포인터
		
		while(p1<n && p2<m) {
			//집합1과 집합2 모두 크기 내 일 경우
			if(a[p1]==b[p2]) {
				answer.add(a[p1++]);
				p2++;
				//배열의 값이 같을 경우, p1의 배열의 값을 넣고, p1, p2포인터 증가
			}
			else if(a[p1]<b[p2])
				p1++;
			//p2의 배열의 값이 크면, p1포인터 증가
			else
				p2++;
			//p1의 배열의 값이 크면, p2포인터 증가
			
			//즉, 지그재그로 하나씩 검사하면서, 배열을 확인하고, 같은 경우 리스트에 넣는다.
		}
		return answer;
	}
	
}

 

1. Map에 모두 삽입

2. 2개이상인 숫자들 리스트에 넣기

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    int m = in.nextInt();
    int[] arr2= new int[m];
    for(int j=0;j<m;j++){
      arr2[j]=in.nextInt();
    }
    solution(n,m,arr1,arr2);
  }
  static void solution(int n, int m, int[] arr1, int[]arr2){
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0;i<n;i++){
      map.put(arr1[i],map.getOrDefault(arr1[i],0)+1);
    }
    for(int i=0;i<m;i++){
      map.put(arr2[i],map.getOrDefault(arr2[i],0)+1);
    }
    ArrayList<Integer> list = new ArrayList<>();
    for(int x:map.keySet()){
      if(map.get(x)>=2) list.add(x);
    }
    Collections.sort(list);
    for(int x:list) System.out.print(x+" ");
  }
}

1. 단순 이중for문 이용 : 타임리밋 발생

2. 정렬을 하고, 이중for문을 돌면서 더 큰 값이 나오면 break;

3. for while문으로 변경

4. while문 하나로 변경

 

1. 단순 이중for문 이용 : 타임리밋 발생

import java.util.*;;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=0;i<n;i++){
      for(int j=i;j<m;j++){
        if(arr1[i]==arr2[j]) list.add(arr1[i]);
      }
    }
    for(int x: list) System.out.print(x+" ");
  }
}

 

2. 정렬을 하고, 이중for문을 돌면서 더 큰 값이 나오면 break;

import java.util.*;;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    int rt=0;
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=0;i<n;i++){
      for(int j=rt;j<m;j++){
        rt=j;
        if(arr1[i]==arr2[j]) list.add(arr1[i]);
        else if (arr2[j]>arr1[i]) break;
      }
    }
    for(int x: list) System.out.print(x+" ");
  }
}

 

3. for-while문으로 변경

import java.util.*;;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    int rt=0;
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=0;i<n;i++){
      while(rt<m){
        if (arr2[rt]>arr1[i]) break;
        if(arr1[i]==arr2[rt]){
          list.add(arr1[i]);
        }
        rt++;
      }
    }
    for(int x: list) System.out.print(x+" ");
  }
}

 

4. while문 하나로 변경

import java.util.*;;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[] arr1 = new int[n];
    for(int i=0;i<n;i++){
      arr1[i]=in.nextInt();
    }
    int m=in.nextInt();
    int[] arr2= new int[m];
    for(int i=0;i<m;i++){
      arr2[i]=in.nextInt();
    }
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    ArrayList<Integer> list = new ArrayList<>();
    int lt=0, rt=0;
      while(lt<n&&rt<m){
        if (arr2[rt]>arr1[lt]) {
          lt++;

        }
        else if(arr1[lt]==arr2[rt]){
          list.add(arr1[lt]);
          lt++;
          rt++;
        }
        else rt++;

      }
    
    for(int x: list) System.out.print(x+" ");
  }
}

 

+) 03.02

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n1 = in.nextInt();
    int[] arr1 =new int[n1];
    for(int i=0;i<n1;i++){
      arr1[i]=in.nextInt();
    }
    int n2 = in.nextInt();
    int[] arr2 =new int[n2];
    for(int i=0;i<n2;i++){
      arr2[i]=in.nextInt();
    }
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    Main main= new Main();
    for(int x: main.solution(arr1, arr2)) 
      System.out.print(x+" ");
  }
  public ArrayList<Integer> solution(int[] arr1, int[]arr2){
    int p1 = 0;
    int p2 = 0;
    ArrayList<Integer> list = new ArrayList<>();
    while(p1!=arr1.length && p2!=arr2.length){
      if(arr1[p1]==arr2[p2]){
        list.add(arr1[p1++]);
        p2++;
      }
      else if(arr1[p1]<arr2[p2]){
        p1++;
      }
      else{
        p2++;
      } 
    }
    return list;
  }
}
728x90
반응형
저작자표시 비영리

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

[Ch.01 - String] 01. 문자 찾기 (+ toCharArray)  (0) 2022.05.12
[Ch.03 - 투 포인터] 6. 최대 길이 연속부분수열 ###  (0) 2022.05.09
[Ch.03 - 투 포인터] 5. 연속된 자연수의 합 # (+ for-while)  (0) 2022.05.09
[Ch.03 - 투 포인터] 4. 연속 부분수열 ##  (0) 2022.05.09
[Ch.03 - 투 포인터] 3. 최대 매출 (+ 슬라이딩 윈도우)  (0) 2022.05.09

'Java/Java 알고리즘 인프런' Related Articles

티스토리툴바