알고리즘 문제를 풀면서 다익스트라 알고리즘과 관련된 내용이 나왔다. 잘 모르는 부분이 있어서 기억하기 위해 정리하려 한다.

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 출발점에서 도착점까지의 최단거리를 구할 때 사용하는 알고리즘이다.

주로 사용하는 변수 두개가 있다.

1
2
int[] distance = new int[n+1];
boolean[] visit = new boolean[n+1];

distance 배열에는 각각의 노드까지의 최단 거리가 저장된다.
visit 배열에는 각각의 노드를 방문했는지 여부를 표시하여 저장한다.

다익스트라 알고리즘의 순서는 다음과 같다.

  1. 최단 거리를 저장하는 distance 배열에는 처음에 나올 수 있는 가장 큰 값으로 초기화 해준다. 보통 Integer.MAX_VALUE 값으로 초기화 한다.
  2. 시작 노드의 거리를 0으로 표시한다. (이는 당연하다. 자기 자신까지의 거리는 0이기 때문.) 그리고 시작 노드의 visit 값을 true로 바꿔준다.
  3. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신한다.
  4. 방문하지 않은 노드 중 distance 값이 최소인 노드 min_node를 찾는다.
  5. min_node의 visit 값을 true로 변경한다. 그리고 min_node와 연결된 노드들(방문하지 않은)의 distance 값을 갱신한다. 이때, min_node와 연결된 distance 값이 distance[min_node] + min_node와 그 노드의 거리 보다 큰 경우 distance 값을 distance[min_node]+ min_node와 그 노드의 거리로 갱신해준다.

4 ~ 5번을 모든 노드를 방문할 때까지 반복한다.

이렇게 순서를 설명했지만, 말로 설명하는 것보다는 그림을 보면서 이해하는 편이 더 빠를 것이다.

다음과 같은 그래프가 존재하고 시작점은 1이라고 가정한다. 그리고 간선에 표시되어 있는 값들은 가중치로 생각하면 된다.

  1. distance 값을 초기화 해준다.
node 1 2 3
distance 무한대 무한대 무한대
visit false false false
  1. 시작 노드가 1이므로 시작 노드의 distance와 visit 값을 변경해준다.
node 1 2 3
distance 0 무한대 무한대
visit true false false
  1. 시작 노드와 연결되어 있는 distance 값을 갱신한다.
node 1 2 3
distance 0 2 4
visit true false false
  1. 방문하지 않은 노드 중 distance가 최소인 값을 찾는다. 노드 2가 될 것이다.

  2. 최소인 노드2의 visit 값을 true로 변경한다.

node 1 2 3
distance 0 2 4
visit true true false

여기서는 노드 2와 연결되면서 방문하지 않은 노드들(여기서 노드 3)에 대해서 distance(3) > distance(2) + (2번과 3번 거리) 조건이 참이면 distance(3) = distance(2) + (2번과 3번 거리) 를 통해서 distance 값을 갱신한다.

3번까지의 거리는 4이고, 2번까지의 거리는 2 + 2와 3거리는 1이므로 4 > 2+1 이 성립된다. 따라서 distance(3)은 3으로 갱신된다.

node 1 2 3
distance 0 2 3
visit true true false

이처럼 노드 3의 distance 값은 더 최소인 값으로 갱신된다.

다익스트라 알고리즘과 관련된 문제는 알고스팟이라는 문제이다.

참고

Comment and share

신입 개발자를 위한 Repository를 만들었습니다. 공부한 내용을 정리 중이니 도움이 되신다면 와서 Star를 눌러주시면 감사하겠습니다.

알고리즘 문제를 풀다가 완전 탐색으로 해결하면 시간 초과가 나서 어떻게 풀어야 하는가 하다가 검색해보니 투 포인터 알고리즘이라는 개념이 나와서 간단하게 정리하고 넘어가겠다.

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 이 때문에 투 포인터 알고리즘이라고 부른다.

대표적인 문제

문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트해보면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 (N^2)이 된다. 따라서 문제를 풀 수 없다.

이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 다음과 같다.

  • 포인터 2개를 준비한다. 시작과 끝을 나타낼 수 있도록 start, end라고 하겠다.
  • 맨 처음에는 start = end = 0이며, 항상 start<=end 을 만족해야 한다.
  • 이 두개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 한다.

