[TIL] 시간복잡도와 싸운 날

기면지·2021년 8월 4일

TIL algorithm

TIL

목록 보기

2/10

안녕하세요!
오늘은 하루종일 알고리즘 문제만 풀었는데요 ㅎ.ㅎ
푼 알고리즘 중에서 시간 고려하느라 애썼던 문제 풀이를 적어보겠습니다.

문제

요약
이 문제는 주어진 N개의 수를 자신보다 작은 숫자가 몇 개 있는지 계산해서 값을 갱신하는 문제입니다.

주의할 점

여기에서, N 이 최대 1,000,000 이라는 것에 집중해야 합니다.
이 상황에서 시간복잡도는 O(N^2) 이 된다면 시간 초과가 발생할 것입니다.
즉, for 문 순회를 중복으로 하면 안된다는 의미일 것입니다.

처음 생각한 방법

입력받은 N 개의 수는 배열로 만들고, Set 을 활용해서 중복을 없앤 배열을 만들어서 계산하자!

위와 같이 생각했지만.. 한 가지 놓친 부분이 있습니다.
바로 Set 은 순서가 존재하지 않아서 반복문으로 순회하면서 배열의 값보다 작은 값인지 체크하는 과정이 필요합니다.
이 과정에서 중복 for 문이 발생하게 되겠네요!

두번째로 생각한 방법

Set 이 안된다면,, Map 을 활용해서 값을 key 로 놓고, key 가 존재한다면 Map 에 저장하지 않고 건너뛰자!

이 방향으로 알고리즘을 풀어갔습니다.
Map 의 containsKey 나, get(key) 와 같은 메소드들의 시간복잡도는 O(1) 이기 때문에 Set 보다 효율적이라는 생각을 했습니다.

코드 설명

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 숫자와 인덱스를 담을 배열 (인덱스 = 자신보다 작은 숫자의 수)
Map<Integer, Integer> map = new HashMap<>();
int N = Integer.parseInt(br.readLine());
int[] numbers = new int[N]; // 입력 배열 저장

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

입력 값들을 받고, 처리하는 부분입니다.
N 이 클 경우를 대비해 Scanner 대신 BufferedReader 를 사용했습니다.
또한, StringBuilder 로 출력 시간도 최소화했습니다.
값을 저장할 Map 과 배열을 선언하고, 숫자들을 배열에 넣기 위해 StringTokenizer 를 활용했습니다.

// 입력 배열 초기화
for (int i = 0; i < N; i++) {
    numbers[i] = Integer.parseInt(st.nextToken());
}

입력으로 받은 숫자들로 배열을 초기화해줍니다.

// 정렬된 배열 추가로 생성
int[] sort_numbers = numbers.clone();
Arrays.sort(sort_numbers);

Map 에 key 는 숫자로, value 는 index 로 설정할 것이기 때문에 정렬을 먼저 해줍니다.
이 때, 원본 배열을 건들지 않도록 새로운 배열에 clone 메소드를 활용해 복사해줬습니다.

// index를 추가해가며 map에 숫자 저장
int index = 0;
for (int num: sort_numbers) {
    if (!map.containsKey(num)) {
        map.put(num, index++);
    }
}

index 를 선언하고, 이 값을 하나씩 늘려가면서 Map 에 저장해줍니다.
이 index 부분이 key 에 저장된 값보다 작은 숫자의 개수가 되겠죠!
앞서 말씀드렸던 것처럼 containsKey() 를 활용해 중복은 없애줍니다.

// key로 찾아오면 value는 index 값, 즉 자신보다 작은 숫자의 개수일 것
for (int i = 0; i < N; i++) {
    sb.append(map.get(numbers[i]) + " ");
}

System.out.println(sb.toString());

그 후에는 따로 처리하지 않고, 원본 배열 순서대로 값을 이용해 map 의 value 인 index 값을 가져와서 StringBuilder 에 덧붙여줍니다.
마지막으로 sb 를 출력하면 출력까지 완성입니다.

전체 코드

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

/**
 * 백준 18870 좌표압축
 *
 * 접근 방법 :
 * N이 1,000,000 이었기 때문에, O(N^2) 알고리즘을 구현하면 시간 초과가 발생할 것이다.
 * 따라서, for문을 두 번 순회하지 않고도 답을 도출할 수 있도록 했다.
 * Set 또는 Map 을 사용해야겠다는 생각을 했고, Set 또한 순회하면서 값을 찾아야하기 때문에
 * key를 사용하는 Map으로 구현했다.
 * 입력으로 들어온 숫자 배열을 sorting한 후, number와 index를 map에 순서대로 저장했다.
 *
 * 시간복잡도 :
 * Arrays.sort() 에서 퀵 정렬의 시간복잡도인 O(NlogN)
 */

public class b18870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 숫자와 인덱스를 담을 배열 (인덱스 = 자신보다 작은 숫자의 수)
        Map<Integer, Integer> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N]; // 입력 배열 저장

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 입력 배열 초기화
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        // 정렬된 배열 추가로 생성
        int[] sort_numbers = numbers.clone();
        Arrays.sort(sort_numbers);

        // index를 추가해가며 map에 숫자 저장
        int index = 0;
        for (int num: sort_numbers) {
            if (!map.containsKey(num)) {
                map.put(num, index++);
            }
        }

        // key로 찾아오면 value는 index 값, 즉 자신보다 작은 숫자의 개수일 것
        for (int i = 0; i < N; i++) {
            sb.append(map.get(numbers[i]) + " ");
        }

        System.out.println(sb.toString());
    }
}