프로세스와 스레드

결론

  • 프로세스(Process)란 메모리 위에 올라와서 실행 중인 프로그램으로 각각의 프로세스는 모두 독립적인 상태이고 Os로부터 자원을 할당 받은 작업의 단위.
  • 스레드(Thread)란 프로세스 내에서 실행되는 작업의 수행 단위로 각각의 스레드는 프로세스가 할당받은 자원을 이용하면서 스레드간 메모리를 공유하며 작동한다.

작동 방식

프로세스

OS에서 자원을 할당받은 프로세스들 (이미지 출처: https://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html)
  • 프로세스는 OS로부터 Code, Data, Stack, Heap으로 이루어진 독립된 메모리 영역을 할당 받는다.
  • 각각 독립된 영역을 할당 받으므로 기본적으로 프로세스들 간에는 다른 프로세스의 변수나, 자료구조에 접근 할 수 없으며 서로 간 통신을 위해선 커널 영역에 IPC를 이용해 프로세스간 통신을 할 수 있다.

프로세스 내 메모리 구조

  1. Code 영역 : 프로그램에서 수행 할 코드가 로딩 되는 메모리
  2. Data 영역 : 프로그램이 실행 될 때 생성되고, 종료 될 때 시스템에 반환되며 BBS와 Data영역으로 나뉘는데 BBS엔 초기화 되지 않은 변수를 위한 영역이고, Data는 초기화된 데이터를 저장하는 메모리이다.
  3. Heap 영역 : 프로그램이 실행되는 동안 필요에 의해 동적으로 사요되는 메모리 영역으로 대표적으로 C언어의 malloc함수를 이용해 메모리를 할당한다면 이 영역에 할당되고 Java의 Object 타입들은 heap 영역에 생성된다.
  4. Stack 영역 : 프로그램이 자동으로 사용하는 임시 메모리 영역으로 지연벽수, 파라미터, 리턴 값 등 잠시 사용됐다가 사라지는 데이터를 저장하는 영역으로 함수 호출 시 생성되고 함수가 끝나면 반환된다. 예로 메서드 내에서 선언한 지역 변수는 Stack 영역에 저장되기 때문에 메서드가 끝날 때 함께 사라지므로 다른 메서드에서 호출 할 수 없다.

스레드

프로세스에서 자원을 할당받은 스레드들 (이미지 출처: https://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html)
  • 스레드는 프로세스 내부에 존재하고 Stack 영역만 각 스레드마다 독립적으로 할당 받고 그 외에 프로세스 영역에 있는 code, data, heap 영역은 프로세스 내에 있는 스레드 끼리 공유한다.
  • 때문에 한 스레드에서 공유된 영역의 자원을 수정한다면 다른 스레드에서 그 자원을 사용 할 때 변경된 자원을 사용하게 되고
  • 결국 개발자가 자원을 동기적으로 사용 할 수 있도록 처리 할 수 있어야 한다.
  • 프로세스 내 자원을 함께 공유하기 때문에 모든 자원을 각각 독립되게 할당 받은 프로세스와 달리 같은 프로세스 내의 스레드가 문제가 생긴다면 다른 스레드들도 강제로 종료되게 된다.

참고 사이트

댓글 공유

Synchronous, Asynchronous와 Blocking, Non-Blocking

결론

  • Synchronous, Asynchronous 는 두 개 이상의 대상에 대한 시간을 관리하는 방법이고,
  • Blocking, Non-Blocking 은 직접 제어 할 수 없는 대상을 처리하는 방법에 대한 것이다.

Synchronous, Asynchronous

  • 두 개 이상의 대상들의 시간을 처리하는 방식
  • Synchronous는 두 개 이상의 대상들의 시간을 일치 시키는 것 으로 메서드가 종료되는 시간과 결과를 전달받은 시간이 일치하면 Synchronous(동기) 방식이다.
  • Asynchronous는 두 개 이상의 대상들의 시간을 일치 시키지 않는 것 으로 메서드가 종료되는 시간과 결과를 전달받은 시간이 일치하지 않으면 Asynchronous(비동기) 방식이다.

Blocking, Non-Blocking

  • 직접 제어 할 수 없는 대상에 대한 처리 방식
  • Blocking은 직접 제어 할 수 없는 대상이 작업이 끝날 때 까지 제어권을 넘기지 않아 작업이 끝날 때 까지 대기 하는 방식이다.
  • Non-Blocking은 직접 제어 할 수 없는 대상의 작업의 종료와 관계없이 제어권을 바로 다시 얻어와 다른 일을 할 수 있게 하는 방식이다.

본론

Synchronous

우선 Synchronous의 뜻을 사전에선 아래와 같이 정의하고 있다.

동시 발생하는

네이버 어학사전

이 처럼 두 개 이상의 작업을 동시에 발생시키거나, 동시에 종료시키는 행동을 말한다.

동기 방식을 사용 할 경우 메서드를 호출 했을 때, 결과를 호출한 쪽에서 스스로 확인하고 처리하기 때문에, 결과를 처리 할 때까지 기다렸다가 결과를 전달받고 메서드를 종료 시킨다.

간단히 요약하면 메서드를 호출하면 그 메서드가 종료되는 시간과 결과가 return 되는 시간이 같다는 것으로, 메서드가 종료되는 시간과 결과가 return 되는 시간이 같으므로 동기 방식이라 말한다.

혹은, 2개 이상의 일을 각각 실행시켜 A가 끝나는 시간과 B가 시작하는 시간이 같은 경우도 마찬가지로 동기 방식이라고 할 수 있다.

Java로 예를 들면 쓰레드를 동기 시키기 위해 사용하는 synchronized가 있고 일반적으로는 일부러 설정하지 않는 한 보통의 메서드 호출은 모두 동기 방식으로 사용된다.

Asynchronous

Asynchronous, 비동기 방식은 부정형 접두사 A를 붙여서 두 개 이상의 대상의 시간을 일치 시키지 않는 방식으로 동기 방식과 반대로 동작한다.

즉, 메서드를 호출 했을 때 결과가 return되지 않더라도 다른 작업을 수행하거나 메서드를 종료하고 나중에 처리되면 그 때 결과물을 가져온다.

이 때 메서드를 호출한 시간과 return된 결과를 받은 시간이 일치하지 않으므로 이러한 방식을 비동기 방식이라 한다.

보통 ajax를 통해 많이 사용 해봤을 것이고, Java에선 쓰레드를 활용해 비동기적으로 처리 할 수 있고, Spring에선 @Async Annotation을 이용해 비동기 방식을 처리 할 수 있다.

Blocking

결론에서 말한 것 처럼 Blocking은 직접 제어 할 수 없는 대상이 작업이 끝날 때 까지 제어권을 넘기지 않아 작업이 끝날 때 까지 대기하게 하는 방식이다.

예를 들면 스타크래프트에서 테란의 SCV는 한번 건물을 짓기 시작하면 건설이 끝날 때 까지 다른 동작을 할 수 없으므로, Blocking 상태라고 할 수 있고, Java에선 System.in 같은 I/O 처리를 예로 들 수 있다.

Non-Blocking

Blocking과 반대되는 방식으로 작업의 처리 여부와 상관없이 작업을 호출한 쪽이 다시 제어권을 가져와서 자유롭게 다른 일을 처리할 수 있는 방식을 Non-Blocking 방식이라고 한다.

마찬가지의 예로 프로토스의 프로브는 건물을 짓게 하면 차원 균열만 개방하고 바로 미네라를 캐는 등의 다른 일을 수행 할 수 있으므로 프로브는 Non-Blocking 상태라고 할 수 있다.


서플라이디포를 건설 하는 동안 다른 행위를 할 수 없는 SCV
첫 번째 파일럿을 소환 후 파일럿이 완성되기 전에 두 번째 파일럿을 소환 할 수 있는 프로브

참고 사이트

댓글 공유

백준 2751번: 수 정렬하기 2

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

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

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < amount; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(list);

        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i).append("\n");
        }

        System.out.println(sb);
    }
}

