코딩공부 63일차: 백준 18870번 좌표 압축 자바 Java

백준 9단계 11번 문제 - 18870 좌표 압축

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

18870번: 좌표 압축

 

 

 

 

---

9. 정렬 (11) 백준 18870번 문제 좌표 압축

---

문제

---

 

 

문제부터 조금 이해하기 힘들다

 

 

 

---

과정 생각해보기

---

 

문제 밑에 도움을 주는 문장들이 붙어 있다

 

값이 큰 순서대로 붙이면 되는 것

즉, 순위다

 

 

 

---

오답

---

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int arr[] = new int[n];
        int sortarr[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            sortarr[i] = arr[i];
        }
    
 
        sortarr = Arrays.stream(sortarr).distinct().toArray();    //중복 제거
        Arrays.sort(sortarr);    //오름차순 정렬
        
//        System.out.println(Arrays.toString(sortarr));    //sortarr 확인용
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < sortarr.length; j++){
                if(arr[i] == sortarr[j]) {
                    arr[i] = j;
                    break;
                }
            }
            System.out.print(arr[i] + " ");
        }
    }
 
}

 

이클립스에서 값을 여러 개 넣어봤을 땐 원하는 대로 순위가 출력됐는데

백준에 입력하니 시간 초과가 떴다

 

 

 

---

정답 인정 코드

---

 

https://st-lab.tistory.com/279

이 블로그를 참고했다

(설명이 자세해서 이 블로그를 안 볼 수가 없다)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Arrays;
 
 
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());
        
        int[] arr = new int[n];
        int[] sorted = new int[n];
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();    // rank를 매길 HashMap
 
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            sorted[i] = arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(sorted);
        
        //map에 순위 넣기
        int rank = 0;
        for(int i = 0; i < arr.length; i++) {        //.contansKey() : 같은 값 있으면 true 반환
            if(!rankingMap.containsKey(sorted[i])) { // !가 붙었으므로 같은 값 없으면 = 중복 아니어야 아래 .put 실행 
                rankingMap.put(sorted[i], rank);    // .put : map에 값 추가
                rank++;        // map에 넣고나면 다음 순위를 가리킬 수 있도록 1씩 더한다
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            int ranking = rankingMap.get(arr[i]);    //순위 가져옴 // .get(): map에 존재하면 입력받은 값 리턴, 없으면 null 
            sb.append(ranking).append(' ');
        }
        
        System.out.println(sb);
        
    }
}

 

새로 배운 HashMap!

Arrays.sort에서 시간을 많이 잡아먹어서 시간초과가 뜨는 줄 알았는데 전혀 아니었다

 

.containsKey()로 중복 있는지 확인하고

.put(sorted[i], rank) 으로 sorted[i]를 순위rank에 넣은 다음에

.get()으로 순위를 가져온다

 

 

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Arrays;
 
 
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());
        
        int[] arr = new int[n];
        int[] sorted = new int[n];
        
        HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            sorted[i] = arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(sorted);
        
        int rank = 0;
        //★
        for(int i = 0; i < arr.length; i++) {
            if(!rankingMap.containsKey(sorted[i])) {
                rankingMap.put(sorted[i], rank);
                rank++;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            int ranking = rankingMap.get(arr[i]);
            sb.append(ranking).append(' ');
        }
        // ★
        System.out.println(sb);
    }
}

 

새로 배운 개념은 항상 어렵다

 

 

 

---