반응형

Comparator 를 이용한 문제 

Compartor 안에 조건문을 걸어주고 return 시켜 주면 이중, 삼중으로 정렬 할 수 있다.

return 값에서 x,y 부분을 반대로 바꿔주면 [오름차순 <-> 내림차순] 으로 바꿀 수 있다.


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
44
45
46
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[][] arr = new String[N][4];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().split(" ");
        }
        
        //Comparator 사용
        Arrays.sort(arr, new Comparator<String[]>() {
            @Override
            public int compare(String[] s1, String[] s2) {
                if (Integer.parseInt(s1[1]) == Integer.parseInt(s2[1])) {
                    if (Integer.parseInt(s1[2]) == Integer.parseInt(s2[2])) {
                        if (Integer.parseInt(s1[3]) == Integer.parseInt(s2[3])) {
                            
                            //국영수 점수가 같다면 사전 오름차순
                            return s1[0].compareTo(s2[0]);
                        }
        
                        //국어점수 같고 영어점수 같을 때, 수학 점수는 내림차순
                        return Integer.compare(Integer.parseInt(s2[3]), Integer.parseInt(s1[3]));
 
                    }
                    //국어 점수 같을 때, 영어 점수는 오름차순
                    return Integer.compare(Integer.parseInt(s1[2]), Integer.parseInt(s2[2]));
                }
                //국어점수는 내림차순
                return Integer.compare(Integer.parseInt(s2[1]), Integer.parseInt(s1[1]));
            }
 
        });
        for (int i = 0; i < N; i++) {
            System.out.println(arr[i][0]);
 
        }
    }
}
cs


반응형
반응형

알고리즘 분류로 정렬 문제를 풀고있는데 이문제는 정렬의 문제가 아닌거 같다.

가장 중요한건 long 변수를 사용해야 한다는 점?

2중 반복문으로 전체를 계산했기 떄문에 시간 성능 나쁘다.

정렬을 하나 마나 똑같을 테고..

좀 더 빠른 방법이 있긴 할텐데..

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
import java.io.FileInputStream;
import java.util.*;
 
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        // 0 이상 1,000,000,000 이하의 정수 이기떄문에 long 변수 사용
        long[] arr = new long[N];
        long sum = 0;
 
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextLong();
        }
 
        // 정렬 안했고 2중 반복문을 통해서 절대값으로 처리해서 계산했다.
        // i == j 일때 처리하지 않은 이유는 어차피 arr[i] - arr[j] 는 0이 되기 때문
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sum += Math.abs(arr[i] - arr[j]);
            }
        }
        System.out.println(sum);
    }
}
 
cs


반응형
반응형

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

그리고 11650 좌표정렬하기 1 번이랑 문제가 또오오오옥같다. (x좌표랑 y좌표만 바꾸면 됨)

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3


처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 

11651 좌표 정렬하기 2 소스코드

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
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
 
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            arr[i][0= sc.nextInt();
            arr[i][1= sc.nextInt();
        }
 
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if(x[1]==y[1]){
                    return Integer.compare(x[0], y[0]);
                }
                return Integer.compare(x[1], y[1]);
            }
        });
 
        for (int i = 0; i < N; i++) {
            System.out.println(arr[i][0+ " " + arr[i][1]);
        }
    }
 
}
cs


반응형
반응형

계속 해서 Comparator를 사용해서 문제를 풀고 있다. 으흠


1. 맨처음 나이순으로 정렬한다.

끝이다.

그 다음 가입한 순서대로 정렬을 해야하는데 들어온 순서가 가입한 순서기 때문에 이미 정렬이 되서 들어왔다.