Arrays.sort(int[]) vs Arrays.sort(Object[]) and Collections.sort(List)

Arrays.sort(int[])

  • DualPivotQuicksort라는 피벗을 두 개를 정해 구간을 3개로 하는 퀵소트를 사용한다.
  • API에 따르면 이 때 평균 O(n log(n)) 성능을 제공하며 일반적으로 기존 (one-pivot) 쿽소트 보다 빠르다고 한다.
  • 하지만 여전히 최악의 경우 O(n^2)인 것은 여전하다.

Arrays.sort(Object[]) and Collections.sort(List)

  • java.util.Arrays.useLegacyMergeSort 설정에 따라 true면 legacyMergeSort를 통해 Merge sort로 정렬하고 false면 TimeSort를 통해 Tim sort로 정렬한다.
  • 이 때 기본적으로 java.util.Arrays.useLegacyMergeSort 설정은 false로 지정되어 있다.
  • Tim sort는 Insertion sort와 Merge sort를 결합하여 만든 정렬로 최선의 경우 O(n), 평균적으로 O(n log(n)), 최악의 경우 O(n log(n))의 성능을 제공한다.
  • Tim sort에 대한 자세한 설명

java.util.Arrays.useLegacyMergeSort 확인

1
2
3
4
5
6
7
8
9
10
...

    static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

