[백준 18870] 좌표압축 시간초과파티 + 복습

 

 

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

통과된거

import java.util.Arrays;
import java.util.Scanner;
import java.util.HashMap;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        int[] sortedNums = new int[N];
        for(int i = 0;i<N;i++){
            nums[i]=sortedNums[i]=sc.nextInt();
        }

        //오름차순 정렬 후 map에 넣기 (key : num / val : rank)
        Arrays.sort(sortedNums);

          HashMap<Integer,Integer> rankMap = new HashMap<>();
        int rank=0;
        for (int num : sortedNums) {
            if(!rankMap.containsKey(num)){
                rankMap.put(num,rank);
                rank++;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int key : nums){
            int ranking = rankMap.get(key);
            sb.append(ranking).append(' ');
        }
        System.out.println(sb);
    }
}

 

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

[백준] 18870번 : 좌표 압축 - JAVA [자바]

이분 꺼를 참고했다. 설명도 정말 잘돼 있음

 

 

원래 했던 거...

import java.util.Scanner;
import java.util.HashMap;


public class test5{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        int[] sortedNums = new int[N];
        for(int i = 0;i<N;i++){
            nums[i]=sortedNums[i]=sc.nextInt();
        }

        //오름차순 정렬 후 map에 넣기 (key : num / val : rank)
        int temp = 0;
        for(int i =0;i<N-1;i++){
            for(int j =i+1;j<N;j++){
                if(sortedNums[i]>sortedNums[j]){
                    temp=sortedNums[i];
                    sortedNums[i]=sortedNums[j];
                    sortedNums[j]=temp;
                }
            }
        }


        HashMap<Integer,Integer> rankMap = new HashMap<>();
        int rank=0;
        for(int i =0;i<N;i++){
            if(!rankMap.containsKey(sortedNums[i])){
                rankMap.put(sortedNums[i],rank);
                rank++;
            }
        }

        for(int i =0;i<N;i++){
            System.out.print(rankMap.get(nums[i])+" ");
       }
    }
}

나는 코테에 되도록이면 import 해야 하는 패키지 쓰면 안 되는 줄 알았는데 안 쓰면 통과가 안됨.

컬렉션도 되도록이면 쓰면 안되는 줄 알고 계속 고민하고 있었음;; ㅋㅋ 다른사람푼거 참고 안하고있었으면 지금도 머리쥐어뜯으면서 고민하고있을듯.

암튼 Scanner를 BufferedReader로 바꿔도 저 정렬부분을 패키지 안 쓰고 직접 하면 시간 초과됨.

 

 

그리고

사실 지금까지 코테풀때 딱히 scanner대신 BufferedReader... 그리고 StringBulider를 써야 하는 필요성을 못 느꼈는데

시간제한 있는 문제 만나니까 뭔가 아 쓰긴 써야 하는구나 느꼈다.

StringBuilder는 가끔 써서 그나마 익숙한데 BufferedReader는 예전에 코테문제에서 한번 만나고 딱히 안 써서 겁나 안 익숙함ㅋ

지금 문제 푸느라 고생했으니 주말에 복습할 때 BufferedReader에 익숙해져 봐야겠다^,^

 

+ 0723 복습

 

쓸 수 있는 패키지 죄다 씀

//수의 개수 N 입력받기
//수 N개 입력받아 배열에 넣기
//수 N개 오름차순 정렬
//수 N개 중복값은 제외하고 순위 hashmap에넣기
//순위 출력
//bufferedReader,StringTokenizer, Stringbuilder이용해보기

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

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       //수의 개수 N 입력받기
        int N = Integer.parseInt(br.readLine());
        String stringNums = br.readLine();
        
        //수 N개 입력받아 배열에 넣기
        StringTokenizer st = new StringTokenizer(stringNums);
        int[] nums = new int[N]; 
        Integer[] sorted = new Integer[N];
        for(int i=0;i<N;i++){
            nums[i]=sorted[i]=Integer.parseInt(st.nextToken());
        }
//        int cnt=0;
//        while(st.hasMoreTokens()){
//            int index = cnt++;
//            nums[index]=sorted[index]=Integer.parseInt(st.nextToken());
//        }
        
        //수 N개 오름차순 정렬 및 중복제거
        Arrays.sort(sorted);
        sorted = Arrays.stream(sorted).distinct().toArray(Integer[]::new);
        
        
        //수 N개중 중복값은 제외한것들 순위 hashmap에넣기
        HashMap<Integer,Integer> rank = new HashMap<>();//key:숫자 value:rank
        for(int i = 0;i<sorted.length;i++){
            rank.put(sorted[i],i);
        }
        
        StringBuilder sb = new StringBuilder();
        for(int num:nums){
            sb.append(rank.get(num));
            sb.append(" ");
        }
        System.out.println(sb.toString());
    }
    
}

 

 

근데 중복제거대신 위에처럼 그냥 if문으로 걸러냈떠니 훨씬빠름

//수의 개수 N 입력받기
//수 N개 입력받아 배열에 넣기
//수 N개 오름차순 정렬
//수 N개 중복값은 제외하고 순위 hashmap에넣기
//순위 출력
//bufferedReader,StringTokenizer, Stringbuilder이용해보기

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

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       //수의 개수 N 입력받기
        int N = Integer.parseInt(br.readLine());
        String stringNums = br.readLine();
        
        //수 N개 입력받아 배열에 넣기
        StringTokenizer st = new StringTokenizer(stringNums);
        int[] nums = new int[N]; 
        Integer[] sorted = new Integer[N];
        for(int i=0;i<N;i++){
            nums[i]=sorted[i]=Integer.parseInt(st.nextToken());
        }
        
        //수 N개 오름차순 정렬 및 중복제거
        Arrays.sort(sorted);
        //sorted = Arrays.stream(sorted).distinct().toArray(Integer[]::new);
        
        
        //수 N개중 중복값은 제외한것들 순위 hashmap에넣기
        HashMap<Integer,Integer> ranks = new HashMap<>();//key:숫자 value:rank
        int rank=0;
        for(int i = 0;i<N;i++){
            if(!ranks.containsKey(sorted[i])){
                 ranks.put(sorted[i],rank++);
            }
           
        }
        
        StringBuilder sb = new StringBuilder();
        for(int num:nums){
            sb.append(ranks.get(num));
            sb.append(" ");
        }
        System.out.println(sb.toString());
    }
    
}

 

위에꺼가 distinct로 중복제거하는대신 if문으로 걸러낸거

신기하군.. 이래서 자료구조를 배워야한다는건가..?