[코딩테스트] 공통원소 구하기

 

문제

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

 

출력

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

 

 

 

예시 입력

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

예시 출력

2 3 5

 

 

 

 

 

문제 풀이

 

[첫번째 풀이]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
  
public class Main {
  public ArrayList<Integer> solution(int[] m1, int[] m2) {
    Arrays.sort(m1);
    Arrays.sort(m2);

    ArrayList<Integer> result = new ArrayList<>();
    for (int m : m1) {
      for (int n : m2) {
        if (m == n) result.add(n);
      }
    }

    return result;
  }
  
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    
    int n1 = scanner.nextInt();
    int[] m1 = new int[n1];
    for (int i=0; i<n1; i++) {
      m1[i] = scanner.nextInt();
    }

    int n2 = scanner.nextInt();
    int[] m2 = new int[n2];
    for (int i=0; i<n2; i++) {
      m2[i] = scanner.nextInt();
    }

    Main main = new Main();
    for (Integer i : main.solution(m1, m2)) {
      System.out.print(i + " ");
    }
  }
}

(Time 1977ms / Memory 35MB) Time Limit Exceeded

 

[두번째 풀이]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
  
public class Main {
  public ArrayList<Integer> solution(int[] m1, int[] m2) {
    Arrays.sort(m1);
    Arrays.sort(m2);

    int j = 0;

    ArrayList<Integer> result = new ArrayList<>();
    for (int m : m1) {
      if (j < m2.length) {
        for (int i=j; i<m2.length; i++) {
          if (m == m2[i]) {
            result.add(m);
            j = i + 1;
            break;
          }
        }
      }
    }

    return result;
  }
  
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    
    int n1 = scanner.nextInt();
    int[] m1 = new int[n1];
    for (int i=0; i<n1; i++) {
      m1[i] = scanner.nextInt();
    }

    int n2 = scanner.nextInt();
    int[] m2 = new int[n2];
    for (int i=0; i<n2; i++) {
      m2[i] = scanner.nextInt();
    }

    Main main = new Main();
    for (Integer i : main.solution(m1, m2)) {
      System.out.print(i + " ");
    }
  }
}

(Time 1363ms / Memory 35MB) Time Limit Exceeded

 

[세번째 풀이]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
  
public class Main {
  public ArrayList<Integer> solution(int[] m1, int[] m2) {
    Arrays.sort(m1);
    Arrays.sort(m2);

    int j = 0;

    ArrayList<Integer> result = new ArrayList<>();
    for (int m : m1) {
      if (j < m2.length) {
        for (int i=j; i<m2.length; i++) {
          if (m == m2[i]) {
            result.add(m);
            j = i + 1;
            break;
          }

          if (m < m2[i]) break;
        }
      }
    }

    return result;
  }
  
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int n1 = scanner.nextInt();
    int[] m1 = new int[n1];
    for (int i=0; i<n1; i++) {
      m1[i] = scanner.nextInt();
    }

    int n2 = scanner.nextInt();
    int[] m2 = new int[n2];
    for (int i=0; i<n2; i++) {
      m2[i] = scanner.nextInt();
    }

    Main main = new Main();
    for (Integer i : main.solution(m1, m2)) {
      System.out.print(i + " ");
    }
  }
}

(Time 693ms / Memory 34MB)

 

 

 

- 첫번째 풀이에서 시간 초과로 실패가 떨어졌다. 뭐가 문제인가 보니 두 집합의 개수가 최대 30,000개까지 입력이 가능하다보니 이중 for 문을 돌면 비효율적인 시간이 들게 되어 있었다.

- 두번째 풀이에선 두번째 for 문의 시작점을 변수로 두고, 교집합에 속하는 숫자일 경우에 그 인덱스 값을 변수에 대입하여 불필요한 for 문이 돌지 않도록 하였다. 하지만 이것조차 Time Limit Exceeded가 떨어졌다.

- 그래서 세번째 풀이에서는 두번째 for 문에서 첫번째 집합의 숫자보다 크면 더이상 두번째 for 문을 돌지 않도록 하고 나니 성공했다.