...
  • new sun.security.action.GetBooleanAction(“java.util.Arrays.useLegacyMergeSort”)).booleanValue(); 를 sysout으로 출력해보면 false가 return 되는 것을 확인할 수 있다.

결과

댓글 공유

프로그래머스: 방금 그 곡

문제

https://programmers.co.kr/learn/courses/30/lessons/17683

코드

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 String solution(String m, String[] musicinfos) {
    String answer = "(None)";

    m = getSharpReplace(m);

    int maxPlayTime = 0;

    for (String music : musicinfos) {
        String[] info = music.split(",");

        int playTimeToMinute = getPlayTime(info[0], info[1]);
        String melody = getMelody(playTimeToMinute, info[3]);

        if (melody.contains(m)) {
            if (maxPlayTime < playTimeToMinute) {
                answer = info[2];
                maxPlayTime = playTimeToMinute;
            }
        }
    }

    return answer;
}

private String getSharpReplace(String arg) {
    return arg.replace("C#", "1")
            .replace("D#", "2")
            .replace("E#", "3")
            .replace("F#", "4")
            .replace("G#", "5")
            .replace("A#", "6");
}

private int getPlayTime(String start, String end) {
    LocalTime startTime = convertLocalTime(start);
    LocalTime endTime = convertLocalTime(end);

    LocalTime playTime = endTime.minusHours(startTime.getHour()).minusMinutes(startTime.getMinute());

    return playTime.getHour() * 60 + playTime.getMinute();
}

private LocalTime convertLocalTime(String time) {
    String[] hourAndMinute = time.split(":");

    return LocalTime.of(Integer.parseInt(hourAndMinute[0]), Integer.parseInt(hourAndMinute[1]), 0);
}

private String getMelody(int playtime, String melody) {
    String sharpReplaceMelody = getSharpReplace(melody);
    StringBuilder sb = new StringBuilder();

    char[] array = sharpReplaceMelody.toCharArray();
    for (int i = 0; i < playtime; i++) {
        sb.append(array[i % sharpReplaceMelody.length()]);
    }

    return sb.toString();
}

흐름

  1. “#”이 붙은 음계들을 유일한 값으로 치환한다.
  2. 곡 정보를 담은 musicinfos의 개수만큼 반복한다.
  3. 돌면서 “,”로 잘라 시작시간, 끝난시간, 곡 이름, 멜로디 순으로 구분하여 String array에 저장한다.
  4. 시작 시간과 끝난 시간을 LocalTime type으로 만들어서 끝난 시간에서 시작 시간을 빼서 얼마나 오래 방송 됐는지 playTime을 구한다.
  5. 곡 정보에 있는 멜로디에서도 “#”이 붙은 음계들을 1번에서 한 것과 같은 값으로 치환한다.
  6. playtime에 따라 멜로디에 음계를 추가하기 위해 멜로디를 char array로 변경한다.
  7. playtime 만큼 반복하면서 멜로디를 만든다.
    1. playtime보다 멜로디가 짧은 경우엔 지금 멜로디에 음계를 이어 붙여 playtime 길이 만큼 만든다.
    2. 멜로디가 더 긴 경우엔 playtime 만큼 자른다.
  8. 이렇게 구한 멜로디에 기억 중인 멜로디 m이 포함된다면 playtime이 가장 긴지 확인하고 곡 정보를 저장한다.
  9. 끝.

결과

