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

 

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net

그리디는 많이 안풀어봐서 어렵네요..

이 문제는 정렬 + 그리디 문제입니다.

 

우선 마감일, 과제 점수를 담은 list배열을

  1. 과제 점수가 높은 순 (내림차순)
  2. 마감일이 적게 남은 순 (오름차순)

으로 정렬합니다.

 

그 다음 과제 점수가 가장 높은 0번 인덱스부터 과제를 진행합니다.

여기서 확인해야할 것은 마감일 안에 과제를 할 수 있는지에 대한 여부입니다.

d일부터 1일까지 visit[d]=true인지 확인해서 해당 일에 과제를 했는지 체크합니다.

과제를 했다면 전날 과제를 했는지 체크하는 방식으로 1일까지 확인합니다.

 

과제를 하지않은 날이 있다면 과제를 진행하고 방문체크 해주면 되고,

d ~ 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
typedef pair<int, int> pi;
 
pi list[MAX];
bool visit[MAX + 1];
int N;
 
bool cmp(pi a, pi b) {
    if (a.second == b.second) return a.first < b.first;
    else return a.second > b.second;
}
 
void func() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int d = list[i].first;
        for (int j = d; j > 0; j--) {
            if (visit[j]) continue;
            
            visit[j] = true;
            ans += list[i].second;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    sort(list, list + N, cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16

프로젝트 진행 중 JpaRepository에서 Pagenation을 적용한 Page객체를 받은 이후 Collections.sort로 정렬을 하였습니다.

하지만 이와 관련된 문제점 하나를 발견하게 되었고 포스팅으로 남길려고 합니다.

 

우선 db에 유저의 정보를 저장해줍니다.

profile_url은 file저장을 공부하면서 사용해본 것이며 이 글과는 상관 없는 file입니다.

내일쯤 file 저장관련 글을 포스팅할 예정입니다.

 

각 유저들의 점수(score)를 같이 저장해줍니다.

이 유저들을 score기준 내림차순으로 조회를 하는데 Pagenation을 적용시키려고 합니다.

 

 

UserRepository에서는 Page 객체로 리턴하는 findAll 메소드를 작성합니다.

 

UserServiceImpl에서 UserRepository의 findAll 메소드를 호출하는 findAllUser 메소드를 작성합니다.

userRepository.findAll로 Page객체를 가져오고, UserGetRes의 of 메소드에서 정렬을 진행합니다.

 

Pagenation을 적용했기 때문에 변수를 많이 사용하였지만 of 메소드의 정렬하는 부분이 핵심입니다.

Page객체를 가져와서 score기준 내림차순으로 정렬을 진행합니다.

 

그리고 Controller에서는 page와 size를 RequestParam으로 받아서 UserService의 findAllUser 메소드를 호출합니다.

 

이제 스웨거를 통해 테스트를 합니다.

확인할 페이지는 0페이지, 즉 첫번째 페이지를 조회하며 최대 3개의 데이터를 조회하려고 합니다.

 

결과는...

네.. 이렇게 나왔습니다.

 

원래 의도한 대로라면 score가 120인 id10부터 score가 100인 id2까지 나오는게 맞습니다.

여기서 확인해봐도 id는 10 -> 5 -> 2 순서대로 조회가 되어야합니다.

 

이 과정에서 제가 치명적인 실수를 한 것이 있습니다.

바로 Repository에서 Page객체를 가져온 이후에 정렬을 진행했다는 것입니다.

 

Page객체에 있는 데이터는 조회 가능한 모든 리스트가 있는것이 아니라 size만큼의 데이터만 있는 것이었습니다.

따라서 제가 Service에서 Repository를 호출할 때 Sort 기준을 아무것도 주지 않았기 때문에 먼저 추가된 데이터부터 size만큼 데이터가 조회된 것이었습니다.

 

그럼 이제 알맞게 수정을 해야겠죠?

우선 UserRepository의 findAll 메소드에 OrderByScore를 추가하거나 Pageable에 Sort를 추가합니다.

그 후에 UserGetRes의 정렬하는 부분을 지웁니다.

 

일단 UserGetRes의 of 메소드의 정렬부분을 지웁니다.

 

 

먼저 UserRepository의 findAll 메소드 수정하는 방법입니다.

findAllUsers로는 자동완성이 안뜨길래 findUsersByOrderByScoreDesc로 수정합니다.

뒤에 Desc를 안붙이면 default로 Asc가 적용됩니다.

 

 

다음은 UserService의 PageRequest에 Sort를 추가하는 방법입니다.

UserRepository에 있는 findAll 메소드는 그대로 두고 Sort를 추가합니다.

score 기준 DESC를 추가합니다.

 

 

둘 중 아무방법이나 사용한 다음 스웨거를 통해 테스트를 합니다.

그러면 이렇게 올바르게 조회를 할 수가 있습니다.

 

저는 두 번째 방법을 선호하기는 합니다만 두 방법 중 어떤 방법이 더 좋을지는 잘 모르겠습니다.

앞으로 로직을 구현할 때 생각이라는 것을 많이 해야겠다는 생각이 듭니다.

 

정렬을 적용하는 시점이 잘못되어 생긴 문제였습니다.

'Spring' 카테고리의 다른 글

@IdClass를 이용하여 복합 키를 복합 키로 갖는 Entity 구현  (0) 2022.04.13
Postman을 이용한 File, Dto 동시 Post요청  (8) 2021.08.15
JpaRepository save를 반복하여 데이터를 추가할 때 update가 되는 문제  (0) 2021.08.06
Entity @GeneratedValue with @IdClass, @EmbeddedId  (2) 2021.08.06
Entity @Embeddable을 이용한 복합 키 구현  (0) 2021.08.01

말 그대로 페이징, 데이터를 페이지 단위로 나눠서 보여주는 작업입니다.

이를 위해 JPA에서는 페이지 정보와 정렬 기준으로 페이징 처리를 하며 PageRequest, Pageable, Sort 객제를 사용합니다.

1
2
3
4
@Repository
public interface ConferenceRepository extends JpaRepository<Conference, Long> {
    Page<Conference> findAll(Pageable pageable);
}
 cs

Repository 구성입니다.

return type을 Page 객체로 감싸줍니다.

Service에서 PageRequest 객체를 넘겨주면 Repository에서 Pageable 객체로 받습니다.

Pageable 객체에는 페이징 정보와 정렬 기준을 모두 포함하므로 전달받는 파라미터에 반드시 포함되어야합니다.

 

1
2
3
4
5
6
7
8
9
10
@Service
public class ConferenceServiceImpl implements ConferenceService {
    @Override
    public ConferenceFindAllGetRes findAllConference(int page, int size) {
        Sort sorts = Sort.by(Sort.Direction.DESC, "id");
        PageRequest pageRequest = PageRequest.of(page, size, sorts);
    
        return ConferenceFindAllGetRes.of(conferenceRepository.findAll(pageRequest), pageRequest, sorts);
    }
}
 cs

Repository에서는 페이징 정보를 Pageable로 받지만 Service에서 호출 시 보낼 페이징 정보는 PageRequest 객체입니다.

딱 Request만 봐도 요청 잘하게 생겼죠?

PageRequest.of(page, size, sorts);

page: 현재 페이지 (코드에서 첫 페이지는 0입니다.)

size: 페이지에서 출력할 데이터의 갯수

sorts: 정렬기준, 방법 (ex. id 기준 asc or desc)

 

그럼 이런식으로 정렬기준에 맞게 출력이 됩니다!

이거를 이제 findByTitle이나 findByConferenceCategoryId와 같은 메소드에도 적용할 수 있습니다

'Spring' 카테고리의 다른 글

Entity @Embeddable을 이용한 복합 키 구현  (0) 2021.08.01
Entity @IdClass를 이용한 복합 키 구현  (0) 2021.07.29
Spring @RequestParam String[] 문제  (0) 2021.07.24
Spring Optional.isPresent()  (0) 2021.07.15
Spring 기본 세팅 (STS)  (0) 2021.06.12

정렬 알고리즘은 N개의 숫자를 기준에 맞게 오름차순 or 내림차순으로 정렬하는 알고리즘입니다.

종류가 다양하게 있지만 이 글에서는 선택, 버블, 삽입, 병합, 퀵 정렬만 정리하려고 합니다.

그리고 오름차순 정렬만 정리하였습니다.

 

1. 선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 수를 찾으면서 정렬하는 알고리즘입니다.

 

1. 선택한 인덱스부터 N까지 가장 작은 값을 찾습니다.

2. 가장 작은 값과 선택한 값을 서로 바꿉니다.

3. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort() {
    for (int i = 0; i < N - 1; i++) {
        int minidx = i;
        for (int j = i + 1; j < N; j++) {
            if (list[minidx] > list[j]) {
                minidx = j;
            }
        }
        int tmp = list[minidx];
        list[minidx] = list[i];
        list[i] = tmp;
    }
}
 cs

 

 

2. 버블 정렬 (Bubble Sort)

버블 정렬은 연속된 2개의 수를 비교하여 정렬하는 알고리즘입니다.

정렬 과정에서 가장 큰수를 맨뒤로 보내는 방식입니다.

 

1. 두 번째 인덱스부터 바로 이전의 인덱스와 값을 비교합니다. (list[idx], list[idx - 1])

2. list[idx - 1] > list[idx]이면 두 수를 바꿉니다.

3. 아니면 다음 인덱스를 확인합니다.

4. 이 과정을 N번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

 

선택 정렬은 앞에서부터 작은 수가 결정되는 방식이지만

버블 정렬은 뒤에서부터 큰 수가 결정되는 방식입니다.

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N - i; j++) {
            if (list[j - 1] > list[j]) {
                int tmp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = tmp;
            }
        }
    }
}
 cs

 

 

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 이전의 값들을 비교하여 자신이 들어갈 위치를 찾아들어가는 정렬 알고리즘입니다.

 

