섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] 2. 공통원소구하기

문제

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

입력

• 첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
• 두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
• 세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
• 네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
• 각 집합의 원소는 1,000,000,000이하의 자연수입니다.

출력

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

입출력 예제

---

풀이 방식을 정리해보자.

 

1. 먼저 배열 A[N] 와 B[M] 를 선언하고, 값을 입력받는다.

 

2. 바로 메소드 구현으로 넘어가보자.

 

3. 배열로 결과값을 출력할 것이기에 ArrayList 형으로 메소드를 선언한다.

 

4. Arrays.sort() 를 이용해서 각 배열안에 인자 값들을 오름차순으로 정렬한다.

• Arrays.sort() : 베열을 자동으로 오름차순으로 정렬해준다.

5. 각 배열에서 사용할 포인터 p1, p2 를 선언하고 0으로 초기화한다.

• 인덱스와 비슷한 개념이라고 간단히 이해하고 넘어가자.

6. 두 배열 중 하나라도 배열의 마지막에 이르면 종료하도록 while 문을 작성한다.

• N은 a[ ] 배열의 최대개수이고 M은 b[ ] 배열의 최대개수이므로 전부 다 돌았으면 종료해야 한다.

7. 두 배열에 동일한 값이 있으면 둘 중 하나의 배열에 값을 결과값 배열에 넣어주고, 두 배열에 포인터를 증가시킨다.

 

8. 두 배열중에 더 작은 값이 있으면, 작은 값이 있는 배열만 포인터를 증가시킨다.

• A[ ] = 1, 2, 3 / B[] = 2, 3, 4 이라고 가정해보자.
• A[ ]에서 1이 더 작으므로 1을 결과값 배열에 넣는다.
• 이 때에 B[ ] 배열에 2 가 있는데, 이 값이 A[ ] 배열에 있으므로 A[1] 과 B[0] 을 비교해야한다.
• 즉, B[ ] 배열에 포인터는 증가하면 안된다. 

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.