번호 속도
테스트 1 통과 (1.31ms, 54.1MB)
테스트 2 통과 (1.38ms, 52.7MB)
테스트 3 통과 (3.19ms, 52.6MB)
테스트 4 통과 (1.33ms, 51.7MB)
테스트 5 통과 (1.44ms, 52.7MB)
테스트 6 통과 (1.42ms, 52.2MB)
테스트 7 통과 (2.26ms, 52.7MB)
테스트 8 통과 (2.27ms, 53.3MB)
테스트 9 통과 (2.38ms, 52.5MB)
테스트 10 통과 (2.31ms, 52MB)
테스트 11 통과 (2.24ms, 53.4MB)
테스트 12 통과 (2.03ms, 53.2MB)
테스트 13 통과 (2.27ms, 53.2MB)
테스트 14 통과 (2.23ms, 52.2MB)
테스트 15 통과 (2.19ms, 53.2MB)
테스트 16 통과 (2.22ms, 52.1MB)
테스트 17 통과 (1.78ms, 52.4MB)
테스트 18 통과 (2.22ms, 53MB)
테스트 19 통과 (2.66ms, 52.5MB)
테스트 20 통과 (2.42ms, 52.1MB)
테스트 21 통과 (2.41ms, 52.3MB)
테스트 22 통과 (3.55ms, 52.9MB)
테스트 23 통과 (3.94ms, 53.2MB)
테스트 24 통과 (2.15ms, 51.9MB)
테스트 25 통과 (1.24ms, 52.3MB)
테스트 26 통과 (1.30ms, 53.2MB)
테스트 27 통과 (1.41ms, 52.6MB)
테스트 28 통과 (1.12ms, 53.1MB)
테스트 29 통과 (12.67ms, 53.4MB)
테스트 30 통과 (13.24ms, 53.1MB)

테스트 케이스

1
2
3
4
5
assertEquals("HELLO", test.solution("ABCDEFG", new String[] {"12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"}));
assertEquals("FOO", test.solution("CC#BCC#BCC#BCC#B", new String[] {"03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"}));
assertEquals("WORLD", test.solution("ABC", new String[] {"12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"}));
assertEquals("(None)", test.solution("CDEFGAC", new String[] {"12:00,12:06,HELLO,CDEFGA"}));
assertEquals("FOO", test.solution("CCB", new String[] {"03:00,03:10,FOO,CCB#CCB", "04:00,04:08,BAR,ABC"}));

댓글 공유

프로그래머스: 파일명 정렬

문제

https://programmers.co.kr/learn/courses/30/lessons/17686

코드

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
public String[] solution(String[] files) {

    List<File> fileList = new ArrayList<>();
    for (int i = 0; i < files.length; i++) {
        char[] array = files[i].toCharArray();

        String originName = files[i];
        String head = "";
        Integer number = 0;

        boolean isString = true;
        int numberStartIndex = 0;
        for (int j = 0; j < array.length; j++) {
            if (isString && isNumber(array[j])) {
                head = new String(array, 0, j).toUpperCase();
                numberStartIndex = j;
                isString = false;
                continue;
            }

            if (!isString && !isNumber(array[j])) {
                number = Integer.parseInt(new String(array, numberStartIndex, j - numberStartIndex));
                isString = true;
                break;
            }
        }

        if (!isString) {
            number = Integer.parseInt(new String(array, numberStartIndex, array.length - numberStartIndex));
        }

        fileList.add(new File(originName, head, number, i));
    }

    sort(fileList);

    return fileList.stream()
            .map(File::getOriginName)
            .toArray(String[]::new);
}

private void sort(List<File> fileList) {
    fileList.sort((f1, f2) -> {
        if (f1.head.compareTo(f2.head) != 0) {
            return f1.head.compareTo(f2.head);
        } else if (f1.number.compareTo(f2.number) != 0) {
            return f1.number.compareTo(f2.number);
        } else {
            return f1.index.compareTo(f2.index);
        }
    });
}

private boolean isNumber(char ch) {
    return (48 <= ch && ch <= 57);
}

static class File {
    private final String originName;
    private final String head;
    private final Integer number;
    private final Integer index;

    public File(String originName, String head, Integer number, Integer index) {
        this.originName = originName;
        this.head = head;
        this.number = number;
        this.index = index;
    }

    public String getOriginName() {
        return this.originName;
    }

    public String getHead() {
        return this.head;
    }

    public Integer getNumber() {
        return this.number;
    }

    public Integer getIndex() {
        return this.index;
    }
}

