본문 바로가기
알고리즘 문제 (백준저지)/정렬

[10989/java] 수 정렬하기3

by 유헤 2019. 6. 7.

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

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

- 이 문제는 메모리 사용이 8MB 밖에 되지 않고, 시간이 3초나 된다는 점을 감안해야 합니다.

처음에는 간단하게 배열에 추가하는 문제인가? 라고 생각했습니다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

 

public class Main {

 

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner sc =new Scanner(System.in);

        

        int n = sc.nextInt();

        int[] d = new int[n+1];

        

        for(int i=0; i <n ; i++) {

            int tmp = sc.nextInt();

            d[tmp]++;

        }

        

        for(int i=0; i <n ; i++) {

            int cnt = d[i];

            for(int j=0; j<cnt ; j++) {

                System.out.println(i);

            }

                

        }

        

        

    }

 

}

 

Colored by Color Scripter

 cs

하지만,,, 시간 초과로 실패

 

 

BufferedReader 로 바꿔서 해볼까? 싶어서 시도해봤지만,

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

import java.io.BufferedInputStream;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

 

public class Main {

 

    public static void main(String[] args) throws Exception {

        // TODO Auto-generated method stub

        

        BufferedReader bs = new BufferedReader(new InputStreamReader(System.in));

        

        

        

        int n = Integer.parseInt(bs.readLine());

        int[] d = new int[n+1];

        

        for(int i=0; i <n ; i++) {

            int tmp = Integer.parseInt(bs.readLine());

            d[tmp]++;

        }

        

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        for(int i=0; i <n ; i++) {

            int cnt = d[i];

            for(int j=0; j<cnt ; j++) {

                bw.write(Integer.toString(i)+"\n");

            }

                

        }

        

        

    }

 

}

 

 

Colored by Color Scripter

 cs

 

또 실패하였다. 뭐가 문제일까 싶었는데... 출력하는 부분에서 분기 ( d[i] >0 ) 을 걸어주지 않아서 생긴 문제였습니다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

import java.io.BufferedInputStream;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

 

public class Main {

 

    public static void main(String[] args) throws Exception {

        // TODO Auto-generated method stub

        

        BufferedReader bs = new BufferedReader(new InputStreamReader(System.in));

        

        

        

        int n = Integer.parseInt(bs.readLine());

        int[] d = new int[10001];

        

        for(int i=0; i <n ; i++) {

            d[Integer.parseInt(bs.readLine())]++;

        }

        

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        for(int i=1; i <10001 ; i++) {

            if(d[i]>0) {

                for(int j=0; j<d[i] ; j++) {

                    bw.write(Integer.toString(i)+"\n");

                }

            }

                

        }

        bs.close();

        bw.close();

        

    }

}

 

Colored by Color Scripter

 cs

분기를 잘 걸어줘서 성공했습니다!! 

'알고리즘 문제 (백준저지) > 정렬' 카테고리의 다른 글

[백준/2751] 수 정렬하기 (Java/코드)  (0) 2019.02.06

관련글

티스토리툴바