1. 현재 인덱스에서 왼쪽으로 이동하면서 값을 비교합니다.

2. tmp보다 작은 수가 나올 때까지 수들을 한칸 옮겨줍니다.

3. tmp보다 작은 수가 나오면 그 다음 자리에 tmp를 넣어줍니다.

4. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(N), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertionSort() {
    for (int i = 1; i < N; i++) {
        int tmp = list[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (list[j] > tmp) {
                list[j + 1] = list[j];
            }
            else
                break;
        }
        list[j + 1] = tmp;
    }
}
 cs

 

 

4. 병합 정렬 (Merge Sort)

병합 정렬은 배열을 반씩 분할해가면서 정렬하는 알고리즘입니다.

시간적으로는 효율적이나 메모리를 배열의 2배 사용해야하는 단점이 있습니다.

 

1. 배열을 가장 작은크기까지 분할합니다.

2. 분할된 배열끼리 정렬합니다.

3. 분할된 배열을 다시 합쳐서 합친 배열을 다시 정렬합니다.

4. 이 과정을 반복합니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}


[배열을 분할합니다.]
N = 8    {4, 5, 8, 2, 6, 1, 7, 3}
    

N = 4    {4, 5, 8, 2}    {6, 1, 7, 3}


N = 2    {4, 5}    {8, 2}    {6, 1}    {7, 3}


