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

참고 사이트

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job