s = e일 경우 그건 크기가 0인 즉, 아무것도 포함하지 않는 부분 배열을 뜻한다. 이제 아래의 과정을 start<N 인 동안 반복한다.

  1. 현재 부분합이 M 이상이거나, 이미 end = N이면 start++
  2. 그렇지 않다면 end++
  3. 현재 부분합이 M과 같다면 count++

쉽게 이해하자면, start와 end를 무조건 증가시키는 방향으로만 변화시켜가면서, 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다.

그림으로 보는게 편하다. 그림을 그리기에는 시간이 좀 걸려서 내가 보고 이해한 그림을 첨부하겠다. 아래 참고한 블로그를 보면 설명을 아주 잘해주셨다. 이것만 보면 이해가 될 것이다.

대표적인 문제를 풀어봤다. 백준 2003번으로 수들의 합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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* 투포인터 알고리즘
* start : 시작
* end : 끝
*/
public class Main {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = parse(input[0]);
int m = parse(input[1]);

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

String[] num = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
arr[i] = parse(num[i - 1]);
}

int start = 0, end = 0, sum = 0, count = 0;

while (true) {
// 부분합이 m 보다 큰 경우 start 가 가리키는 원소를 빼고
// start 의 값을 증가시킨다. 즉, start 뒤로 이동.
if (sum >= m) {
sum = sum - arr[start++];

// end 가 n 에 도달하면 종료한다.
} else if (end == n) {
break;
} else {
// 위의 두 경우에 해당하지 않으면 end 는 뒤로 이동하면서 원소의 값을
// sum 에 더한다.
sum = sum + arr[end++];
}

// 부분 합이 m 과 같다면 count 를 증가시켜준다.
if (sum == m) {
count++;
}
}
System.out.println(count);
}

private static int parse(String str) {
return Integer.parseInt(str);
}
}

참고

Comment and share

알고리즘을 푸는데 백트래킹 문제가 나왔다. 근데, 백트래킹의 정확한 의미를 잘 몰라서 간략하게 정리하려고 한다.

백트래킹

위키피디아의 정의를 보면 한정 조건을 가진 문제를 풀려는 전략이라고 나와있다. 즉, 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때만 살펴본다.

설명을 덧붙이자면, 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색한다.

  • 유망성은 조건을 만족하는가 아닌가를 뜻한다.
  • 즉, 유망하지 않으면 배제를 하고 부모 노드로 돌아가서 풀이 시간이 단축될 수 있다.
  • DFS에서 가지치기를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 중 하나이다.

백트래킹의 대표적인 문제는 N-Queen 문제이다. 이 문제를 통해서 백트래킹을 한 번 더 이해해보자.

N-Queen

크키가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구해보자.

4x4를 기준으로 문제를 풀어보자. 퀸이 어떻게 이동할 수 있는지만 알면 체스가 무엇인지 몰라도 된다. 퀸은 배치된 칸을 기준으로 오와 열, 대각선 이동이 가능한 말이다.

빨간색 선이 퀸이 이동할 수 있는 경로이고, 첫 번째로 배치된 퀸과 공격할 수 없도록 배치하려면 2번째 줄은 2,3번 위치에 퀸을 놓아야 조건을 만족시킬 수 있다. 첫 번째 퀸의 위치를 (1,1)로 하면 트리구조는 다음과 같다.

이 문제를 가지치기를 하지 않는 DFS로 풀었다면 유망하지 않는 즉, 조건에 위배하는 (2,1), (2,2) 지점도 검사했을 것이다. 그러면 연산 횟수가 많아져 시간복잡도도 증가했을 것이다.

그래서 백트래킹에서 가지치기를 잘해야 한다. 백트래킹은 크게 4가지 절차로 구성되어 있다.

  1. DFS 수행 - 평소와 같이 깊이 우선 탐색인 DFS를 수행하여 노드를 찾는다.
  2. 유망한 노드 검토 - 방문한 노드를 포함해서 유망한 노드이면 서브트리(하위노드)로 이동하고 그렇지 않으면 백트래킹을 수행하낟.
  3. 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS를 수행한다.
  4. 백트래킹 수행 - 방문한 노드를 가지치기를 하고 상위 노드로 백트래킹한 후 DFS를 다시 수행한다.
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

import java.util.Scanner;