N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


[배열을 병합하는 과정에서 정렬합니다.]
N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


N = 2    {4, 5}    {2, 8}    {1, 6}    {3, 7}


N = 4    {2, 4, 5, 8}    {1, 3, 6, 7}


N = 8    {1, 2, 3, 4, 5, 6, 7, 8}

 

정렬로직 설명)
 
분할된 두 개의 배열에서 가장 작은 값들끼리 비교하여 작은 값을 새로운 배열에 넣습니다.
arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1 or arr2의 숫자를 모두 고를때까지 반복합니다.


arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1[i] = 2
arr2[j] = 1


arr1: {2, 4, 5, 8}    arr2: {3, 6, 7}    sorted: {1}
arr1[i] = 2
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {3, 6, 7}    sorted: {1, 2}
arr1[i] = 4
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {6, 7}    sorted: {1, 2, 3}
arr1[i] = 4
arr2[j] = 6


arr1: {5, 8}    arr2: {6, 7}    sorted: {1, 2, 3, 4}
arr1[i] = 5
arr2[j] = 6


arr1: {8}    arr2: {6, 7}    sorted: {1, 2, 3, 4, 5}
arr1[i] = 8
arr2[j] = 6


arr1: {8}    arr2: {7}    sorted: {1, 2, 3, 4, 5, 6}
arr1[i] = 8
arr2[j] = 7


arr1: {8}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7}
여기서 arr2의 숫자를 모두 골랐으니 arr1의 남은 숫자를 sorted의 뒤에 붙여주면 됩니다.


arr1: {}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7, 8}

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(NlogN)이고, 공간복잡도는 O(N * 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
34
void merge(int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;
 
    while (i <= m && j <= r) {
        if (list[i] < list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
 
    if (i > m) {
        for (int t = j; t <= r; t++, k++) {
            sorted[k] = list[t];
        }
    } else {
        for (int t = i; t <= m; t++, k++) {
            sorted[k] = list[t];
        }
    }
 
    for (int t = l; t <= r; t++)
        list[t] = sorted[t];
}
 
void mergeSort(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }
}
 cs

 

 

 

5. 퀵 정렬 (Quick Sort)

배열에서 피봇을 선택해 피봇보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 옮겨지고

피봇을 기준으로 피봇을 제외한 왼쪽, 오른쪽 원소들을 다시 정렬해나가는 알고리즘입니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
피봇은 배열의 첫번째 요소로 지정합니다.


list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot = 0
i = 1
j = 0


list[] = {4, 2, 8, 5, 6, 1, 7, 3}
pivot = 0
i = 3
j = 1


list[] = {4, 2, 1, 5, 6, 8, 7, 3}
pivot = 0
i = 5
j = 2


list[] = {4, 2, 1, 3, 6, 8, 7, 5}
pivot = 0
i = 7
j = 3


list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}


이후에 피봇 기준 왼쪽 오른쪽 배열{3, 2, 1}과    {6, 8, 7, 5}도 똑같은 로직을 반복합니다.

 

정렬로직 설명)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot : 0
i = 1
j = 0


