[99클럽 코테 스터디 13일차 TIL] 백준 - 숫자 카드

99클럽 코테 스터디 13일차 TIL 입니다.

[Silver V] 숫자 카드 - 10815

문제 링크

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 정렬

문제 설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] arr = new boolean[20_000_001]; // 크기를 20,000,001로 변경하여 인덱스 문제 해결
        int n = Integer.parseInt(br.readLine());
        String[] cards = br.readLine().split(" ");
        int m = Integer.parseInt(br.readLine());
        String[] numbers = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();

        for (String card : cards) {
            int c = Integer.parseInt(card);
            if (c < 0) c = Math.abs(c) + 10_000_000;
            arr[c] = true;
        }

        for (String number : numbers) {
            int no = Integer.parseInt(number);
            if (no < 0) no = Math.abs(no) + 10_000_000;
            if (arr[no]) sb.append("1").append(" ");
            else sb.append("0").append(" ");
        }

        System.out.println(sb);
    }
}

• Time: 732 ms

• Memory: 133752 KB

숫자 카드의 숫자 인덱스의 값을 true 로 변경하기 위해 boolean 배열을 선언했다. 숫자 값은 -10,000,000 ~ 10,000,000 까지의 범위를 가지기 때문에 음수 처리를 위해 배열의 크기를 20,000,001 로 선언했다. 음수 값이 들어오면 절대 값으로 변환 후 10,000,000 을 더한 인덱스 값에 넣으려고 한다.

처음엔 절대 값으로 변환해야 하는걸 깜빡해서 헤맸다. 그리고 이 풀이를 훨씬 더 간결하고 쉽게 개선할 수 있는데 아래 풀이와 같다.

개선하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<Integer> set = new HashSet<>();
        int n = Integer.parseInt(br.readLine());
        String[] cards = br.readLine().split(" ");
        int m = Integer.parseInt(br.readLine());
        String[] numbers = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();
        for (String card : cards) set.add(Integer.parseInt(card));
        for (String number : numbers) {
            if (set.contains(Integer.parseInt(number))) sb.append("1").append(" ");
            else sb.append("0").append(" ");
        }

        System.out.println(sb);
    }
}

• Time: 864 ms

• Memory: 153272 KB

HashSet 을 이용한 풀이인데 속도는 조금 느리긴 해도 간결하고 가독성도 좋다. 그리고 실무에서는 숫자 범위가 정해져서 들어오는게 아니기 때문에 어떤 숫자여도 대응이 가능하다.

---

돌아보기

항상 작은 실수들을 한다. 이번에 절대 값 변환을 빼먹었다는걸 알아차린건 질문을 작성하면서 알게 됐다. 뭘 놓친건지 모르면 한번 글로 직접 적어보는 것도 큰 도움이 되는 것 같다.

다음에는

• 여러 자료 구조를 생각하면서 풀기

• 문제를 적어보기

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL