11728번 문제

문제

풀이

익숙한 문제라서 크게 고민하지 않고 코드를 짰다.
투포인터를 이용하여 두 배열을 계속해서 대소를 비교해나가며 새로운 배열에 저장하였다.

첫 번째 시도

package twopointers;

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

public class Boj11728 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); 
        int m = Integer.parseInt(st.nextToken());
        int arr1[] = new int[n];
        int arr2[] = new int[m];
        int resultArr[] = new int[n+m];

        // 배열 초기화
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        // 두 배열 합치기
        int p1 = 0, p2 = 0;
        int idx = 0;
        while(p1<n && p2<m) {
            if(arr1[p1] == arr2[p2]) {
                resultArr[idx] = arr1[p1];
                idx++;
                p1++; p2++;
            } else if(arr1[p1] < arr2[p2]) {
                resultArr[idx] = arr1[p1];
                idx++; 
                p1++;
            } else {
                resultArr[idx] = arr2[p2];
                idx++;
                p2++;
            }
        }
        
        // 남은 배열 처리
        while(p1<n) {
            resultArr[idx] = arr1[p1];
            idx++; 
            p1++;
        }
        while(p2<m) {
            resultArr[idx] = arr2[p2];
            idx++;
            p2++;
        }

        // 출력
        for(int i=0; i<resultArr.length; i++) {
            System.out.print(resultArr[i]+" ");
        }
    }
}

그런데 결과는 ..

시간초과 ?..
시간복잡도가 O(n+m)밖에 안 나오는 코드인데 어떻게 시간초과가 나올 수 있지...?

두 번째 시도

입출력 문제인가 싶어서
BufferedReader와 System.out.print를 쓰던 반만 최적화된 코드를 BufferedWriter도 사용하도록 바꾸었다.

        // 출력
        for(int i=0; i<resultArr.length; i++) {
            bw.write(resultArr[i]+" ");
        }
        bw.flush();
        bw.close();

이렇게 바꾸니 다행히 시간초과는 뜨지 않고, 대신 ..

걍 틀림

세 번째 시도

문제를 풀면서 조금 모호했던 부분이
'만일 두 배열에 중복된 원소가 있다면?' 이었다.
여기서 제대로 생각 안 하고 p1++; p2++;를 했던 것이 틀렸었다.
이 사실을 아래 테케를 돌려보고 알아냈다.

2 2
-1 0
0 1

두 배열에 중복된 원소가 있으면, 그대로 결과 배열에 두 번 다 넣어주면 된다.
p1++; p2++; 두 개 중 하나만 보존하면 되는데, 난 그냥 p1를 남겨뒀다.

결론적으로 p2++; 부분을 삭제하고 제출했더니 통과 !

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); 
        int m = Integer.parseInt(st.nextToken());
        int arr1[] = new int[n];
        int arr2[] = new int[m];
        int resultArr[] = new int[n+m];

        // 배열 초기화
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        // 두 배열 합치기
        int p1 = 0, p2 = 0;
        int idx = 0;
        while(p1<n && p2<m) {
            if(arr1[p1] == arr2[p2]) {
                resultArr[idx] = arr1[p1];
                idx++;
                p1++;
            } else if(arr1[p1] < arr2[p2]) {
                resultArr[idx] = arr1[p1];
                idx++; 
                p1++;
            } else {
                resultArr[idx] = arr2[p2];
                idx++;
                p2++;
            }
        }
        
        // 남은 배열 처리
        while(p1<n) {
            resultArr[idx] = arr1[p1];
            idx++; 
            p1++;
        }
        while(p2<m) {
            resultArr[idx] = arr2[p2];
            idx++;
            p2++;
        }

        // 출력
        for(int i=0; i<resultArr.length; i++) {
            bw.write(resultArr[i]+" ");
        }
        bw.flush();
        bw.close();
    }
}

---

사실 BufferedReader를 쓰면서 sout은 그대로 쓰는게 좀 말이 안 되긴 했지만 그냥 귀찮아서 습관처럼 계속 써왔는데, 계속 앞으로는 sout을 버리고 BufferedWriter를 써어 풀어야겠다. 흑.
그리고 얼레벌레 코드 짜고 제출하는 버릇 좀 버리자 제 - 발