단순히 String[][] 2차원 배열을 어떻게 정렬할까에 대한 문제이다.



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.io.FileInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) throws Exception {
        //Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int N = sc.nextInt();
        String[][] arr = new String[N][2];
        for(int i=0; i<N; i++){
            arr[i][0= sc.next();
            arr[i][1= sc.next();
        }
        
        
        Arrays.sort(arr,new Comparator<String[]>(){
            @Override
            public int compare(String[] one, String[] two){
                return Integer.compare(Integer.parseInt(one[0]),Integer.parseInt(two[0]));
            }
        });
        
        for(int i=0; i<N; i++){
            System.out.println(arr[i][0+" "+ arr[i][1]);
        }
    }
}
 
cs


반응형
반응형

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3


처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 


11650 좌표 정렬하기 <소스코드>

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine().trim());
        int[][] arr = new int[N][2];
        String[] str = new String[2];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            arr[i][0=Integer.parseInt(str[0]);
            arr[i][1= Integer.parseInt(str[1]);
        }
 
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if (x[0== y[0]) {
                    return Integer.compare(x[1], y[1]);
                }
                return Integer.compare(x[0], y[0]);
            }
 
        });
 
        for (int i = 0; i < N; i++) {
            System.out.println(arr[i][0+ " " + arr[i][1]);
        }
 
    }
 
}
cs


반응형
반응형

Comparator 가 부족한것 같아서 Compartor를 이용해서 문제를 풀었다.

Comparator에서 int, float, char 등은 원시적인 데이터등은 정렬이 되지 않고 Object등만 정렬 가능하다. (String, Integer 등등)

그런데 원시적인 데이터의 2차 배열은 객체인가보다.. int[][]는 Comparator를 통해 정렬을 할 수 있다.  너므 어려운것...

나는 그래서 이문제를 Comparator를 통해 풀고자 int배열이 아닌 Integer 배열을 사용했다.


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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
 
public class Main {
    static boolean[][] arr;
    static int[][] kevin;
    static int[] bacon;
    static int n;
    static int m;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String str = br.readLine();
        int size = str.length();
        Integer[] arr = new Integer[size];
        for (int i = 0; i < size; i++) {
            arr[i] = str.charAt(i) - '0';
        }
        // Comparator를 사용하기 위해 객체인 Integer 변수를 사용
        Arrays.sort(arr,new Comparator<Integer>(){
            @Override
            public int compare(Integer x, Integer y){
                //x,y 값으로 놓으면 오름차순이다. 나는 y,x로 놓아서 내림차순으로 바꾸었다.
                return Integer.compare(y, x);
            }
        });
        //for-each
        for(Integer i:arr){
            System.out.print(i);
        }
        
    }
 
}
cs


반응형
반응형

나처럼 Comparator를 사용해서 푼 사람은 많이 없는거 같아서 나한텐 어려웠던 문제

푸는 방법) 

끝난 시간이 빠를 수록 다음 시작시간이 빠르기 때문에 2차원 배열을 정렬한다.

다음 제일 빨리 시작하는 회의를 선택한다. (끝나는 시간도 제일 빠르다. 이미 정렬을 해 놨으므로)

차례대로 마지막까지 반복한다.


1. 시작시간 - 종료시간 을 arr[][] 배열에 저장한다.

2. arr[][] 배열을 종료시간에 따라 정렬한다.

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3


처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Comparator;
 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
 
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            arr[i][0= sc.nextInt();
            arr[i][1= sc.nextInt();
 
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] start, int[] end) {
                //start[0], end[0] 배열은 arr[][] 의 첫번째 라인(시작시간)이다.
                //start[1], end[0] 배열은 arr[][] 의 두번째 라인(종료시간)이다.
                if(start[1]==end[1]){
                    //만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬한다.
                    return Integer.compare(start[0], end[0]);
                }
                //종료시간에 따라 정렬한다.
                return Integer.compare(start[1], end[1]);
            }
 
        });
        
 
        int count = 0;    // 최대값 변수 
        int end = -1;    // 다음시작 시간과 비교할 변수
        for (int i = 0; i < N; i++) {
            //현재 시작시간이 이전 종료시간보다 늦을 경우 
            if (arr[i][0>= end) {
                //System.out.println(arr[i][0] + " " + arr[i][1]);
                end = arr[i][1];    //현재 종료시간을 다음 시작시간과 비교하기위해 저장 
                count++;
            }
        }
        System.out.println(count);
    }
}
 
cs



반응형
반응형

BFS를 통해 푸는 문제이다. 물론 DFS로 문제를 풀 수 있을 것 같다.


나는 세가지 변수를 설정했다.


1. 1촌 관계를 저장하는 배열 : Arr[][2]


2. 방문했던 점을 저장하는 배열 : visited[]


3. 얼마만큼 지나왔는지 저장하는 배열 : total[]