list[i]와 list[pivot]을 비교합니다.
list[i] < list[pivot]이면 j를 1증가하고, list[i]와 list[j]를 바꿉니다.
이를 i = 1부터 끝까지 반복합니다.


그럼 최종적으로
list[] = {4, 2, 1, 3, 6, 8, 7, 5} 라는 배열이 만들어집니다.
여기서 pivot은 여전히 0이고
j는 3입니다.


그럼 list[pivot]과 list[j]를 바꿉니다.
=> list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}
이제 4의 위치는 정해졌으며 이를 기준으로 왼쪽 배열과 오른쪽 배열도 같은 로직을 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(NlogN), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(int pivot, int l, int r) {
    int j = pivot;
    for (int i = pivot + 1; i <= r; i++) {
        if (list[pivot] > list[i]) {
            swap(list[++j], list[i]);
        }
    }
    swap(list[pivot], list[j]);
    
    return j;
}
 
void quickSort(int l, int r) {
    if (l < r) {
        int pivot = partition(l, l, r);
        quickSort(l, pivot - 1);
        quickSort(pivot + 1, r);
    }
}
 cs

 

'algorithm > Theory' 카테고리의 다른 글

좌표 압축 (Coordinate Compression)  (2) 2022.08.24

 

www.acmicpc.net/problem/8980

 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

처음에는 보내는 마을 기준으로 오름차순 정렬하였으나, 반례를 만나고 소스를 갈아엎고 받는 마을 기준으로 오름차순 정렬하였습니다.

 

우선 to배열에는 해당 마을을 지날때 최대용량으로 초기화를 시켜놓았습니다.

다음은 예제로 설명을 하겠습니다.

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20

N = 4, C = 40, M = 6

택배 정보를 받는 마을 기준으로 정렬하면 이렇게됩니다. to[1] = 40, to[2] = 40, to[3] = 40

1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20

이제 1 -> 2로 10만큼을 보냅니다.

도착마을인 2를 제외하고 1 -> 2 경로에 있는 마을의 남은 용량의 최소는 40으로 10보다 큽니다.

그러면 to[1]에서 10만큼 빼줍니다.

(ans = 10)

to[1] = 30, to[2] = 40, to[3] = 40

 

다음 1 -> 3으로 20만큼 보냅니다.

도착마을인 3을 제외하고 1 -> 3 경로에 있는 마을의 남은 용량의 최소는 30으로 20보다 큽니다.

그러면 to[1]와 to[2]에서 20만큼 빼줍니다.

(ans = 10 + 20 = 30)

to[1] = 10, to[2] = 20, to[3] = 40

 

다음 2 -> 3으로 10만큼 보냅니다.

도착마을인 3을 제외하고 2 -> 3 경로에 있는 마을의 남은 용량의 최소는 20으로 10보다 큽니다.

그러면 to[2]에 10만큼 빼줍니다.

(ans = 30 + 10 = 40)

to[1] = 10, to[2] = 10, to[3] = 40

 

다음 1 -> 4로 30만큼 보냅니다.

도착마을인 4를 제외하고 1 -> 4 경로에 있는 마을의 남은 용량의 최소는 10으로 30보다 작습니다.

따라서 남은 용량의 최소만큼인 10만큼 빼줍니다.

(ans = 40 + 10 = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 2 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 2 -> 4 경로에 있는 마을의 남은 용량의 최소는 0이므로 보낼 수 없습니다.

(ans = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 3 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 3 -> 4 경로에 있는 마을의 남은 용량의 최소는 40으로 20보다 큽니다.

그러면 to[3]에 20만큼 빼줍니다.

(ans = 70)

to[1] = 0, to[2] = 0, to[3] = 20

 

과정이 모두 끝났으니 ans를 출력해줍니다.

 

 

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
65
66
67
68
69
70
71
72
73
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<int[]> list = new ArrayList<>();
    static int to[];
    static int N, C, M, ans;
 
    static void func() {
        for (int i = 0; i < M; i++) {
            int u = list.get(i)[0];
            int v = list.get(i)[1];
            int c = list.get(i)[2];
 
            int maxC = Integer.MAX_VALUE;
            for (int j = u; j < v; j++)
                maxC = Math.min(maxC, to[j]);
 
            if (maxC >= c) {
                for (int j = u; j < v; j++)
                    to[j] -= c;
                ans += c;
            } else {
                for (int j = u; j < v; j++)
                    to[j] -= maxC;
                ans += maxC;
            }
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int u, v, c;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        to = new int[N + 1];
        Arrays.fill(to, C);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            list.add(new int[] { u, v, c });
        }
 
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1])
                    return a[0] - b[0];
                else
                    return a[1] - b[1];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > Greedy' 카테고리의 다른 글

boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16

+ Recent posts

티스토리툴바