문제

https://www.acmicpc.net/problem/18870

<예제>
5
2 4 -10 4 -9  				2 3 0 3 1

나의 풀이

1. 배열에 좌표를 저장
2. 배열을 set으로 변환하여 중복값을 없애고 정렬을 하기 위해 다시 배열로 변환하여 정렬
3. 정렬 순서에 맞게 해당 값이 몇번째에 있는 지를 반환하는 문자열 생성

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Integer[] arr = new Integer[N];                      // 원래 좌표 저장 배열
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i <N ; i++) {
            int n = Integer.parseInt(st.nextToken());
            arr[i] = n;
        }

        HashSet<Integer> set = new HashSet<>(Arrays.asList(arr)); // 좌표 배열을 set으로 저장
        Integer[] arr_1 = set.toArray(new Integer[0]);            // 정렬할 수 있게 배열로 바꿈
        Arrays.sort(arr_1);                                       // {-10, -9, 2, 4}

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(Arrays.asList(arr_1).indexOf(arr[i])).append(" ");
        }

        System.out.println(sb);
    }
}

• 답은 나왔지만 StringBuilder와 BufferedReader를 사용해도 시간초과가나왔다.
• 찾아보니 Map으로 풀어야한다는 답이 많아 고쳐보기로 했다.

다른 풀이

- Map을 활용하여 해당 값과 그 값의 index를 저장
- 그 값을 stringbuilder에 추가하여 출력

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

public class Prac{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];                   // 원래 좌표 저장 배열
        int[] arr_1 = new int[N];                 // 저장 배열 정렬용 배열
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i <N ; i++) {
            int n = Integer.parseInt(st.nextToken());
            arr[i] = arr_1[i] = n;
        }

        Arrays.sort(arr_1);                      // {-10, -9, 2, 4, 4}
        
        Map<Integer, Integer> map = new HashMap<>();
        int rank = 0;

        for (int i : arr_1) {
            if (!map.containsKey(i)) {
                map.put(i, rank);
                rank++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(map.get(i)).append(" ");
        }

        System.out.println(sb);
    }
}

• map으로 저장하여 출력하니 시간 초과로 나오던 위 풀이와 달리 정답처리 되었다.
• 바뀐 부분은 set으로 만들고 배열로 변환 후 정렬, 리스트로 변환 후 index를 구하는 부분을 map으로 바꾸는 과정이 전부다
• 구체적으로 어떤 과정이 시간이 많이 걸리는 건지 알아봐야겠다.

시간 초과 이유

• array -> set -> array -> 정렬 -> list로 바꾸어 index 도출
• array -> set -> list -> 정렬 -> index 도출

  혹시나 싶어 과정을 줄여 다시 시도해봤지만 여전히 시간초과가 떴다.
  다른 사람들이 푼 과정을 보니 array -> set 이러한 과정을 쓰고도 통과된 분이 많았기에 index로 값을 도출해내는 과정이 시간이 오래걸린다고 짐작해본다.
  -> HashMap을 사용하여 성능을 높여야했던 문제였던 거 같다.

ArrayList 와 HashTable(HashMap)의 차이점

• ArrayList의 입력방식
  add(Object o), add(int index, Object o), set(int index, Object o)…etc
  데이터를 검색하기 위해서는 처음부터 끝까지 돌거나 사용자가 index를 알아야함
  index정보를 알고 있다면 ArrayList가 HashMap보다 빠름

• HashMap의 입력방식
  put(Object key, Object value)
  key 값을 Object로 갖고 있기에 자바에서 사용가능한 모든 클래스 가능
  (복잡한 값을 갖는 Object 도 키로 활용가능)
  키 값을 이용해 바로 원하는 정보를 얻어낼 수 있기에 검색능력이 탁월하다.

• 용도의 차이점
  ArrayList의 경우 단순히 데이터를 입력하고 데이터를 출력하는 용도로
  HashMap의 경우 데이터를 캐쉬해서 특정 key값으로 HashMap에 있는 데이터를 검색해서 사용하는 용도로 많이 쓰인다.

18870번 참고풀이
ArrayList와 HashTable