백준 2485번: 가로수

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    List<Integer> differences = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    int preValue = 0;

    int n = Integer.parseInt(br.readLine());
    while (n-- > 0) {
        int input = Integer.parseInt(br.readLine());
        list.add(input);

        if (preValue != 0) {
            differences.add(Math.abs(preValue - input));
        }

        preValue = input;
    }

    Collections.sort(list);

    int gcd = Integer.MAX_VALUE;
    for (int i = 1; i < differences.size(); i++) {
        int temp = gcd(differences.get(i-1), differences.get(i));
        gcd = temp > gcd ? gcd : temp;
    }

    int answer = 0;
    int pre = list.get(0);
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i) - pre != gcd) {
            answer += ((list.get(i) - pre) / gcd) - 1;
        }
        pre = list.get(i);
    }

    System.out.println(answer);
}

private static int gcd(int a, int b) {
    return b!=0 ? gcd(b, a%b) : a;
}

흐름

  1. 입력 받은 값들을 뺀 값의 차를 구한 값으로 약수를 구하기 위한 differences,
    입력 받은 값을 그대로 저장하는 list 변수 생성.
  2. 두 리스트 모두 n 만큼 돌면서 값을 저장하는데
  3. differences의 경우 첫 번쨰 루프에서 값을 저장 할 수 없으므로(2 번쨰 값부터 첫 번째 값과 뺄 수 있으므로) 이전 값이 있는 경우에만 리스트에 저장한다.
  4. 가로수들 사이에 끼워넣어야 되는 가로수의 개수를 구해야 하므로 입력 받은 가로수의 위치를 정렬한다.
  5. 가로수 간의 최소 간격을 구하기 위해 아까 저장한 가로수 간의 차이를 구한 리스트 differences를 돌면서 유클리드 호제법을 이용해 최대공약수를 구하고, 구한 최대 공약수 중 가장 작은 값을 저장한다.
  6. 가로수 간의 차이값에서 최대 공약수를 구하는 이유는,
  7. 문제가 가로수를 일정한 간격으로 최대한 적게 심기게 하기 위한 문제 이므로 두 수에서 공통되는 값들 중 가장 큰 수인 최대 공약수를 구하고,
  8. 그 최대 공약수들 중 가장 작은 값이어야 모두 일정한 간격으로 심을 수 있으므로 최대 공약수 중 가장 작을 값을 구한다.
  9. 이렇게 잘 구한 값으로 이제 몇 개의 가로수를 더 심어야 하는지 알아내야 하므로
  10. 아까 정렬시킨 가로수 리스트를 반복 하면서 이전 가로수 와의 간격이 최대 공약수 보다 큰 녀석들이 있으면
  11. 그 녀석들 사이에 가로수를 심어야 되므로,
  12. 구한 간격을 최대 공약수로 나눈 값에서 -1 한 값을 더한다.
  13. 이 때 -1을 하는 이유는 두 수의 간격이므로 하나는 이미 심어져 있으니 -1 을 한다.
  14. 그렇게 추가로 심어야 하는 가로수의 개수를 모두 구하면
  15. 끝.

결과

댓글 공유

백준 10527번: Judging Troubles

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    Map<String, Boolean> isDuplicate = new HashMap<>();
    Map<String, Integer> domJudge = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (!isDuplicate.containsKey(input)) {
            isDuplicate.put(input, false);
        }

        domJudge.put(input, domJudge.getOrDefault(input, 0) + 1);
    }

    Map<String, Integer> kattis = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (isDuplicate.containsKey(input)) {
            isDuplicate.put(input, true);
        }

        kattis.put(input, kattis.getOrDefault(input, 0) + 1);
    }

    List<Map.Entry<String, Integer>> entries1 = new ArrayList<>(domJudge.entrySet());
    List<Map.Entry<String, Integer>> entries2 = new ArrayList<>(kattis.entrySet());

    entries1.addAll(entries2);
    Collections.sort(entries1, (e1, e2) -> {
        if (e1.getKey().compareTo(e2.getKey()) > 0) {
            return 1;
        } else if (e1.getKey().compareTo(e2.getKey()) < 0) {
            return -1;
        } else {
            return Integer.compare(e1.getValue(), e2.getValue());
        }
    });

    int answer = 0;
    Set<String> set = new HashSet<>();
    for (int i = 0; i < entries1.size(); i++) {
        Map.Entry<String, Integer> entry = entries1.get(i);

        if (isDuplicate.getOrDefault(entry.getKey(), false) && set.add(entry.getKey())) {
            answer += entry.getValue();
        }
    }

    System.out.println(answer);
}