/**
* 22/05/2019
* 완탐 : N-Queen
* 백트래킹의 대표적인 문제.
*/
public class Main {
private static int N = 0;
private static int count = 0;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();

for (int i = 1; i <= N; i++) {
int[] column = new int[N + 1]; // N행 까지 담기 위해. index -> 행, value -> 열.
column[1] = i; // 1행 i열에 퀸을 놓음.

// 1. DFS 수행.
// 1행 i 열에 퀸을 놓았을 경우 dfs 로 가능한 경우를 확인한다.
dfs(column, 1);
}

System.out.println(count);
}

private static void dfs(int[] column, int row) {
// row 와 N 이 같다는 말은 N 번째 행까지 퀸을 놓았다는 의미이다.
// 즉, 퀸을 다 놓았다는 말! 따라서 count 를 증가시킨다.
if (row == N) {
count++;
} else {
for (int i = 1; i <= N; i++) {
column[row + 1] = i; // (row+1)행 i열에 퀸을 놓는다.

// 2. 유망한 노드인지 판단.
if (isPossible(column, row + 1)) {
// 3. 서브 트리로 이동.(해당 노드의 하위 노드)
dfs(column, row + 1);
}else {
// 4. 백트래킹 수행. 해당 노드는 가지치기 됨.
// 아니면 백트래킹. 0이면 퀸을 못놓는다는 의미.
column[row+1] = 0;
}
}
}
column[row] = 0;
}

private static boolean isPossible(int[] column, int row) {

// (row+1)이 들어오는데 그 전까지 즉, row 행 전까지 검사한다.
for (int i = 1; i < row; i++) {

// i 행과 row 행의 열이 같으면 퀸을 놓을 수 없다.
if (column[i] == column[row]) {
return false;
}
// i 행과 row 행의 열 값이 대각선 위치에 존재하면 퀸을 놓을 수 없다.
if (Math.abs(i - row) == Math.abs(column[i] - column[row])) {
return false;
}

}
// 위의 경우가 모두 된다면 true 반환한다.
return true;

}
}

참고

Comment and share

실력을 쌓아 알고리즘 문제를 풀려는 계획을 가지고 있었는데, GoodGid님께서 팩폭을 해주셔서 그 분의 커리큘럼을 따라가는 중입니다. 그래서 프로그래머스의 leve1,2 수준의 문제를 먼저 풀고 나태 지옥에 빠지지 않기 위해 푼 문제를 포스팅 할 계획입니다.

level1을 못풀면 코딩 접어야 한다고 했는데, 다행히도 접을 정도는 아닌가봅니다.

소수의합

어려울 줄 알았지만, 생각보다 간단한 문제입니다. N이 주어지면 2부터 N까지의 소수의 합을 구하면 됩니다. 소수의 대한 간단한 정의는 다음과 같습니다.

1과 자기 자신으로만 나누어 떨어지는 수

이에 반대로 1과 자기 자신이 아닌 수로 나누어 떨어지면 소수가 아니라는 생각을 했고 이를 아래와 같이 구현했습니다.

  • 이미 나누어 떨어짐에도 불구하고 for문을 돌면서 나머지를 계속 검사하기 때문에 break 추가해서 문제 해결!
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
import java.io.*;

public class ex1 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
int total = 0; // 소수의 합
Boolean isPrime = false;

for(int i=2;i<=N;i++){
isPrime = true;

for(int j=2;j<i;j++) {
// 이 부분은 입력받은 수가 1과 자기 자신을 제외한 수로 나누는 과정
// 이 과정에서 나누어 떨어진다는 것은 소수가 아닌 배수임을 의미
// 그렇기 때문에 한번 들어오면 어차피 소수가 아님으로 낭비를 줄이고자
// break문으로 빠져나옴.
if (i % j == 0) {
isPrime = false;
break;
}

}

if(isPrime == true)
total += i;

}

bw.write(total+"");
bw.flush();
bw.close();
}
}

에라토스테네스의체

Comment and share

문제 : https://www.acmicpc.net/problem/10814

풀이방법


이 문제는 너무 너무 간단한 문제입니다. 정렬 시리즈 중에 하나로 나이순으로 정렬하고 나이가 같다면 먼저 가입한 순서로 정렬하게 됩니다. 여기서 먼저 가입한 순서는 먼저 입력된 순서와 같으므로 입력될 때 list에 Member이라는 클래스에 index를 추가로 가지게 하여 구현했습니다.

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
import java.io.*;
import java.util.*;