세가지만 이용하면 쉽게 문제를 풀 수 있다.


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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int[][] arr;
    static boolean[] visited;
    static int[] total;
    static int x;
    static int y;
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        arr = new int[N + 1][2];    //1촌관계를 저장할 배열
        visited = new boolean[N + 1];    // 방문했던 값을 다시 방문하면 무한루프에 빠지게 된다.
        total = new int[N + 1];        //몇칸을 거쳐왔는지에 대한 배열
        x = sc.nextInt();        //입력 X값
        y = sc.nextInt();        //입력 Y값
 
        
        int K = sc.nextInt();
        for (int i = 1; i <= K; i++) {
            arr[i][0= sc.nextInt();
            arr[i][1= sc.nextInt();
        }
        System.out.println(BFS(x, N));
    }
 
    public static int BFS(int x, int N) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(x);
        //큐가 비었으면 연결이 끊어졌다는 소리이다.
        while (!q.isEmpty()) {
            int nextX = q.poll();
            visited[nextX] = true;
            //방문한 점은 true로 바꿈으로써 재방문 하지 안도록 한다.
            for (int i = 0; i < N; i++) {
                //전체 배열을 돌면서 연결되있으면서 방문 안한점이 있나 체크한다
                //있다면 큐에 넣어준다.
                if (arr[i][0== nextX && !visited[arr[i][1]]) {
                    //1촌관계가 랜덤으로 되어있으므로 왼쪽 라인 한번
                    q.add(arr[i][1]);
                    //이전에서 +1 된 값을 저장한다
                    total[arr[i][1]] = total[arr[i][0]] + 1;
                } else if (arr[i][1== nextX && !visited[arr[i][0]]) {
                    //오른쪽 라인 한번
                    q.add(arr[i][0]);
                    //이전에서 +1된값을 저장한다.
                    total[arr[i][0]] = total[arr[i][1]] + 1;
                }
            }
            //q가 비었거나 찾는값이 있으면 종료한다.
            if (!q.isEmpty() && q.peek() == y) {
                return total[y];
            }
 
        }
        return -1;
    }
}
 
cs


문제에 나와있지 않은 예시를 하나 들자면.

10

7 6

9

1 2

1 3

1 4

9 1

9 10

3 5

3 6

2 7

2 8

이 있다. 이때의 결과값은 4가 나와야 한다.

반응형
반응형


규칙만 찾으면 정말 금방 풀 수 있는 문제이다.


DP 문제는 일단 경우를 모두 써서 규칙을 찾아내는 게 중요하다고 배웠다.


그래서 무작정 경우를 작성해보았다.



위 표와 같은 결과가 나온다.

위 표에서 DP[] 라는 배열을 할당했을때

 - 0은 횟수(N)이 증가함에도 상관없이 1임을 알수 있었다.

 - 1~9는 횟수(N)이 1일때를 제외하고, 이전에 있던 자신의 값과 바로 전값의 합임을 알 수 있었다.

즉,  dp[i] = dp[i]  dp[i - 1] 이라는 규칙을 얻어 낼 수 있었다.


<소스코드>


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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int N = sc.nextInt();
 
        int[] dp = new int[10];
        int result = 0;
        for (int i = 0; i < 10; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < N; i++) {
            result = 0;
            for (int j = 1; j < 10; j++) {
                dp[j] = (dp[j] + dp[j - 1]) % 10007;
                result = (result + dp[j]) % 10007;
            }
        }
        if(result==0){
            System.out.println(10);
        }
        else
        System.out.println((result + 1) % 10007);
    }
}
 
cs


반응형
반응형

배열이 아닌 큐를 사용해서 풀었다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.FileInputStream;
import java.util.*;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int M = sc.nextInt();
        Queue<Integer> q = new LinkedList<Integer>();    //Queue 사용
        int count = 0;
        for (int i = 0; i < N; i++) {
            q.add(sc.nextInt());    //큐에 저장
        }
        
        while(!q.isEmpty()&&M-q.peek()>=0){    //큐가 비었거나     합의 값이 0보다 커질경우에 종료
            M -= q.poll();
            count++;
        }
        System.out.println(count);
    }
}
 
cs


반응형

+ Recent posts