흐름

  1. file 개수만큼 반복하면서 파일명을 char array로 만든다.
  2. char array를 숫자가 나올 때 까지 반복한다.
  3. 숫자가 나오면 0부터 숫자가 나온 index까지 짤라서 head 변수에 저장시키고 숫자가 시작된 index와 다음에 숫자인지 체크 할 flag 변수를 false로 변경한다.
  4. head를 만들고 난 후엔 숫자만 뽑아서 number로 저장해야 하므로
  5. 돌면서 현재 문자가 아니고 지금 값도 숫자가 아니면 지금 index까지 잘라서 number에 저장한다.
  6. 만약 tail이 없어서 이번 조건문에 걸리지 않았다면, 숫자가 시직된 index부터 array 길이에서 숫자가 시작된 index를 뺀 크기 만큼 잘라서 number에 저장한다.
  7. 구한 head, number를 가지고 원래 파일명, head, number, 원래 순서를 갖는 File Object를 생성하고 List에 추가한다.
  8. 리스트를 문제의 제약조건 처럼 정렬한다.
    1. head로 비교해서 정렬
    2. head가 같으면 number로 비교해서 정렬
    3. 둘 다 같으면 원래 순서대로 정렬
  9. 정렬한 List를 String[]로 만들어서 return 한다.
  10. 끝

결과

번호 속도
테스트 1 통과 (2.80ms, 52.3MB)
테스트 2 통과 (2.92ms, 52.8MB)
테스트 3 통과 (15.41ms, 54.1MB)
테스트 4 통과 (17.89ms, 54.3MB)
테스트 5 통과 (16.74ms, 54.3MB)
테스트 6 통과 (15.07ms, 53.3MB)
테스트 7 통과 (21.21ms, 54.5MB)
테스트 8 통과 (21.20ms, 53.8MB)
테스트 9 통과 (17.57ms, 53.6MB)
테스트 10 통과 (20.00ms, 53.5MB)
테스트 11 통과 (15.30ms, 53.8MB)
테스트 12 통과 (14.44ms, 54.1MB)
테스트 13 통과 (10.24ms, 53.8MB)
테스트 14 통과 (12.50ms, 54.1MB)
테스트 15 통과 (18.61ms, 54.1MB)
테스트 16 통과 (20.40ms, 53.9MB)
테스트 17 통과 (10.36ms, 53.8MB)
테스트 18 통과 (13.84ms, 54.6MB)
테스트 19 통과 (16.07ms, 54.4MB)
테스트 20 통과 (14.91ms, 53.8MB)

정렬을 stream에 추가 할 경우

stream sorted

1
2
3
4
5
6
return fileList.stream()
        .sorted(Comparator.comparing(File::getHead)
        .thenComparing(Comparator.comparing(File::getNumber)
        .thenComparing(File::getIndex)))
        .map(File::getOriginName)
        .toArray(String[]::new);

결과

번호 속도
테스트 1 통과 (10.64ms, 53.2MB)
테스트 2 통과 (18.65ms, 53.2MB)
테스트 3 통과 (25.96ms, 54.7MB)
테스트 4 통과 (24.73ms, 54.8MB)
테스트 5 통과 (20.97ms, 54.3MB)
테스트 6 통과 (29.57ms, 54.3MB)
테스트 7 통과 (30.45ms, 54.3MB)
테스트 8 통과 (24.91ms, 54.3MB)
테스트 9 통과 (26.40ms, 54.8MB)
테스트 10 통과 (28.88ms, 54.1MB)
테스트 11 통과 (22.73ms, 54.7MB)
테스트 12 통과 (25.60ms, 54.4MB)
테스트 13 통과 (22.06ms, 54.2MB)
테스트 14 통과 (19.49ms, 54.9MB)
테스트 15 통과 (17.53ms, 54.2MB)
테스트 16 통과 (20.05ms, 54.1MB)
테스트 17 통과 (18.01ms, 54.7MB)
테스트 18 통과 (18.53ms, 53.7MB)
테스트 19 통과 (26.25ms, 54.2MB)
테스트 20 통과 (20.81ms, 55.2MB)

테스트 케이스

1
2
3
4
5
assertArrayEquals(new String[] {"img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"}, test.solution(new String[] {"img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"}));
assertArrayEquals(new String[] {"A-10 Thunderbolt II", "B-50 Superfortress", "F-5 Freedom Fighter", "F-14 Tomcat"}, test.solution(new String[] {"F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"}));
assertArrayEquals(new String[] {"img100.p2ng", "img202.png123"}, test.solution(new String[] {"img202.png123", "img100.p2ng"}));
assertArrayEquals(new String[] {"foo010bar020.zip", "foo010bar030.zip"}, test.solution(new String[] {"foo010bar020.zip", "foo010bar030.zip"}));
assertArrayEquals(new String[] {"F-15", "F-17", "F-22"}, test.solution(new String[] {"F-22", "F-17", "F-15"}));

