시간초과를 관리하자

이번에 풀은 문제는 백준 18870번이다.

처음에 이 문제의 내용 자체를 몰라서 좌표압축이 뭔지부터 공부해보았다.

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

18870번: 좌표 압축

 

좌표압축이란 간단하게 설명하면 입력 받은 값들을 정렬하여서 순서대로 인덱스값(좌표를 부여하는 것이다.)

ex) 2,4,-10,4,-9를 주면 -10, -9, 2, 4, 4으로 정렬하고 -10은 0, -9는 1, 2는 2, 4는 3 그다음 4도 3으로한다.

 

그래서 코드를 짜면 해시맵을 사용해서 아래와 같은 코드를 짠다.

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b18870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count  = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<count; i++){
           list.add(Integer.parseInt(st.nextToken()));
        }

        ArrayList<Integer> sorted = new ArrayList<>();
        for(int i : list){
            sorted.add(i);
        }
        Collections.sort(sorted);
        HashMap<Integer,Integer> map =new HashMap();
        int tmp=0;
        for(int i=0; i<sorted.size(); i++){
            if(!map.containsKey(sorted.get(i))){
                map.put(sorted.get(i),tmp);
                tmp++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i : list){
            sb.append(map.get(i)+" ");
        }
        System.out.println(sb);
    }
}

 

처음에는 시간초과가 너무 나서 무엇이 문제 인지 몰랐었다. 내가 처음 짰던 코드는 

for(int i : list){
	System.out.print(map.get(i)+" ");
}

위와 같은 코드로 결과 값을 출력했었다.

나는 이 부분이 문제인지 몰랐었지만 학교선배가 알려줘서 알 수 있었다... System I/O를 하는 과정은 많은 시간을 잡아먹는다는 것을

그래서 도입 한 것이 StringBuilder이다. StringBuilber는 스트링값들을 모아서 한번에 출력하기 위한 String 클래스 객체를 만드는 것이다.

 

오늘은 한 감자 했다.