[백준] 1822 java 풀이법

분류가 어떻게 되는지는 모르겠다.

일단 풀이 방법은 각 배열 aSet, bSet을 오름차순으로 정렬해주고,

정렬한 후 aSet을 bSet과 비교하며

aSet의 각 원소가 bSet의 비교 대상 원소보다 클 때에는 bSet의 포인터를 1 증가하고, 

bSet의 원소가 aSet의 원소보다 클 때에는 결과 셋에 저장하면서 aSet의 포인터를 1 증가,

aSet의 원소와 bSet의 원소의 값이 동일하다면 두 포인터 모두 증가시키는 방법으로 수행했다.

 

예시를 가지고 설명한다면

 

4 3

2 5 11 7

9 7 4

 

에서 정렬을 하고 나면

 

2 5 7 11

4 7 9

 

가 될 것이고,

 

2부터 비교를 시작한다면

 

2<4   => 2를 결과 셋에 저장 후 aSet 포인터 1 증가,

5>4   => bSet의 포인터를 1 증가,

5<7   => 5를 결과 셋에 저장 후 aSet 포인터 1 증가,

7==7 => 두 포인터 모두 1 증가,

11>9 => 11을 결과 셋에 저장 후 aSet 포인터 1 증가,

 

이후 반복문이 종료되도록 설정했다.

 

만약 aSet의 데이터가 남았는데 bSet에서 더 이상 검색할 원소가 없다면

aSet의 나머지 데이터를 결과 셋에 모두 저장하도록 설정했다.

만약 예시 데이터에서 aSet에 9가 있었다면 7==7 이후 9==9가 됐을 것이고

bSet에 더 이상 데이터가 없기 때문에 검색을 수행할 수 없고,

aSet의 나머지 데이터들은 모두 bSet의 모든 데이터보다 클 것이기 때문이다.

근거로는 문제에 나와있던 "하나의 집합에 속하는 모든 원소의 값은 다르다"이다.

 

소스 코드는 다음과 같다.

 

ArrayList<Integer> resSet = new ArrayList<>();
Arrays.sort(aSet);
Arrays.sort(bSet);
            
int aPointer=0;
int bPointer=0;
        
while(aPointer<n){
    if(bPointer<m){
        if(aSet[aPointer]>bSet[bPointer]){
            bPointer++;
        } else if (aSet[aPointer]==bSet[bPointer]){
            aPointer++;
            bPointer++;
        } else {
            resSet.add(aSet[aPointer++]);
        }
    } else {
        resSet.add(aSet[aPointer++]);
    }
}
 
StringBuffer sb = new StringBuffer();
sb.append(resSet.size()).append("\n");
for(int num : resSet) {
    sb.append(num).append(" ");
}
System.out.println(sb.toString());

 

이렇게 푸니 결국엔 맞췄다.