신입 개발자를 위한 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

문제 : 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

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

풀이 방법


이 문제는 딱 보았을 때 간단하게 풀면 되겠다라고 생각을 했습니다. 하지만, mid라는 바구니를 기준으로 해서 end ~ mid 까지 그리고 begin의 순서로 바구니의 순서를 바꿔야 하는데, 처음에 mid ~ end까지 바꾸고 나서 그 다음에 begin ~ mid까지 바꾸려고 하는데 중간에 begin부터의 값을 가지고 있는 상태를 만들어주는 것을 못했습니다. 이 부분은 문제를 풀고 나서 깨닫게 되었는데, 일단 한번 더 시도해보려고 생각 중입니다.

C++을 rotate 기능이 있는데, 자바는…ㅜㅜ 노력해봅시다!!

Comment and share

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

풀이 방법


  1. 첫 번째 풀이
    이 문제는 어제 풀었던 도현이의 바구니 시리즈편인 것 같습니다. 그래서 이 문제도 간단하게 배열로 구현했습니다… 하지만, 정답이 틀렸다는 결과가,ㅜㅜ 그래서 무엇이 틀린지 코드를 분석해보는데 틀린 부분이 없었습니다.

제가 푼 방식은 우선, 바구니를 뒤집을 범위를 입력 받고 난 다음에 i부터 (i+j)/2 까지 반복문을 돌면서 조건을 검사합니다. int형 변수인 temp를 만듭니다. i번째 바구니와 j번째 바구니를 바꾸고, (i+1)번째 바구니와 (j-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
package language;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ10811 {
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());

for(int m=i;m<=(i+j)/2;m++){
int temp = arr[m];
arr[m] = arr[j];
arr[j] = temp;
j--;
}
}

for(int i=1;i<arr.length;i++)
System.out.print(arr[i]+" ");
}

}
  1. Stack을 이용한 풀이
    내 생각에는 정확히 풀었다고 생각을 했는데, 결과는 틀렸다고 했습니다… 그래서 다른 사람들은 도대체 어떻게 풀었으며 제가 예전에 어떻게 풀었는지 확인해보았습니다. 먼저, 예전에 저는 자바가 아닌 C++을 이용해서 풀었습니다. 도움이 되지 않으니 패스, 그리고 다른 사람들은 Stack을 이용해서 문제를 풀었습니다. 사람들은 왜 Stack을 사용해서 풀었는지 의문이 생겼고 직접 Stack을 이용해서 문제를 풀어보았습니다.

Stack은 후입선출(LIFO)의 구조를 가지는 자료구조입니다. 문제에서 원하는대로 바구니를 뒤집을 범위를 입력받으면 Stack에 push하고 다시 pop을 해서 원래 배열에 담으면 뒤집어진 상태로 출력이 되기 때문에 원하는 결과를 얻을 수 있습니다.

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
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ10811 {
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++) {
Stack<Integer> stack = new Stack<>();
st = new StringTokenizer(bf.readLine(), " ");
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());

for (int m = i; m <= j; m++)
stack.push(arr[m]);

for (int m = i; m <= j; m++)
arr[m] = stack.pop();
}

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++)
sb.append(arr[i] + " ");

bw.write(sb.toString() + "\n");
bw.flush();
bw.close();
bf.close();
}

}

배운점


가끔 다른 사람의 코드를 참고하여 문제를 이해하거나 풀이를 확인해서 로직을 이해하는데 이로 인해 배움을 얻고 이해를 하는 것이 좋은 과정이라고 생각합니다. 굿굿~

Comment and share

Author's picture

VictoryWoo

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


Android Developer