[백준] 단계별로 풀어보기(단계:12,정렬,JAVA)18870번, 좌표 압축

문제 링크

18870번: 좌표 압축

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

처음 문제에 접근할 때에는 ArrayList를 사용하여 Collections.sort로 오름차순으로 정렬한 뒤 list.indexof()를 사용하여 위치를 통해 결과를 출력하려고 했지만 시간초과가 발생하였습니다.list.indexof()를 사용하기 때문에 시간초과가 발생한 것 같다고 판단하여 정렬한 값들을 HashMap을 사용하여 저장한 뒤 값을 불러오는 방식을 채택하여 문제를 해결하였습니다. 정렬할 때에는 Arrays.sort를 사용하여 배열을 정렬하였습니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 숫자들을 나누었습니다.
• 입력 숫자를 순서대로 저장하는 배열 arr과 숫자들을 정렬할 배열 sortedArr을 초기화하였습니다.
• for문을 통하여 배열에 값들을 저장하였습니다.
• Arrays.sort()를 사용하여 배열을 정렬하였습니다.
• HashMap을 구성하였습니다.

• stack은 숫자가 몇 번째로 작은 값인지 확인하기 위해 사용하였습니다.
• 중복된 key값이 들어가지 않도록 if문에 containkey를 사용하여 중복을 방지하였습니다.
• sorted배열에 값을 key값으로 사용하였으며 value는 stack값을 사용하였습니다.

• for문을 통해 HashMap에 있는 값들을 bw에 저장하였습니다.
• BufferedWriter를 통해 저장된 결과를 출력하였습니다.

결과 코드

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));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 출력
    	int index = Integer.parseInt(br.readLine());	//입력 횟수
        //띄어쓰기 나누는 StringTokenizer
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //----------------배열 초기화 및 값 저장---------------------
    	int[] arr = new int[index];
    	int[] sortedArr = new int[index];
    	for(int i=0;i<index;i++) {
    		int temp = Integer.parseInt(st.nextToken());
    		arr[i] = temp;
    		sortedArr[i] = temp;
    	}
    	Arrays.sort(sortedArr);	//배열 정렬
       	//----------------HashMap 초기화 및 값 저장-----------------
    	HashMap<Integer,Integer> map = new HashMap<>();
    	int stack = 0;
    	for(int val : sortedArr) {
    		if(!map.containsKey(val)) {
    			map.put(val, stack);
    			stack++;
    		}
    	}
        //---------------결과 출력-----------------
    	for(int val : arr) {
    		bw.write(map.get(val) + " ");
    	}
    	bw.flush();
    	bw.close();
    	br.close();
	}
}