public class BOJ10814 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
List<Member> list = new ArrayList<>();
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int age = Integer.parseInt(st.nextToken());
String name = st.nextToken();
list.add(new Member(age, name, (i+1)));
}

Collections.sort(list, new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
if(o1.age>o2.age){
return 1;
}else if(o1.age == o2.age){
if(o1.order>o2.order){
return 1;
}else {
return -1;
}
}else {
return -1;
}
}
});

for(int i=0;i<list.size();i++)
bw.write(list.get(i).age+" "+list.get(i).name+"\n");

bw.flush();
bw.close();
bf.close();

}
}
class Member{
int age;
String name;
int order;

public Member(int age, String name, int order){
this.age = age;
this.name = name;
this.order = order;
}
}

Comment and share

문제 : https://www.acmicpc.net/problem/10825

풀이방법


최근 푼 문제들은 정렬 시리즈 인 것 같습니다.ㅎㅎㅎㅎ 아무튼! 오늘은 학생들의 국,영,수 점수를 입력받아서 조건에 따라 정렬을 하는 문제입니다. 학생 이름, 국어, 영어, 수학 점수를 갖는 Student 클래스를 만들고 List를 만들어서 add를 통하여 추가해줍니다.

그리고 Comparator를 이용해서 객체의 요소들끼리 비교를 통해서 원하는 정렬을 진행합니다.

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
import java.io.*;
import java.util.*;

public class BOJ10825 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
List<Student> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
String person = st.nextToken();
int korean_grade = Integer.parseInt(st.nextToken());
int english_grade = Integer.parseInt(st.nextToken());
int math_grade = Integer.parseInt(st.nextToken());
list.add(new Student(person, korean_grade, english_grade, math_grade));

}

Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {

if (o1.korean == o2.korean) {
if (o1.english == o2.english) {
if (o1.math == o2.math) {
// 이름에 대해서는 오름차순 정렬으로!

return o1.name.compareTo(o2.name);
} else if (o1.math > o2.math) {
return -1;
} else {
return 1;
}
} else if (o1.english > o2.english) {
return 1;
} else {
return -1;
}
} else if (o1.korean > o2.korean) {
return -1;
} else {
return 1;
}
}
});

for (int i = 0; i < list.size(); i++)
bw.write(list.get(i).name + "\n");

bw.flush();
bw.close();
bf.close();

}
}

class Student {
String name;
int korean;
int english;
int math;

public Student(String name, int korean, int english, int math) {
this.name = name;
this.korean = korean;
this.english = english;
this.math = math;
}
}

배운점


최근에 Comparator 혹은 Comparable을 구현해서 정렬하는 문제를 풀어보았는데, 잘 알아두면 추후에 유용하게 쓸 수 있을 것 같다는 생각이 듭니다. 이 문제는 조건에 따라서 if~else 문으로 분기하여 푸는 간단한 문제이지만, 나중에는 더 어려운 문제가 나올 것이므로 미리미리 이 개념을 익혀 두는 것이 도움이 될 것 같다고 느꼈습니다. :)

Comment and share

문제 : https://www.acmicpc.net/problem/11651

풀이방법


어제 풀었던 좌표 정렬하기 문제에서 x를 기준으로 정렬했다면 이 문제는 y를 기준으로 정렬하고 y좌표의 값이 같으면 x좌표를 오름차순으로 정렬하는 문제입니다. 어제 언급했던 Comparable or Comparator을 활용해서 문제를 풀 수 있는지 확인하는 문제입니다.

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
import java.io.*;
import java.util.*;

public class BOJ11651 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
List<Point> list = new ArrayList<>();

for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
list.add(new Point(x, y));
}

Collections.sort(list, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if(o1.y == o2.y){
if(o1.x>o2.x){
return 1;
}else if(o1.x<o2.x){
return -1;
}else {
return 0;
}
}else if(o1.y>o2.y){
return 1;
}else if(o1.y<o2.y){
return -1;
}else {
return 0;
}
}
});