흐름

  • 우선 이 문제는 domJudge와 kattis가 순서대로 n만큼씩 입력 받는 문제다.

예제를 보며 얘기하면

1
2
3
4
5
6
7
8
9
10
11
5
correct
wronganswer
correct
correct
timelimit
wronganswer
correct
timelimit
correct
timelimit

이렇게 되어 있을 때 위에 다섯 줄은 domJudge에서 채점한 결과고, 그 아래 다섯 줄은 kattis 채점한 결과다.

이걸 생각하고 프로그램을 작성하면

  1. 우선 양 쪽에서 채점된 결과들 중에 작은 녀석의 값을 골라야 하므로 채점 결과를 Key로 하는 Map을 만들고
  2. n 만큼 돌면서 domJudge의 채점 결과를 저장하는데 이 때 처음나온 채점 결과는 Map에 false로 저장하고, 이전에 이미 나온 결과는 +1 해준다.
  3. 그 후 다시 n만큼 돌면서 kattis의 채점결과를 저장하는데
  4. 이 때는 전에 domJudge에서 나온 채점 결과 인지 확인해야 하므로 중복을 체크하기 위해 만든 Map에 채점 결과가 존재하면 그 key의 값을 true로 변경시켜서 양 쪽에서 모두 나온 결과 임을 저장한다.
  5. 그 후 양 쪽에서 모두 나온 채점 결과들 중 작은 값들을 더하기 위해
  6. 두 Map을 리스트로 변환 후 합쳐서 key와 value로 sorting 한다.
  7. 그 후 합친 리스트를 반복하면서..
  8. 채점 결과가 양 쪽 모두에서 나온 녀석이면서 이전에 더한 key가 아니라면 쭉 더하고
  9. 출력하고 끝낸다.

결과

다른 분의 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine().trim();
    int n = Integer.parseInt(line);
    Map<String, Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        String dom = br.readLine();
        map.put(dom, map.getOrDefault(dom, 0) + 1);
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        String kattis = br.readLine();
        if(map.containsKey(kattis) && map.get(kattis) > 0){
            cnt++;
            map.put(kattis, map.get(kattis) - 1);
        }
    }
    System.out.println(cnt);
}
  • 나 처럼 바보 같이 Map을 여러 개 쓰지 않고 하나의 맵에 +1, -1로 해서 겹치는 결과 인지 아닌지 판단했다.
  • 나는 왜 이렇게 생각하지 못했을까? 다른 곳에서도 흔히 쓰이는 방식인데
  • 오늘도 역시 반성해본다…

댓글 공유

백준 1417번: 국회의원 선거

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    LinkedList<Integer> queue = new LinkedList<>();
    int dasom = Integer.parseInt(br.readLine());
    for (int i = 0; i < n-1; i++) {
        int input = Integer.parseInt(br.readLine());

        if (dasom <= input) {
            queue.offer(input);
        }
    }

    Collections.sort(queue);

    int answer = 0;
    for (; !queue.isEmpty() && queue.peekLast() >= dasom; answer++) {
        if (queue.peek() < dasom) {
            queue.poll();
        }

        queue.offer((queue.pollLast()-1));
        dasom++;

        Collections.sort(queue);
    }

    System.out.println(answer);
}

흐름

  1. 다솜이는 기호 1번이므로 첫 번째 입력을 다솜이의 표로 저장한다.
  2. 우선순위 큐로 사용하기 위해 list에 입력들을 저장하는데 다솜이 보다 작을 경우엔 문제의 답과 상관이 없으므로 다솜이의 표보다 적은 표는 큐에 저장하지 않는다.
  3. 우선순위 큐로서 동작하게 하기 위해 반복 전에 큐를 한번 정렬시켜준다.
  4. 그 후엔 큐가 비거나, 큐의 가장 큰 값이 다솜이가 될 때까지 반복한다.
  5. 반복하면서 큐의 맨 앞이 다솜이보다 작다면, 이제 그 사람은 다솜이가 재낀 것 이므로 큐에서 빼주고,
  6. 제일 표가 많은 놈한테서 표 하나를 뻇어서 다솜이가 가져가면 되므로 큐의 마지막 값에서 -1 빼서 다시 큐에 넣어준다.
  7. 그리고 제일 표가 많은 놈에게 뺏은 표를 다솜이에게 줬으므로 다솜이의 값을 1 증가시키고
  8. 우선순위 큐 처럼 동작 할 수 있게 큐를 다시 정렬 시킨다.
  9. 반복된 횟수를 출력하면 끝.

결과

여담

