백준 10867 자바 - 중복 빼고 정렬하기 (BOJ 10867 JAVA)

문제 : boj10867

 

 

  중복 제거만 하고 정렬만해도 풀 수 있는 간단한 문제이다. 해시로 중복체크하면서 list에 넣고 정렬 후 출력만 해줘도 된다. 또 다른 방법은 그냥 TreeSet에 넣으면 중복이 알아서 제거되므로 순서대로 꺼내면 된다.

 

  내 경우엔 어차피 값이 -1000~1000 까지의 정수이므로 2000개짜리 배열에 어떤 수가 존재하는지 기입한다. 그럼 중복은 알아서 제거되고, 배열 순서대로 출력만 해주면 된다. 배열을 2001개 잡아두고 0~1000은 음수가, 그 이상은 양수가 사용하게 해도 되고, 그냥 음수 따로 양수 따로 1000개씩 배열을 만들어줘도 된다. 내 경우엔 후자로 진행했다.

 

  예를들어 '-5 4 4 -1 -5 3 0'이 있고, 값이 -5~5 까지 가능했다고 한다면(그리기 쉽게) 다음과 같이 될 것이다. '실제'는 해당 idx가 실제 의미하는 수 이다. 존재는 해당 수가 존재하는지 여부이다.

  

  N개의 입력값에 대해 위 두 배열에 존재여부를 체크하고, 아래와 같이 순서대로 존재하는 값만 출력하면 중복이 제거된 정렬된 값이 나오게 된다. (답 : -5 -1 0 3 4) 이걸 -1000~1000으로 확장 시키면 이 문제의 답을 구할 수 있다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine());
        boolean[] negArr = new boolean[1001];
        boolean[] posArr = new boolean[1001];
        while (st.hasMoreTokens()) {
            int cur = Integer.parseInt(st.nextToken());
            if (cur < 0) {
                negArr[-cur] = true;
            } else {
                posArr[cur] = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1000; i > 0; i--) {
            if (negArr[i])
                sb.append(-i).append(' ');
        }
        for (int i = 0; i <= 1000; i++) {
            if (posArr[i])
                sb.append(i).append(' ');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}