for(int i=0;i<list.size();i++)
bw.write(list.get(i).x+" "+list.get(i).y+"\n");
bw.flush();
bw.close();
bf.close();
}
}
class Point {
int x;
int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

Comment and share

문제 : https://www.acmicpc.net/problem/11650

풀이방법


이 문제는 어제 풀어보았던 단어 정렬 문제와 비슷한 유형입니다. 바로 Comparator 혹은 Comparable을 구현해서 정렬하는 문제입니다. 그럼 여기서 의문이 생길 수 있습니다.

그냥 sort를 사용해서 정렬을 하면 되는데, 왜 저런 것을 사용하는거지??

sort는 하나의 값을 기준으로 정렬할 때 사용할 수 있지만, 객체를 정렬할 때는 사용하지 못하기 때문입니다. 즉 객체의 어떤 속성(값)을 기준으로 정렬할 지 모호하기 때문에 Comparable 혹은 Comparator를 구현해서 원하는 정렬을 진행해야 합니다. 사용법만 안다면 간단하게 구현할 수 있습니다.

  1. Comparable 구현
    Comparable은 객체가 될 클래스가 Comparable을 구현함으로써 사용 가능합니다. compareTo라는 함수를 오버라이드 해서 클래스의 객체인 Coordinates와 this의 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
47
48
49
50
51
52
53
54
55
56
57
58
import java.io.*;
import java.util.*;

public class BOJ11650 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
List<Coordinates> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
list.add(new Coordinates(x, y));
}

Collections.sort(list);

for (int i = 0; i < list.size(); i++)
bw.write(list.get(i).x + " " + list.get(i).y + "\n");

bw.flush();
bw.close();
bf.close();
}
}

class Coordinates implements Comparable<Coordinates> {
int x;
int y;

public Coordinates(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int compareTo(Coordinates o) {
// 오름 차순일 경우
// this를 기준으로 함
// this가 크면 1, this가 작으면 -1 : 오름차순 정렬!
// 여기서 비교하는 값은 o라는 객체가 됨.
if (this.x > o.x) {
return 1;
} else if (o.x == this.x) {
if (this.y > o.y) {
return 1;
} else {
return -1;
}
} else if (this.x < o.x) {
return -1;
} else {
return 0;
}
}
}
  1. Comparator 구현
    Comparator를 구현하면 compare()라는 메소드를 오버라이드 합니다. 이 함수는 매개 변수로 두 개의 객체가 들어있어서 두 개의 객체를 비교하여 리턴하는 값에 따라서 정렬된 값을 알 수 있습니다. 두 객체를 비교해서 음수, 0, 양수를 반환하도록 합니다. Comparator를 구현하면 기본 정렬 외에도 다른 기준으로 정렬하고자 할 때 사용할 수 있습니다.
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
package language;

import java.io.*;
import java.util.*;

public class BOJ11650 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(bf.readLine());
List<Coordinates> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
list.add(new Coordinates(x, y));
}


// Comparator를 이용한 방법
list.sort(new Comparator<Coordinates>() {
@Override
public int compare(Coordinates o1, Coordinates o2) {
// o1을 기준으로 잡는다.
// o2가 비교하는 객체가 된다.
// 오름 차순!

if (o1.x == o2.x) {
if (o1.y > o2.y) {
return 1;
} else {
return -1;
}
}else if(o1.x>o2.x){
return 1;
}else if(o1.x<o2.x){
return -1;
}else {
return 0;
}
}
});

Collections.sort(list);

for (int i = 0; i < list.size(); i++)
bw.write(list.get(i).x + " " + list.get(i).y + "\n");

bw.flush();
bw.close();
bf.close();
}
}

class Coordinates {
int x;
int y;

public Coordinates(int x, int y) {
this.x = x;
this.y = y;
}

}

참고 : Collection Framework 중 Comparable, Comparator에 관한 내용

Comment and share

문제 : https://www.acmicpc.net/problem/1181

풀이 방법


  1. 첫 번째 시도
    처음에는 간단하게 배열로 입력받은 문자열을 담은 다음에 Comparable을 구현한 클래스를 통해서 정렬을 하려고 했습니다. 하지만, 문자열의 길이순으로는 정렬이 되는데, 문자열의 길이가 같은 경우에는 사전 순으로 먼저 나오는 단어가 출력되고 그 다음 단어가 출력되는 형식으로 결과를 도출해야 합니다. 하지만, 배열을 사용할 경우에 그렇게 하기란 쉽지 않았습니다.
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
import java.io.*;
import java.util.Arrays;

public class BOJ1181 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


int N = Integer.parseInt(bf.readLine());
Data[] arr = new Data[N];
for(int i=0;i<N;i++){
String input = bf.readLine();
arr[i] = new Data(input,input.length());

}


