백준 1920번: 수 찾기

문제

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

코드

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

        br.readLine();
        int[] array2 = convertStringArrayToIntegerArray(br.readLine().split(" "));

        int[] answer = solution(array1, array2);

        for (int i : answer) {
            System.out.println(i);
        }
    }
}

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;
}

public static int[] solution(int[] array1, int[] array2) {
    Arrays.sort(array1);

    int[] answer = new int[array2.length];

    int index = 0;
    for (int i : array2) {
        answer[index++] = Arrays.binarySearch(array1, i) < 0 ? 0 : 1;
    }

    return answer;
}

흐름

  1. 이진 탐색(Binary Search)을 위해 검색 할 array를 우선 정렬한다.
  2. array에 value가 존재하면 1, 없으면 0으로 저장하기 위한 answer array를 생성한다.
  3. array에 value가 존재하는 지 확인하기 위해 array2를 돌면서 element를 꺼낸다.
  4. 꺼낸 element를 이진 탐색으로 array안에서 검색해서 존재하면 1, 아니면 0을 저장한다.
  5. 결과를 return 한다.
  6. 끝.

Arrays.binarySearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int binarySearch(int[] a, int key) {
    return binarySearch0(a, 0, a.length, key);
}

// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                    int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}
  1. 기준이 되는 array와 array에서 검색 할 value(key)를 입력 받는다.
  2. from index가 to index보다 작거나 같은 동안 반복하면서
  3. 두 index를 더한 값을 >>> 연산을 통해 나눈다.
    1. ex) 15(10) -> 1111(2), 15 >>> 1 = 1111 >>> 1 이므로, 0111(2)가 되고 이는 10진수 7이므로 15를 2로 나눈 값과 같다.
    2. ‘>>’ 연산은 부호 비트를 보존하고, ‘>>>’ 연산은 부호 비트 관계없이 무조건 0으로 채운다.
  4. 중간이 되는 index를 구해서 array의 중간 값을 구한 후
  5. 현재 값이 중간 값 보다 작은 지 큰지 비교하면서 array에 존재하는지 확인하고
  6. 존재한다면 array에서 현재 값의 index를 return하고
  7. 존재하지 않는 다면 array에서 현재 값의 가장 가까운 index를 음수로 return 한다.

결과

결과

테스트 케이스

1
2
3
4
assertArrayEquals(new int[] {1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0}, test.solution(new int[] {1, 3, 4, 6, 9, 13, 18}, new int[] {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}));
assertArrayEquals(new int[] {1, 1, 0, 0, 1}, test.solution(new int[] {4, 1, 5, 2, 3}, new int[] {1, 3, 7, 9, 5}));
assertArrayEquals(new int[] {1}, test.solution(new int[] {1,2}, new int[] {2}));
assertArrayEquals(new int[] {0,1,0,1,0,1,0,1,0,1}, test.solution(new int[] {2,4,6,8,10}, new int[] {1,2,3,4,5,6,7,8,9,10}));

댓글 공유

백준 2869번: 달팽이는 올라가고 싶다

문제

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

코드

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 class 달팽이는_올라가고_싶다 {
    public static void main(String[] args) throws IOException {
        String[] input = getInputData(System.in).split(" ");
        int[] abv = convertStringArrayToIntegerArray(input);

        System.out.println(solution(abv));
    }

    public static String getInputData(InputStream in) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(in))) {

            return br.readLine();
        }
    }

    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;
    }

    public static int solution(int[] abv) {
        return (abv[2] - abv[1] - 1) / (abv[0] - abv[1]) + 1;
    }
}

흐름

  1. 달팽이는 하루에 A 만큼 올라가는데 자면서 B만큼 미끄러지므로 하루에 (A - B) 만큼 씩 올라가서 V미터 만큼 올라가면 된다.
  2. 하지만 꼭대기에 도달하면 미끄러지지 않는다고 하였으므로, 꼭대기(V) 에서 미끄러지는 만큼(B) 을 뺀 거리만큼만 올라가면 된다. (V - B)
  3. 그럼 수식은 (V - B) / (A / B)가 되고 int형은 소수점을 없애므로 나누어떨어지지 않으면 + 1을 하는데
  4. (V - B)에서 - 1을 먼저하고 무조건 1을 더한다.

(V - B - 1) / (A - B) + 1

  • V-B를 X, A-B를 y로 가정
  1. x/y가 나누어 떨어지는 경우
    1. x / y = d 일 때 (x-1)/y 는 반드시 d보다 작다.
    2. int형은 소수점 아래를 없애므로 x-1 /y = d - 1이 되고,
    3. +1을 하면 d가 된다.
  2. x/y가 나누어 떨어지지 않는 경우
    1. x / y = d + f 일 때 y를 양변에 곱하면
    2. x = y(d + f) 여기서 양변에 1을 빼면,
    3. x - 1 = y(d + f) - 1 여기서 y를 양변에 나누면
    4. (x - 1) / y = (d + f) -1 / y 이 된다.
    5. 이 때 1 / y 는 y >= 2 이고 int형은 소수점 아래를 없애버리므로 1 / y 는 없어진다.
      1. y >= 2 인 이유는 현재 x / y가 나누어 떨어지지 않는 경우임을 상정하고 있으므로 y가 1이면 나누어 떨어지기 때문에 y는 2보다 크게 된다.
    6. 그럼 (x - 1) / y = d + f 이 되고 +1을 하면,
    7. (x - 1) / y + 1 = d + f + 1 된다.