댓글 공유

프로그래머스: 프렌즈4블록

문제

https://programmers.co.kr/learn/courses/30/lessons/17679

코드

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
private static final int ASCII = 32;
private static final char EMPTY = ' ';

public int solution(int m, int n, String[] board) {
    int answer = 0;
    char[][] charBoard = convertStringArrayToCharArray(m, n, board);

    while (true) {
        boolean isEnd = box(charBoard);

        if (isEnd) {
            break;
        }

        answer += delete(charBoard);
    }

    return answer;
}

public char[][] convertStringArrayToCharArray(int m, int n, String[] board) {
    char[][] charBoard = new char[m][n];

    int i = 0;
    for (String str : board) {
        char[] toChar = str.toCharArray();
        charBoard[i] = toChar;
        ++i;
    }

    return charBoard;
}

public char toLowerCase(char value) {
    return (char) ((value >= 65 && value <= 90) ? (value + ASCII) : value);
}

public boolean box(char[][] charBoard) {
    boolean isEnd = true;

    for (int i = 0; i < charBoard.length; i++) {
        for (int j = 0; j < charBoard[i].length; j++) {
            if (validation(i, j, charBoard)) {
                char value = toLowerCase(charBoard[i][j]);
                charBoard[i][j] = value;
                charBoard[i][j+1] = value;
                charBoard[i+1][j] = value;
                charBoard[i+1][j+1] = value;

                isEnd = false;
            }
        }
    }

    return isEnd;
}

private boolean validation(int i, int j, char[][] charBoard) {
    if ((i + 1) == charBoard.length || (j + 1) == charBoard[0].length) {
        return false;
    }
    char position = toLowerCase(charBoard[i][j]);

    if (position == EMPTY) {
        return false;
    }

    char moveX = toLowerCase(charBoard[i][j+1]);
    char moveY = toLowerCase(charBoard[i+1][j]);
    char moveXY = toLowerCase(charBoard[i+1][j+1]);

    if (position != moveX) {
        return false;
    }

    if (position != moveY) {
        return false;
    }

    if (position != moveXY) {
        return false;
    }

    return true;
}

private int delete(char[][] charBoard) {
    int answer = 0;

    for (int i = 0; i < charBoard.length; i++) {
        for (int j = 0; j < charBoard[i].length; j++) {
            if (charBoard[i][j] == EMPTY) {
                continue;
            }

            if (charBoard[i][j] >= 97 && charBoard[i][j] <= 122) {
                if (i != 0) {
                    for (int k = i; k > 0; k--) {
                        charBoard[k][j] = charBoard[k-1][j];
                        charBoard[k-1][j] = EMPTY;
                    }
                } else {
                    charBoard[i][j] = EMPTY;
                }

                ++answer;
            }
        }
    }

    return answer;
}

흐름

  1. String array로 넘어온 board를 2차원 array로 만든다.
  2. 무한루프를 돌면서 char로 만든 board array의 element들을 모두 꺼내면서
  3. 제약조건을 확인하여 모두 통과할 때만 true를 return 한다.
    1. 현재 element가 있는 위치가 맨 끝인지
    2. 현재 element가 빈 값인지
    3. 현재 element의 오른쪽 element와 값이 같지 않은지
    4. 현재 element의 아래쪽 element와 값이 같지 않은지
    5. 현재 element의 우하(右下)쪽 element와 값이 같지 않은지
  4. 제약조건을 통과하면 현재 위치에서 오른쪽, 아래쪽, 우하(右下)쪽 element들을 소문자로 만들고 삭제 할 블록이 남았으므로, false를 return 한다.
  5. 다시 board array를 반복하면서 element가 소문자인 경우
  6. 현재 높이가 0이라면 위에서 내려올 블록이 없으므로 바로 빈 값을 저장하고
  7. 0이 아니라면 현재 위치부터 값을 1씩 빼면서 위에 블록을 현재 위치에 저장 시키고 위 블록은 빈 값으로 저장한다.
  8. 블록을 제거 할 때 마다 제거시킨 블록 개수를 저장하는 변수를 증가시킨다.
  9. 삭제 할 블록이 없을 때 까지 2번부터 8번까지 반복하고 삭제 할 블록이 없으면 루프를 빠져 나오고 삭제한 블록의 개수를 return 한다.
  10. 끝

