[백준 / Java] 18870번 : 좌표 압축

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

18870번: 좌표 압축

 

---

◎ 문제

 

 

---

◎ 코드 및 풀이

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));
        StringBuilder sb = new StringBuilder();
 
        // 테스트 갯수 입력
        int n = Integer.parseInt(br.readLine());
 
        // 리스트 생성 후 입력받기
        Integer[] numArray = new Integer[n];
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < n; i++) {
            numArray[i] = Integer.parseInt(st.nextToken());
        }
 
        // 리스트 복사 후 정렬할 리스트 생성 (원본을 가지고 있어야 인덱스를 뽑아낼 수 있음)
        Integer[] numSortArray = numArray.clone();
        // 배열을 정렬
        Arrays.sort(numSortArray);
        // 인덱스를 저장할 맵 생성
        HashMap<Integer,Integer> numMap = new HashMap<Integer,Integer>();
 
        int index=0;
        // 정렬된 어레이를 키 값으로 맵에 넣어주는데 벨류에 인덱스를 하나씩 늘려가며 넣어준다.
        for(int i=0; i<n; i++) {
            if(!numMap.containsKey(numSortArray[i]))
                numMap.put(numSortArray[i], index++);
        }
        // 맵에서 원본의 값들의 벨류값을 꺼내 출력한다.
        for(int i=0; i<n; i++)
            sb.append(numMap.get(numArray[i])+" ");
 
        System.out.print(sb);
    }
}

 

 

---

◎ 기록

 

첫번째 도전했던 코드이다. 결과는 시간초과였다.

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));
        StringBuilder sb = new StringBuilder();
 
        // 테스트 갯수 입력
        int n = Integer.parseInt(br.readLine());
 
        // 리스트 생성 후 입력받기
        Integer[] numList = new Integer[n];
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < n; i++) {
            numList[i] = Integer.parseInt(st.nextToken());
        }
 
        // 리스트 복사 후 정렬할 리스트 생성
        Integer[] numSortList = numList;
 
        // 세트로 중복 제거
        Set<Integer> numSetSortList= new HashSet<Integer>(Arrays.asList(numSortList));
 
        // 다시 세트를 배열로
        numSortList = numSetSortList.toArray(new Integer[0]);
 
        // 배열을 정렬
        Arrays.sort(numSortList);
 
        for (int i = 0; i < n; i++) {
            sb.append(Arrays.asList(numSortList).indexOf(numList[i]) + " ");
        }
 
        System.out.println(sb);
    }
}

반복문안에 indexOf 함수를 넣으면 시간복잡도는 n*n 인 n^2가 된다. 당연히 시간초과가 뜰 수 밖에 없었다.

고민 끝에 구글링으로 힌트를 얻었고 해답은 HashMap이였다. Map은 키 값과 벨류 값 한 쌍으로 이루는 자료형이다. 이해를 돕기위해 비유하자면 파이썬의 딕셔너리 같은거다. ex) {key1:value1,key2:value2,....}

워낙 별의 별 시도를 다 해보다 보니 이번 기회에 항상 헷갈려하던 배열과 리스트 그리고 어레이리스트까지 뭔가 깨달은것 같다. 좋은 공부가 되는 문제였다.