결과

결과

테스트 케이스

1
2
3
4
5
6
7
assertEquals(4, test.solution(new int[] {2,1,5}));
assertEquals(2, test.solution(new int[] {5,1,6}));
assertEquals(999999901, test.solution(new int[] {100,99,1000000000}));
assertEquals(1, test.solution(new int[] {5,0,5}));
assertEquals(4, test.solution(new int[] {3,2,6}));
assertEquals(2, test.solution(new int[] {100,1,101}));
assertEquals(3, test.solution(new int[] {3,1,6}));

참고 사이트

댓글 공유

백준 11047번: 동전 0

문제

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

코드

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

    String[] coinAndMoneyArray = coinAndMoney.split(" ");

    int coinAmount = Integer.parseInt(coinAndMoneyArray[0]);
    long money = Long.parseLong(coinAndMoneyArray[1]);

    long[] coinCategory = getCoincategory(coinAmount, br);

    long answer = solution(coinAmount, money, coinCategory);

    System.out.println(answer);
}

public static long[] getCoincategory(int coinAmount, BufferedReader br) throws IOException {
    long[] result = new long[coinAmount];
    for (int i = 0; i < coinAmount; i++) {

        result[i] = Integer.parseInt(br.readLine());
    }

    return result;
}

public static long solution(int n, long money, long[] array) {
    long answer = 0;

    for (int i = n - 1; i >= 0; i--) {
        if (array[i] > money) {
            continue;
        }

        answer += (money / array[i]);
        money %= array[i];

        if (money == 0) {
            break;
        }
    }

    return answer;
}

흐름

  1. 돈의 종류 만큼 돌면서 큰 수 부터 가지고 있는 돈을 나눔
  2. 돈의 가치가 더 큰 경우엔 나눌 수 없으므로 continue
  3. 돈으로 갖고 있는 돈을 나눈 값을 더하고 남은 값은 다시 나눠야 하므로 money에 다시 저장함
  4. momeny가 0이 되면 나눌 돈이 없는 것이므로 사용한 돈 갯수 return
  5. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long[] array = new long[] {1,5,10,50,100,500,1000,5000,10000,50000};
assertEquals(6, test.solution(10, 4200, array));
assertEquals(12, test.solution(10, 4790, array));
assertEquals(1, test.solution(10, 50000, array));
assertEquals(2000, test.solution(10, 100000000, array));

array = new long[] {1};
assertEquals(2, test.solution(1, 2, array));
assertEquals(1, test.solution(1, 1, array));
assertEquals(100000000, test.solution(1, 100000000, array));

array = new long[] {1, 5};
assertEquals(1, test.solution(2, 5, array));

array = new long[] {1, 3};
assertEquals(2, test.solution(2, 4, array));

array = new long[] {1, 100};
assertEquals(1, test.solution(2, 100, array));

array = new long[] {5000};
assertEquals(1, test.solution(1, 5000, array));
  • 나머지는 입력 값 처리이고 solution 메서드가 주요 로직이므로 solution 메서드를 테스트
  • 이렇게 테스트 할 경우 입력처리 때문에 에러가 발생 할 수 있으니 꼭 java application으로 함께 테스트 해볼 것

댓글 공유

백준 1152번: 단어의 개수

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long solution(String args) {
    char[] tochar = args.trim().toCharArray();

    long answer = 0;
    if (tochar.length == 0) {
        return answer;
    }

    for (char ch : tochar) {
        if (ch == ' ') {
            ++answer;
        }
    }

    return answer + 1;
}

흐름

  1. 문자열 앞 뒤로 공백이 존재 할 수 있으므로 trim()
  2. 공백만 있는 문자열인 경우 0 return
  3. char array로 변환된 문자열을 돌면서 공백인 경우 count 증가
  4. 공백을 기준으로 단어가 만들어졌으니 공백 개수 + 1 return
    • ex) hello, wolrd! = 공백 1개, 문자 2개
  5. 끝

결과

결과

테스트 케이스

1
2
3
4
5
assertEquals(6, test.solution("The Curious Case of Benjamin Button"));
assertEquals(3, test.solution(" Mazatneunde Wae Teullyeoyo"));
assertEquals(2, test.solution("Teullinika Teullyeotzi "));
assertEquals(7, test.solution(" a b c d e f g "));
assertEquals(0, test.solution(" "));

전체 코드

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/baekjoon/string/%EB%8B%A8%EC%96%B4%EC%9D%98_%EA%B0%9C%EC%88%98.java

댓글 공유

백준 11399번: ATM

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

소스

1
2
3
4
5
6
7
8
9
10
11
12

public static int solution(int n, int[] times) {
    Arrays.sort(times);
    
    int answer = 0;
    for (int i = 0; i < times.length; i++) {
        answer += times[i] * (n-i);
    }
    
    return answer;
}

흐름

  1. 시간이 짧게 걸리는 사람이 앞에 올수록 전체 수행 시간이 짧아지므로 sorting부터 실행

  2. 앞에 사람이 걸리는 시간은 그 뒤 사람들도 그만큼 시간이 + 되는 것이므로 n-i 한 값을 곱함

    ex) 첫 번째 사람이 1분 걸리면 2, 3, 4, 5 번째 사람도 1분씩 더 걸리게 됨

  3. 다 더한 값을 출력하면 끝

댓글 공유

Junggu Ji

author.bio


author.job