[백준] 18870 - 좌표압축 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

1 ≤ N ≤ 1,000,000
입력
첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

접근방법

 각 좌표마다, 해당 조건에 맞는 값을 반환하는 문제이다.  N의 개수가 1000000이므로, 정렬을 잘못 사용한다면, 최악의 경우 각 좌표를 비교하기 위해 총 N^2의 시간 복잡도를 지니게 되므로, 어떻게 정렬할 것인가에 대해 문제는 요구하고 있다. 이 점을 생각하고 풀이로 들어가자

풀이

 문제에서는 서로 다른 좌표에 대해서만 조건 처리를 하므로, 중복 값을 처리하지 않는다는 사실을 먼저 인지하자. X1, X2의 값들을 모두 조건에 의해 구했다고 가정하자. 이들을 효율적으로 순서에 따라 출력하기 위해서는 찾는 시간을 줄여야 한다.(N이 최대 1000000이므로) 따라서, Hashmap을 이용했다. HashMap은 검색 속도가 O(1)이기 때문에, 만들기만 한다면, 중복 값에 대해 검색에 걸리는 시간을 신경 쓸 필요가 없다.

 

 이제 문제 조건에 의한 값을 어떻게 구할 것인지 생각해보자. 예제 1을 기준으로 정렬을 사용 시 숫자들은 다음과 같이 정렬된다.

 

-10 - 9 2 4 4

 

-10보다 작은 숫자는 0이며, -9 는 -10 하나이므로 1이다. 4번째 4는 3의 값을 가지며, 5번째 4도 마찬가지로 3의 값을 갖게 된다. 문제에서 요구하는 조건이 정렬 시 오름차순의 순서를 가진다는 것을 알 수 있다. 따라서 정렬 후 0부터 Rank를 주고 그 값을 입력 순서에 맞게 출력해주면 된다. 

 

실패 원인

 Hashmap을 이용한 것까지는 좋았는데, 해당 조건에 대해 그려보지 않아, 값들이 오름차순이라는 규칙성을 발견하지 못했다. 때문에 키값을 추가할 때마다 키값을 통해 모든 값을 재조정했고, 이로 인한 시간 초과를 겪었다.

 

 한 번만 그려봤다면, 이 오름차순이라는 규칙성을 보고, 정렬한 뒤에 순차적으로 값만 부여했다면, 가볍게 풀었을 것이다. 

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        Map<Integer,Integer> map = new HashMap<>();
        int tc = Integer.parseInt(br.readLine());
        stk = new StringTokenizer(br.readLine()," ");

        int[] results = new int[tc];
        for (int i = 0 ; i < tc;i++){
            int data = Integer.parseInt(stk.nextToken());
            results[i] =data;
            if(map.isEmpty()){
                map.put(data,0);
                continue;
            }

            //데이터 존재시 넘어감
            if(map.get(data)!=null){
                continue;
            }
            int cnt =0;

            for(int key : map.keySet()){

                if(key > data){
                    map.put(key,map.get(key)+1);
                    continue;
                }else{
                    cnt++;
                }

            }

            map.put(data,cnt);

        }

        for (int result : results){
            sb.append(map.get(result)+ " ");
        }

        System.out.println(sb);

    }
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {

       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        Map<Integer, Integer> map = new HashMap<>();
        int tc = Integer.parseInt(br.readLine());
        stk = new StringTokenizer(br.readLine(), " ");
        int[] results = new int[tc];

        for (int i = 0; i < tc; i++) {
            results[i] = Integer.parseInt(stk.nextToken());
        }
        //정렬용 배열
        int[] copied = results.clone();
        Arrays.sort(copied);
        
        //Rank용 변수
        int cnt = 0;
        
        //map에 키값이 없을때만 랭크와 함께 삽입 
        for (int result : copied) {
            //데이터 존재시 넘어감
            if (map.get(result) != null) {
                continue;
            }
            map.put(result, cnt++);

        }

		//출력형식에 맞춰 value값 반환
        for (int result : results){
            sb.append(map.get(result)+" ");
        }

        System.out.println(sb);

    }
}

결과

 문제에 정답에 근접했는데, 이런 생각을 못한 점이 미처 아쉽다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.