Arrays.sort(arr);

for(int i=0;i<N;i++)
bw.write(arr[i].name+"\n");

bw.flush();
bw.close();
bf.close();


}

}

class Data implements Comparable<Data>{
String name;
int length;

public Data(String name, int length){
this.name = name;
this.length = length;
}

@Override
public int compareTo(Data o) {
if(this.length>o.length){
System.out.println("here 0");
return 1;
}else if(this.length<o.length){
System.out.println("here -1");
return -1;
}else {
return 0;
}
}
}
  1. 두 번째 방법
    문제를 자세히 읽어보니 이미 나온 단어가 또 나오면 한번만 출력한다고 합니다. 이 뜻은 중복을 허용하지 않는다는 뜻이므로, Set을 이용할 수 있다는 의미입니다. 또한, Set을 이용해서 데이터를 add 하고 나서 List list = new ArrayList<>(set); 을 통해서 Set을 List의 생성자에 대입할 수 있습니다.

그로 인해서 Set이 List가 되어서 Collections.sort를 통해서 입력 받은 문자열들을 먼저 사전순으로 정렬할 수 있습니다. 그 후에, Comparator를 구현하여 문자열의 길이순으로 오름차순 정렬을 수행할 수 있습니다.

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
import java.io.*;
import java.util.*;

public class BOJ1181 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


int N = Integer.parseInt(bf.readLine());
Set<String> set = new HashSet<>();
for (int i = 0; i < N; i++) {
String input = bf.readLine();
set.add(input);

}

List<String> list = new ArrayList<>(set);

// 일단 사전순으로 먼저 정렬
Collections.sort(list);

// 길이순으로 정렬
// Comparator을 구현함.
// compare 함수를 오버라이드하여 길이로 비교함
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() > o2.length())
return 1;
else if (o1.length() < o2.length())
return -1;
else
return 0;
}
});


// 출력
for (int i = 0; i < list.size(); i++)
bw.write(list.get(i) + "\n");

bw.flush();
bw.close();
bf.close();


}

}

배운 점


1일 1 알고리즘을 실천하기 위해서 매일 알고리즘을 풉니다. 그리고 지금은 기초 단계이기 때문에 비교적 쉬운 문제이지만 기초를 잘 다져놔야 추후에 난이도 있는 문제도 풀 수 있다고 생각합니다. 오늘처럼 분명 사용해보았지만 기억이 나지 않았던 부분들은 확실하게 기억하고 넘어가야 할 필요가 있습니다.

오늘 나왔었던 개념은 문제를 자세히 읽어보고 어떠한 자료구조를 선택할 것인가를 잘 생각하고 문제를 이해하고 풀어야 한다는 것입니다. 이 부분은 자료구조에 대한 이해력을 더 높이고 공부를 더 해야 할 것 같습니다. 그리고 두 번째로는 Comparable 혹은 Comparator에 대한 내용입니다. 예전에 공부할 때 포스팅해 둔 내용이 있어서 잠깐 참고해서 보았습니다. 하지만, 이 부분도 시간이 지나면서 점차 기억 속에서 잊혀졌기 때문에 다시 한 번 보면서 개념을 상기시켜야 할 것 같습니다!! :)

Comparable or Comparator 내용 : https://woovictory.github.io/2018/03/08/java-collection-framework/

Comment and share

문제 : https://www.acmicpc.net/problem/10813

풀이방법


이 문제는 풀이방법을 말하기도 민망합니다…;; 왜냐하면 단순하게 Swap 하는 문제이기 때문이죠! 배열을 생성하고 공을 바꿔주기만 하면 되는 간단한 문제입니다:) 오늘은 간단한 문제들이기 때문에 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
import java.io.*;
import java.util.StringTokenizer;

public class BOJ10813 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

StringTokenizer st = new StringTokenizer(bf.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N+1];

for(int i=1;i<=N;i++)
arr[i]=i;

for(int k=0;k<M;k++){
st = new StringTokenizer(bf.readLine()," ");
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

for(int i=1;i<arr.length;i++)
bw.write(arr[i]+" ");

bw.flush();
bw.close();
bf.close();
}
}

Comment and share

Author's picture

VictoryWoo

기록을 통해 사람들과 공유하는 것을 좋아합니다.


Android Developer