반복문에서 소팅을 하기 때문에 시간 초과가 날 것으로 예상했는데 수가 적은 문제라 그런지 무사히 통과되어 참 다행이다…

댓글 공유

백준 4796번: 캠핑

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringBuilder sb = new StringBuilder();
    int i = 0;

    String input = "";
    while (!"0 0 0".equals(input = br.readLine())) {
        int[] lpv = convertStringArrayToIntegerArray(input.split(" "));

        int l = lpv[0];
        int p = lpv[1];
        int v = lpv[2];

        sb.append("Case ").append(++i).append(": ").append((v/p) * l + ((v%p) > l ? l : (v%p))).append("\n");
    }

    System.out.println(sb);
}

private static int[] convertStringArrayToIntegerArray(String[] args) {
    int[] array = new int[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

흐름

  1. V일 중에 연속되는 P일 동안 L일 만큼 휴가를 사용 할 수 있으므로
  2. V에서 P를 나눈 값에서 L일을 곱하면 사용 가능한 휴가 일수가 구해지고
  3. L이 V일에서 P일을 나눈 값보다 작을 땐 L일 만큼 휴가를 더 갈 수 있고
  4. 큰 경우엔 V % P 일 만큼 갈 수 있으므로 구한 값을 더하면
  5. 총 휴가 일수를 구할 수 있다.

결과

댓글 공유

백준 18870번: 좌표 압축

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    Integer[] array = convertStringArrayToIntegerArray(br.readLine().split(" "));
    List<Integer> list = Arrays.asList(array.clone());

    Collections.sort(list);

    Map<Integer, Integer> map = new HashMap<>();
    int index = 0;
    for (int i : list) {
        if (!map.containsKey(i)) {
            map.put(i, index++);
        }
    }

    StringBuilder sb = new StringBuilder();
    for (int i : array) {
            sb.append(map.get(i)).append(" ");
    }

    System.out.println(sb.toString());
}

private static Integer[] convertStringArrayToIntegerArray(String[] args) {
    Integer[] array = new Integer[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

흐름

  1. 입력받은 좌표를 저장한 리스트로 수정하면 출력 순서를 맞출 수 없으니 우선 좌표 list를 복사한다.
  2. 복사한 list를 정렬하고 순서대로 반복하면서 좌표값을 key로 index를 저장한다.
    1. {-10 : 0}, {-9, 1}… {4,4}
  3. 입력받은 좌표를 순서대로 반복하면서 map에 key로 index를 가져온다.
  4. 끝

좌표 압축의 이유

좌표 {2 4 -10 4 -9} 압축 전
좌표 {2 4 -10 4 -9} 압축 후
  • 문제의 예제인 좌표 {2 4 -10 4 -9}을 위와 같은 알고리즘으로 압축하면 {2 3 0 3 1}이 되는데 위 그림 처럼 압축된 점들도 같은 동일선상 안에 놓이게 된다.
  • 이렇게 범위가 매우 넓은 좌표의 경우에 좌표를 인덱싱해서 처리 할 경우 손쉽게 처리 할 수 있게 된다.

결과

참고 사이트

댓글 공유

백준 1406번: 에디터

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    char[] input = br.readLine().toCharArray();

    LinkedList<Character> list = new LinkedList<>();
    for (char c : input) {
        list.add(c);
    }

    ListIterator<Character> it = list.listIterator();
    while (it.hasNext()) {
        it.next();
    }

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

    while (n-- > 0) {
        String command = br.readLine();

        switch (command) {
            case "L" :
                if (it.hasPrevious()) {
                    it.previous();
                }
                break;
            case "D" :
                if (it.hasNext()) {
                    it.next();
                }
                break;
            case "B" :
                if (it.hasPrevious() && !list.isEmpty()) {
                    it.previous();
                    it.remove();
                }
                break;
            default:
                it.add(command.charAt(2));
                break;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (char c : list) {
        sb.append(c);
    }

    System.out.println(sb);
}
  • 이 문제는 로직보다 걸리는 시간이 문제였다.
  • 처음엔 LinkedList를 그대로 사용해 add, remove를 했지만 시간초과로 인해 ListIterator을 이용해 해결했다.

ListIterator

  • List를 양방향으로 탐색하고, 루프 중에 리스트를 수정하고, 리스트에서 현재 위치를 가져올 수 있다.
  • 커서는 previous()로 리턴되는 원소와 next()로 리턴되는 원소 사이에 존재한다.
1
2
                    Element(0)   Element(1)   Element(2)   ... Element(n-1)
cursor positions:  ^            ^            ^            ^                  ^
  • remove()와 set()를 호출해도 커서의 위치는 움직이지 않는다.
  • remove() 호출 시 next()혹은 preivous()에 의해 리턴된 마지막 요소를 리스트에서 제거한다.
1
2
3
4
5
6
case "B" :
        if (it.hasPrevious() && !list.isEmpty()) {
            it.previous();
            it.remove();
        }
        break;

결과

참고 사이트

댓글 공유

백준 11724번: 연결 요소의 개수

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] nm = convertStringArrayToIntegerArray(br.readLine().split(" "));
    int n = nm[0];
    int m = nm[1];

    boolean[][] graph = new boolean[n+1][n+1];
    while (m-- > 0) {
        int[] xy = convertStringArrayToIntegerArray(br.readLine().split(" "));

        graph[xy[0]][xy[1]] = true;
        graph[xy[1]][xy[0]] = true;
    }

    int answer = 0;

    boolean[] isVisit = new boolean[n+1];
    for (int i = 1; i < graph.length; i++) {
        if (!isVisit[i]) {
            answer += bfs(isVisit, graph, i);
        }
    }

    System.out.println(answer);
}

private static int[] convertStringArrayToIntegerArray(String[] args) {
    int[] array = new int[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

private static int bfs(boolean[] isVisit, boolean[][] graph,int startIndex) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startIndex);
    isVisit[startIndex] = true;

    while (!queue.isEmpty()) {
        int x = queue.poll();

        for (int i = 1; i < isVisit.length; i++) {
            if (isVisit[i]) {
                continue;
            }

            if (graph[x][i]) {
                queue.offer(i);
                isVisit[i] = true;
            }
        }
    }

    return 1;
}

흐름

  1. 그래프의 연결 관계를 인접행렬로 만들기 위해 정점의 개수 + n한 크기의 2차원 배열을 만들고,
  2. 이 문제에서 그래프는 방향이 없는 무방향 그래프이기 때문에 a->b로 가는 간선이 있으면 b->a로 가는 간선도 있는 것이므로 대칭이 되도록 배열에 저장한다.
  3. 이후 정점의 개수만큼 루프 돌면서 연결요소의 개수를 구하는데 아직 간선이 연결되지 않은 정점일 경우에만 BFS 탐색을 통해 탐색한다.
  4. queue를 이용해 bfs를 구현하는데 우선 탐색이 시작되는 정점의 index를 queue에 저장하고, isVisit[] 변수에도 true로 해당 index를 탐색했다고 저장한다.
  5. queue가 빌 때 까지 반복하면서 queue에 저장된 index를 poll한다.
  6. 정점의 개수 만큼 반복하면서 이미 연결된 정점이면 넘어가고
  7. 아직 연결되지 않은 정점이면서 다른 정점과 연결된 정점이면 queue에 해당 index를 저장하고, 방문했으니 true도 저장한다.
  8. queue가 비어 루프가 종료되면 연결 요소 하나가 완성된 것이므로 1을 return 하고 bfs를 종료한다.
  9. return된 1들을 저장해 모든 정점을 탐색 후 종료한다.
  10. 끝

결과

참고 사이트

댓글 공유

백준 5525번: IOIOI

문제

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

코드

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
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    br.readLine();

    int answer = solution(n, br.readLine());

    System.out.println(answer);
}

public static int solution(int n, String target) {
    int answer = 0;

    char[] s = target.toCharArray();
    char[] targetString = getTargetString(n).toCharArray();
    int[] fail = failFunction(targetString);

    int start = 0;
    int m = 0;

    while (start <= s.length - targetString.length) {
        if (m < targetString.length && s[start + m] == targetString[m]) {
            ++m;
            if (m == targetString.length) {
                answer++;
            }
        } else {
            if  (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return answer;
}

private static String getTargetString(int n) {
    StringBuilder sb = new StringBuilder();
    sb.append("I");

    while (n-- > 0) {
        sb.append("OI");
    }
    return sb.toString();
}

private static int[] failFunction(char[] target) {
    int n = target.length;
    int[] fail = new int[n];

    int start = 1;
    int m = 0;

    while (start + m < n) {
        if (target[start + m] == target[m]) {
            m++;
            fail[start + m - 1] = m;
        } else {
            if (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return fail;
}

흐름

  1. S에서 찾을 문자열(targetString)을 만든다.
  2. 찾을 문자열에서 실패함수 값을 구한다.
  3. 배열의 범위를 벗어나기 전까지 반복한다.
  4. 검색 할 문자열 s에서 찾을 단어을 한 문자씩 비교한다.
  5. 한 문자가 같으면, 그 다음 문자를 비교 할 수 있게 m을 1씩 더해서 최종적으로 문자열에 단어가 포함되어 있으면 answer를 증가시킨다.
  6. 문자가 일치하지 않으면
    1. m이 0이면 시작도 못해본거니깐 검색 할 문자열에서 한 문자 뒤로 간다.
      ex) S = ABCDEF 일 경우, B부터 검색하도록 start를 증가
    2. 0이 아니면 단어에서 어느정도 일치한 문자열이 존재한 것이므로 비교 시작 할 문자의 index를 m에서 실패함수 값을 빼서 구한다.
    3. 일치한 문자열 뒤 부터 검색하면 되므로 m도 실패함수 값에서 구한다.
  7. 반복이 끝나면 answer 값을 return 한다.
  8. 끝.

KMP 알고리즘 해설

문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘

위키백과
  • 비교한 정보를 최대한 활용
  • 문자열 S = OOIOIIOIOIOIOIOIOIOIOOIOI 에서 패턴 M = IOIOI 를 찾는다고 가정
  • 우선 패턴 M의 실패함수를 구하기 위해 IOIOI에서 접두사와 접미사의 길이가 가장 긴 부분을 구한다.

실패함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int[] failFunction(char[] target) {
    int n = target.length;
    int[] fail = new int[n];

    int start = 1;
    int m = 0;

    while (start + m < n) {
        if (target[start + m] == target[m]) {
            m++;
            fail[start + m - 1] = m;
        } else {
            if (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return fail;
}
  1. IOIOI 패턴에서 index 1에 저장된 ‘O’와 0에 저장된 ‘I’는 같지 않으므로 비교가 시작되는 위치를 1 증가 시킨다. (현재 start = 2, m = 0)
  2. 루프에 의해 다시 비교하면 2에 저장된 ‘I’와 0에 저장된 ‘O’는 같으니 m을 증가시키고 접두사와 접미사가 일치한 값인 m를 저장한다. (현재 start = 2, m = 1)
    1. IOIOI에서 IOI까지 진행한 상태에서 I와 I가 일치 했으므로 길이 1이 일치한 것
  3. 3에 저장된 ‘O’과 1에 저장된 ‘O’가 같으므로, 다시 m을 1 증가 시키고 접두사와 접미사가 일치한 값인 m을 저장한다. (현재 start = 2, m = 2)
    1. IOIOI에서 IOIO까지 진행한 상태에서 ‘IO’와 ‘IO’가 같으므로 길이 2가 일치한 것
  4. 4에 저장된 ‘I’과 2에 저장된 ‘I’가 같으므로, 다시 m을 1 증가 시키고 접두사와 접미사가 일치한 값인 m을 저장한다. (현재 start = 2, m = 3)
    1. IOIOI는 접두사 ‘IOI’와 ‘IOI’의 길이가 3이므로 3
  5. array return
  6. 끝

KMP 알고리즘

  • 실패함수 값 구하는 것과 동일하다.
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
public static int solution(int n, String target) {
    int answer = 0;

    char[] s = target.toCharArray();
    char[] targetString = getTargetString(n).toCharArray();
    int[] fail = failFunction(targetString);

    int start = 0;
    int m = 0;

    while (start <= s.length - targetString.length) {
        if (m < targetString.length && s[start + m] == targetString[m]) {
            ++m;
            if (m == targetString.length) {
                answer++;
            }
        } else {
            if  (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return answer;
}
  • 실패함수 array [0, 0, 1, 2, 3]
  1. m이 패턴의 길이보다 작고, 문자열 s(OOIOIIOIOIOIOIOIOIOIOOIOI) 에서 start+m 한 index의 문자와 비교할 패턴(IOIOI)의 m 번째 문자가 같지 않으므로 s에서 비교가 시작되는 위치를 1 증가 시킨다. (현재 start = 1, m = 0)
  2. S의 1와 패턴의 0을 비교해도 여전히 같지 않으므로 시작 위치를 또 증가 시킨다. (start = 2, m = 0)
  3. S의 2와 패턴의 0을 비교하면 둘다 ‘I’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 1)
  4. S의 3와 패턴의 1을 비교하면 둘다 ‘O’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 2)
  5. S의 4와 패턴의 2을 비교하면 둘다 ‘I’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 3)
  6. S의 5와 패턴의 3을 비교하면 같지 않고 이제 m이 0이 아니므로,
  7. s의 시작 위치를 증가 시켜야 하는데 1을 증가 시키는게 아니라 이전에 구한 실패 함수 값에서 찾아온다.
    1. (m(3) - 실패함수 값 array[m(3) - 1]) = 2
    2. 즉 현재 시작 위치에서 1을 더한 값이 아닌 2를 더한다.
    3. 이미 index 4까지는 접두사 접미사가 2 자리까지 같기 때문에
  8. m 역시 실패함수 값을 가져온다.
    1. IOIOI에서 IOIO까지 비교한 값에서 실패했기 떄문에
    2. 그 이전 접미사 접두사 길이만큼으로 비교한다.
  9. 이 시점에서 start = 4, m = 1이 되고 루프를 반복한다.
  10. 4와 1은 같지 않으므로 다시 7번부터 8번까지 반복해서 start와 m을 조정한다.
    1. 이 예제로 하면 처음부터 같지 않았으므로 start는 한칸만 뒤로 가고
    2. m 역시 접두사 접미사 1 짜리도 실패했으므로 처음부터 비교한다.
    3. (start = 5, m = 0)
  11. (5, 0), (6, 1), (7, 2), (8, 3), (9, 4) 이 쭉~ 같으므로 드디어 문자열 s에서 패턴을 찾은 것이므로 answer을 증가 시킨다.
  12. 그 이후로 다시 비교하면 m의 길이가 패턴의 길이를 넘어 갔으므로,
  13. start와 m의 위치를 다시 조정한다.
  14. 반복
  15. 끝.
  • 결국 정리하면, 처음 말한 것 처럼 이미 비교한 값은 다시 비교하지 않고 그 다음 부터 비교하는 방식으로 시간을 줄인다.
  • 더 자세한 설명들은 글 마지막 참고 사이트를 찾아가면 다른 분들이 매우 자세하게 설명해주시고 계신다.

결과

테스트 케이스

1
2
3
assertEquals(4, test.solution(1, "OOIOIOIOIIOII"));
assertEquals(6, test.solution(2, "OOIOIIOIOIOIOIOIOIOIOOIOI"));
assertEquals(7, test.solution(1, "IOIOIOIOIOIOIOI"));

참고 사이트

댓글 공유

백준 18111번: 마인크래프트

문제

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

코드

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
74
75
76
77
78
79
80
81
82
83
84
public class 마인크래프트 {
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int[] nmb = convertStringArrayToIntegerArray(br.readLine().split(" "));

            int n = nmb[0];
            int m = nmb[1];

            int[][] ground = initGround(br, n, m);
            int[] minAndMax = getMinAndMax(ground);

            int[] timeAndHigh = getMinimumConstructionTime(ground, nmb[2], minAndMax[0], minAndMax[1]);

            System.out.println(timeAndHigh[0] + " " + timeAndHigh[1]);
        }
    }

    private static int[] convertStringArrayToIntegerArray(String[] args) {
        int[] array = new int[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    private static int[][] initGround(BufferedReader br, int n, int m) throws IOException {
        int[][] ground = new int[n][m];
        for (int i = 0; i < n; i++) {
            ground[i] = convertStringArrayToIntegerArray(br.readLine().split(" "));
        }

        return ground;
    }

    private static int[] getMinAndMax(int[][] ground) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int[] i : ground) {
            for (int j : i) {
                min = min > j ? j : min;
                max = max < j ? j : max;
            }
        }

        return new int[] {min, max};
    }

    private static int[] getMinimumConstructionTime(int[][] ground, int inventory, int min, int max) {
        int answerTime = Integer.MAX_VALUE;
        int answerHigh = 0;

        for (int currentHigh = min; currentHigh <= max; currentHigh++) {
            int up = 0;
            int down = 0;

            for (int i = 0; i < ground.length; i++) {
                for (int j = 0; j < ground[0].length; j++) {
                    int high = ground[i][j] - currentHigh;

                    if (high > 0) {
                        down += high;
                    } else if (high < 0) {
                        up -= high;
                    }
                }
            }

            if (down + inventory >= up) {
                int time = (down * 2) + up;

                if (answerTime >= time) {
                    answerTime = time;
                    answerHigh = currentHigh;
                }
            }
        }

        return new int[]{answerTime, answerHigh};
    }
}

흐름

  1. n * m 크기의 2차원 배열을 만들어서 저장한다.
  2. 땅 높이를 저장한 2차원 배열을 돌면서 가장 작은 높이와 가장 큰 높이를 구한다.
  3. 우선, 가장 낮은 높이부터 가장 높은 높이 까지 반복하면서
  4. 3번에 해당하는 높이를 기준으로 2차원 배열을 2중 루프 돌면서 모든 땅에서 현재 땅 높이를 뺀다. (int high = ground[i][j] - currentHigh;)
  5. 그 높이가 0보다 크면 기준이 되는 땅보다 높은 것 이므로 땅을 깎아서 기준이 되는 높이와 맞추기 위해 down 변수에 높이를 더한다.
  6. 반대로 0 보다 작으면 기준이 되는 땅 보다 낮은 것이므로 땅을 높여서 기준이 되는 높이와 맞추기 위해 up 변수에 높이를 더해야 하는데 high가 0보다 작으면 - 이므로 up에 높이를 - 해서 더한다.
  7. 그렇게 2차원 배열을 전부 반복했으면 땅을 깎으면서 구한 블록과 원래 인벤토리에 있던 블록의 갯수가 쌓아야되는 블록의 갯수보다 크거나 같아야 높이를 맞출 수 있으므로 크거나 같은지 비교해서
  8. 땅을 깎는건 2초가 걸리므로 down * 2 한 값에 쌓아야 되는 높이 만큼 더한다.
  9. 그렇게 구한 걸리는 시간이 이전에 구한 최소 시간 보다 작으면 최소 시간을 지금 구한 time으로 변경하고
  10. 걸리는 시간이 같은 경우엔 가장 높은 높이로 구해야 하므로
  11. 높이도 현재 높이로 바꿔준다.
    • 높이는 제일 작은 높이부터 제일 큰 높이로 순차적으로 올라가고 있으므로 나중에 구한 높이가 이전에 구한 높이 보다 무조건 높다.
  12. 끝.

결과

결과

P.S BFS로 시도했던 코드

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
package algorithm.baekjoon.class2.bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 마인크래프트 {
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int[] nmb = convertStringArrayToIntegerArray(br.readLine().split(" "));

            int n = nmb[0];
            int m = nmb[1];

            int[][] ground = initGround(br, n, m);
            boolean[][] isPassed = new boolean[n][m];

            List<Block> blockList = getBlockList(n, m, ground, isPassed);

            int[] timeAndHigh = getMinimumConstructionTime(blockList, nmb[2]);

            System.out.println(timeAndHigh[0] + " " + timeAndHigh[1]);
        }
    }

    private static int[] convertStringArrayToIntegerArray(String[] args) {
        int[] array = new int[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    private static int[][] initGround(BufferedReader br, int n, int m) throws IOException {
        int[][] ground = new int[n][m];
        for (int i = 0; i < n; i++) {
            ground[i]= convertStringArrayToIntegerArray(br.readLine().split(" "));
        }

        return ground;
    }

    private static List<Block> getBlockList(int n, int m, int[][] ground, boolean[][] isPassed) {
        List<Block> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isPassed[i][j]) {
                    continue;
                }

                int count = breadthFirstSearch(i, j, ground, isPassed);

                list.add(new Block(ground[i][j], count));
            }
        }

        return list;
    }

    private static int breadthFirstSearch(int x, int y, int[][] picture, boolean[][] isPassed) {
        final int[] xAround = new int[]{1, -1, 0, 0};
        final int[] yAround = new int[]{0, 0, 1, -1};

        int areaRange = 1;

        Queue<Position> queue = new LinkedList<>();

        setPassedArea(isPassed, queue, x, y);

        while (!queue.isEmpty()) {
            Position currentPosition = queue.poll();

            for (int i = 0; i < xAround.length; i++) {
                int moveX = xAround[i] + currentPosition.x;
                int moveY = yAround[i] + currentPosition.y;

                if (!isSameAreaValidation(moveX, moveY, picture, isPassed, currentPosition)) {
                    continue;
                }

                setPassedArea(isPassed, queue, moveX, moveY);
                ++areaRange;
            }
        }

        return areaRange;
    }

    private static void setPassedArea(boolean[][] isPassed, Queue<Position> queue, int x, int y) {
        isPassed[x][y] = true;
        queue.offer(new Position(x, y));
    }

    private static boolean isSameAreaValidation(int moveX, int moveY, int[][] picture, boolean[][] isPassed, Position currentPosition) {
        if (isOutOfPicture(moveX, moveY, picture)) {
            return false;
        }

        if (isPassed[moveX][moveY]) {
            return false;
        }

        if (picture[currentPosition.x][currentPosition.y] != picture[moveX][moveY]) {
            return false;
        }

        return true;
    }

    private static boolean isOutOfPicture(int moveX, int moveY, int[][] picture) {
        if (moveX < 0 || moveY < 0) {
            return true;
        }

        if (picture.length <= moveX || picture[0].length <= moveY) {
            return true;
        }

        return false;
    }

    private static int[] getMinimumConstructionTime(List<Block> blockList, int inventory) {
        int answerTime = Integer.MAX_VALUE;
        int answerHigh = 0;

        for (Block currentBlock : blockList) {
            int currentHigh = currentBlock.high;

            int up = 0;
            int down = 0;

            for (Block loopBlock : blockList) {
                int loopHigh = loopBlock.high;
                int loopCount = loopBlock.count;

                if (currentHigh > loopHigh) {
                    up += (currentHigh - loopHigh) * loopCount;
                } else if (currentHigh < loopHigh) {
                    down += (loopHigh - currentHigh) * loopCount;
                }
            }

            if (down + inventory >= up) {
                int time = (down * 2) + up;

                if (answerTime > time) {
                    answerTime = time;
                    answerHigh = currentBlock.high;
                }
            }
        }

        return new int[]{answerTime, answerHigh};
    }

    static class Block {
        private Integer high;
        private Integer count;

        public Block(Integer high, Integer count) {
            this.high = high;
            this.count = count;
        }
    }

    static class Position {
        private int x;
        private int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
  • BFS로 높이 별 갯수를 구한 후 높이 별로 sorting 하여 처리 하려고 했는데 시간 초과로 실패

댓글 공유

백준 2805번: 나무 자르기

문제

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

코드

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
public class 나무_자르기 {
    public static void main(String[] args) throws IOException {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            long[] nm = convertStringArrayToLongArray(br.readLine().split(" "));

            long m = nm[1];

            long[] trees = convertStringArrayToLongArray(br.readLine().split(" "));

            long answer = solution(trees, m);

            System.out.println(answer);
        }
    }

    private static long[] convertStringArrayToLongArray(String[] args) {
        long[] array = new long[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    public static long solution(long[] trees, long m) {
        Arrays.sort(trees);

        long low = 0;
        long high = trees[trees.length - 1];

        long answer = 0;

        while (low <= high) {
            long mid = (low + high) >>> 1;
            long sum = getTrees(trees, mid);

            if (sum < m) {
                high = mid - 1;
            } else {
                answer = Math.max(answer, mid);
                low = mid + 1;
            }
        }

        return answer;
    }

    private static long getTrees(long[] trees, long mid) {
        long sum = 0;
        for (int i = 0; i < trees.length; i++) {
            sum += trees[i] > mid ? trees[i] - mid : 0;
        }

        return sum;
    }
}

흐름

  1. 나무들을 크기가 큰 순서로 정렬한다.
  2. 0부터 높이가 제일 큰 나무까지 탐색하기 위해 low와 high 변수를 지정한다.
  3. low와 high의 중간 값을 구한다.
  4. 나무들을 반복하면서 중간 값 보다 크면 나무 길이와 중간 값을 뺀 값을 더한다.
  5. 그렇게 벌목한 나무를 전부 더한 값이 필요한 나무 길이인 m 보다 작으면,
  6. 벌복한 나무의 길이가 m보다 크거나 같으면, 벌목한 나무가 남는 것 이므로, 나무를 낭비하지 않기 위해 이전에 구한 중간 값(answer) 와 현재 중간 값 중 큰 값을 저장하고 중간 값 + 1 해서 최소 값을 올린다.
  7. 반대로 벌목한 나무의 길이가 m 보다 작은 경우 더 크게 자르기 위해 중간 값 - 1을 high에 저장해서 다음 루프 때 (low + high) >>> 1 에서 더 크게 잘릴 수 있도록 한다.
  8. low와 high가 같아질 때 까지 반복한다.
  9. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
assertEquals(15, test.solution(new long[] {20, 15, 10, 17}, 7));
assertEquals(3, test.solution(new long[] {6, 6}, 5));
assertEquals(4, test.solution(new long[] {6, 6, 6, 6}, 6));
assertEquals(500000000, test.solution(new long[] {900000000, 900000000, 900000000, 900000000, 900000000}, 2000000000));
assertEquals(19, test.solution(new long[] {20, 15, 10, 17}, 1));
assertEquals(0, test.solution(new long[] {2, 2}, 3));
assertEquals(21, test.solution(new long[] {13, 23, 21, 32}, 12));
assertEquals(2, test.solution(new long[] {1,4,5,7}, 10));
assertEquals(1, test.solution(new long[] {51, 1}, 50));
assertEquals(999999999, test.solution(new long[] {1000000000}, 1));
assertEquals(0, test.solution(new long[] {2, 2,2,2}, 8));

댓글 공유

Junggu Ji

author.bio


author.job