[코딩테스트] [10989] 수정렬하기3 & [3273] 두수의합

수 정렬하기 3

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

5 초 (하단 참고)

8 MB (하단 참고)

324390

77725

59315

23.852%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

문제풀이

이 문제는 저번에 풀었던 줄세우기와 유사한 문제로 입력받은 값을 배열로 받아 정렬을 해주는 문제이다.

이 문제의 시간복잡도와 공간복잡도를 생각해보자.

시간복잡도 & 공간복잡도

• 시간 제한은 5초이다. 만약 저번 줄세우기 문제를 풀었던 알고리즘을 적용한다면 시간복잡도가 어떻게 될까?
• 저번에 풀었던 알고리즘으로 푼다면 정렬된 답이 나오는 것을 볼 수 있다 하지만 제출을 눌러본다면 시간 초과가 발생하는 것을 알 수 있다. 이유는 반복문을 3번 돌면서 O(N) + O(N^2) = O(N^2)인데 N의 크기는 1 ≤ N ≤ 10,000,000이다. 즉 최대로 값을 넣는다고 가정하면 O(10,000,000^2)이다. (O(10,000,000^2))의 시간 복잡도를 가진 알고리즘은 약 100,000 초가 소요될 것으로 예상된다.
• 그리고 O(N)만큼 배열을 넣어주게 되는데 그러면 int는 4byte이니깐 4*10,000,000을 한다면 40,000,000 byte = 약 40MB이다
• 문제에서는 시간 제한 5초, 메모리 제한 8MB이기 때문에 초과가 된다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] res = new int[N];
        int cnt = 0;
        for(int i =0; i<N; i++) {
            res[i] = sc.nextInt();
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<i; j++) {
                if(res[j] > res[i]) {
                    int temp = res[i];
                    for (int k = i; k > j; k--) {
                        res[k] = res[k-1];
                    }
                    res[j] = temp;
                    break;
                }
            }
        }
        for(int i = 0; i<N; i++)
            System.out.println(res[i]);
    }
}

// ------ Input 
10
5
2
3
1
4
2
3
5
1
7
// ------- Output
1
1
2
2
3
3
4
5
5
7

주어진 수를 파악하기

• N에 들어갈 수 있는 수는 10,000보다 작거나 같은 자연수이다. 그렇다면 1~10,000까지의 배열을 만든다. 만약 입력받은 값들 중 1이 10개이고 2가 300개라면 배열의 0번째요소에 10을 추가하고 1번째요소에 300을 추가하면 1이 몇개가 있는지 2가 몇개가 있는지 알 수 있다 코드로 작성해보자.
• 아래 처럼 코드를 작성하면 입력받은 수가 몇개 있는지 알 수 있다.

  			int N = sc.nextInt();
        int[] cnt = new int[10001];
        
        for(int i=0; i<N; i++) {
            cnt[sc.nextInt()]++;
        }

정렬하여 출력하기

• 배열에 저장한 값을 정렬하여 출력하기 위해 반복문을 사용해서 출력해보자 0은 자연수가 아니니 1부터 시작하여 10000까지 반복을 해주자.
• 추가로 배열의 1번째 요소가 5라면 1이 5개 있는 것이니 while문을 사용해서 반복하여 출력해주자..!
• 아래 이미지를 보면 답이 잘 정렬되는 것을 볼 수 있다 제출을 해보자!

        for(int i=1; i<10001; i++){
            while(cnt[i]-->0)
                System.out.println(i);
        }

• 하지만 돌아오는 결과는 시간 초과..! 이유는 Scanner와 System.out.print에 있다. 15552번 문제 빠른 A+B를 보면 아래처럼 작성되어 있다.

💡 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다. 

BufferedReader와 BufferedWriter를 사용

• BufferedReader와 BufferedWriter를 사용하면 에러 예외처리를 하여 혹시 모를 입출력 에러를 throws 해주기 위해 throws IOException를 사용해주고 br.flush()를 사용해 출력해주자.

import java.io.*;

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));        
        
        int N = Integer.parseInt(br.readLine());
        int[] cnt = new int[10001];
        
        for(int i=0; i<N; i++) {
            cnt[Integer.parseInt(br.readLine())]++;
        }
        for(int i=1; i<10001; i++){
            while(cnt[i]-->0)
                bw.write(i + "\\n");
        }
        bw.flush();
    }
}

두수의합

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

68503

24622

17943

34.435%

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

문제풀이

1. 입력 받기

• 일단 n과 수열에 포함되는 수, x를 입력받자 (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
• 수열은 int 배열에 저장해야 하는데 입력을 string 배열로 받고 반복문을 사용하여 int배열에 저장해주자.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] stringNumbers = br.readLine().split(" ");
        int x = Integer.parseInt(br.readLine());

        int[] numbers = new int[n];
        for(int i=0; i<n; i++) {
            numbers[i] = Integer.parseInt(stringNumbers[i]);
        }

2. 입력받은 배열을 정렬하고 투포인터를 사용하여 값을 찾자.

• 정렬을 하는 이유는 투 포인터를 사용하기 때문인데 조건 ai + aj = x (1 ≤ i < j ≤ n)을 만족해야 하기 때문에 포인터를 사용해서 만족 시킬 것이다.
• count, left, right를 만드는데 right는 n-1로 배열 끝에서부터 올 수 있도록 한다.
• 배열의 left요소와 right를 더한값이 x라면 count++,left++,right—
• left++와 right—를 하는 이유는 중복 계산을 피하기 위해서이다. (1 ≤ i < j ≤ n)조건 만족

        Arrays.sort(numbers);

        int count = 0;
        int left = 0;
        int right = n-1;

        while(left<right) {
            if (numbers[left]+numbers[right] == x) {
                count++;
                left++;
                right--;
            } else if (numbers[left]+numbers[right] < x) {
                left++;
            } else {
                right--;
            }
        }
        bw.write(count + "\\n");
        bw.flush();

전체 시간 복잡도

• 입력 처리: (O(n))
• 정렬: (O(n \log n))
• 투 포인터 탐색: (O(n))
• 즉, O(n) + O(n \log n) + O(n) = O(n \log n) = O(n)이다.