결과

번호 속도
테스트 1 통과 (0.07ms, 52.3MB)
테스트 2 통과 (0.09ms, 51.7MB)
테스트 3 통과 (0.04ms, 51.9MB)
테스트 4 통과 (1.08ms, 52.5MB)
테스트 5 통과 (14.40ms, 52.6MB)
테스트 6 통과 (3.08ms, 52.3MB)
테스트 7 통과 (0.81ms, 52.3MB)
테스트 8 통과 (1.81ms, 53.7MB)
테스트 9 통과 (0.07ms, 53.4MB)
테스트 10 통과 (0.59ms, 51.7MB)
테스트 11 통과 (1.38ms, 52.7MB)

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
assertEquals(14, test.solution(4,5, new String[] {"CCBDE", "AAADE", "AAABF", "CCBBF"}));
assertEquals(15, test.solution(6,6, new String[] {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"}));
assertEquals(14, test.solution(4,5, new String[] {"AAAAA","AUUUA","AUUAA","AAAAA"}));
assertEquals(4, test.solution(2,2, new String[] {"AA","AA"}));
assertEquals(0, test.solution(2,2, new String[] {"AA","AB"}));
assertEquals(4, test.solution(3,2, new String[] {"AA","AA", "AB"}));
assertEquals(8, test.solution(4,2, new String[] {"CC","AA", "AA", "CC"}));
assertEquals(12, test.solution(6,2, new String[] {"DD", "CC", "AA", "AA", "CC", "DD"}));
assertEquals(8, test.solution(8,2, new String[] {"FF", "AA", "CC", "AA", "AA", "CC", "DD", "FF"}));
assertEquals(8, test.solution(6,2, new String[] {"AA", "AA", "CC", "AA", "AA", "DD"}));
assertEquals(8, test.solution(4,4, new String[] {"ABCD", "BACE", "BCDD", "BCDD"}));
assertEquals(27, test.solution(8,9, new String[] {"ABCDADFDA", "ABDFQWERF", "WKDNFNRIT", "AKAKWODCJ", "AKAKWODCJ", "KKKKKKKKK", "KKKKKKKKK", "KKKKKKKKK"}));
assertEquals(15, test.solution(4,5, new String[] {"AAAAA", "AAAAU", "AAAUU", "UUUUU"}));
assertEquals(24, test.solution(5,6, new String[] {"AAAAAA", "BBAATB", "BBAATB", "JJJTAA", "JJJTAA"}));
assertEquals(32, test.solution(6,6, new String[] {"AABBEE", "AAAEEE", "VAAEEV", "AABBEE", "AACCEE", "VVCCEE"}));

댓글 공유

Vue 개발 순서 정리

서론

Spring boot + Vue를 활용해 토이 프로젝트 진행하고 있는데 헷갈리는 부분을 차후 또 Vue로 개발 할 일이 있을 경우 참고하기 위해 글로 남겨 놓는다.

개발 순서

  • Vue는 설치되어 있다고 가정한다.
  1. root 디렉토리에 vue.config.js 생성하고 필요한 설정 추가

vue.config.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const path = require("path");

module.exports = {
  assetsDir: "static",
  outputDir: path.resolve(__dirname, "../backend/src/main/resources/static"),
  devServer: {
    proxy: {
      "/": {
        target: "http://localhost:9312",
        ws: true,
        changeOrigin: true
      }
    }
  },
  chainWebpack: config => {
    const svgRule = config.module.rule("svg");
    svgRule.uses.clear();
    svgRule.use("vue-svg-loader").loader("vue-svg-loader");
  }
};
  1. views/ 에 화면이 될 vue 파일 생성
  2. src/ 에 api 폴더 생성
  3. api/ 에 화면 별로 필요한 js 파일 생성
    1. 이 js 파일들엔 각 컴포넌트 별로 필요한 api 주소를 호출 할 수 있는 js 코드를 작성한다.
  4. api 호출 시 공통으로 들어갈 header를 포함하는 common.js 생성

common.js

1
2
3
4
5
6
7
8
9
import axios from "axios";

const AXIOS = axios.create({
  headers: {
    "Access-Control-Allow-Origin": "*",
    "Content-Type": "application/json; charset = utf-8"
  },
  timeout: 1000
});
  1. components/ 에 2번에서 만든 화면에 출력 될 component vue 파일 생성
  2. router/index.js 에 추가한 vue path 추가
    • rotuer에 추가하지 않으면 화면이 나오지 않음

router/index.js

1
2
3
4
5
6
7
...
  {
    path: "/main",
    name: "Main",
    component: () => import("../views/Main")
  }
...

댓글 공유

JQPL은 return class로 Inner class는 불가능

결론

JPQL의 return 값으로 Inner class를 지정하면 class를 찾을 수 없다는 에러가 발생 하므로 Inner class 말고 따로 class를 생성하고 그 class를 return class로 지정해줘야 한다.

발견

아래 처럼 DTO를 생성하고 view별로 inner class로 DTO를 만들고 jpql의 return class로 지정해주었는데 클래스를 찾을 수 없다는 에러가 발생하였다.

DTO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ChannelDTO {

    @NoArgsConstructor
    @Getter
    public static class SubChannelList {
        private Integer subChannel;
        private KillTime killTime;

        @Builder
        public SubChannelList(Integer subChannel, KillTime killTime) {
            this.subChannel = subChannel;
            this.killTime = killTime;
        }
    }

    ...
}

JPQL 호출 메서드

1
2
3
4
5
6
7
8
9
10
11
public List<SubChannelList> findSubChannelList(Integer dungeonId, Integer mainChannel) {
    return em.createQuery(
            "select new com.jungguji.windbossgentimer.web.dto.channel.ChannelDTO.SubChannelList" +
                    "(c.subChannel, k)" +
                    " FROM Channel c left join c.killTimes k" +
                    " WHERE c.dungeon.id = :dungeonId AND c.mainChannel = :mainChannel" +
                    "", SubChannelList.class)
            .setParameter("dungeonId", dungeonId)
            .setParameter("mainChannel", mainChannel)
            .getResultList();
}

발생한 에러

1
2
3
4
5
6
7
8
9
10
11
12
Caused by: org.hibernate.hql.internal.ast.QuerySyntaxException: Unable to locate class [com.jungguji.windbossgentimer.web.dto.channel.ChannelDTO.SubChannelList] [select new com.jungguji.windbossgentimer.web.dto.channel.ChannelDTO.SubChannelList(c.subChannel, k) FROM com.jungguji.windbossgentimer.domain.channel.Channel c left join c.killTimes k WHERE c.dungeon.id = :dungeonId AND c.mainChannel = :mainChannel]
    at org.hibernate.hql.internal.ast.QuerySyntaxException.convert(QuerySyntaxException.java:74)
    at org.hibernate.hql.internal.ast.ErrorTracker.throwQueryException(ErrorTracker.java:93)
    at org.hibernate.hql.internal.ast.QueryTranslatorImpl.analyze(QueryTranslatorImpl.java:282)
    at org.hibernate.hql.internal.ast.QueryTranslatorImpl.doCompile(QueryTranslatorImpl.java:192)
    at org.hibernate.hql.internal.ast.QueryTranslatorImpl.compile(QueryTranslatorImpl.java:144)
    at org.hibernate.engine.query.spi.HQLQueryPlan.<init>(HQLQueryPlan.java:113)
    at org.hibernate.engine.query.spi.HQLQueryPlan.<init>(HQLQueryPlan.java:73)
    at org.hibernate.engine.query.spi.QueryPlanCache.getHQLQueryPlan(QueryPlanCache.java:162)
    at org.hibernate.internal.AbstractSharedSessionContract.getQueryPlan(AbstractSharedSessionContract.java:604)
    at org.hibernate.internal.AbstractSharedSessionContract.createQuery(AbstractSharedSessionContract.java:716)
    ... 73 more

해결

Inner class로 되어있던 DTO를 class로 생성한다.

따로 생성한 DTO

1
2
3
4
5
6
7
8
9
10
11
12
@NoArgsConstructor
@Getter
public class SubChannelListResponseDTO {
    private Integer subChannel;
    private KillTime killTime;

    @Builder
    public SubChannelListResponseDTO(Integer subChannel, KillTime killTime) {
        this.subChannel = subChannel;
        this.killTime = killTime;
    }
}

결과

Junit Test 통과한 모습

P.S

  • 일반적으로 class명과 table명을 헷갈려 대소문자 때문에 발생하는 에러 이므로 대소문자도 잘 확인 하여야 한다.

댓글 공유

백준 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));

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job