99클럽 코테 스터디 13일차 TIL 숫자 카드

📝 문제

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

🔥 시도해본 접근 방식

 

입력으로 들어온 문자열중 2, 4번째 라인을 split(" ")을 통하여 배열로 만들고 반복문을 선언하여 4번째 라인 배열의 원소가 2번째 라인 배열의 원소에 속한다면 1 아니라면 0 을 출력하는 이중 포문을 선언 하여 풀어보기로 생각하고 접근하였다.

 

1️⃣ 첫번째 시도

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String ownCardCount = sc.nextLine();
        String ownCardString = sc.nextLine();
        String comparerCardCount = sc.nextLine();
        String comparerCardString = sc.nextLine();

        String[] ownCards = ownCardString.split(" ");
        String[] comparerCards = comparerCardString.split(" ");
        String[] answer = new String[comparerCards.length];

        for (int i = 0; i < comparerCards.length; i++) {
            answer[i] = "0";
            for (String ownCard : ownCards) {
                if (comparerCards[i].equals(ownCard)) {
                    answer[i] = "1";
                    continue;
                }
            }
            System.out.print(answer[i] + " ");
        }
    }
}

 

다음과 같이 작성하여 첫 제출을 하였으나 시간 초과가 발생하였다.

문제를 보았을 때 배열의 사이즈가 최대 500,000까지 될 수 있었으므로 시간복잡도가 O(N^2)인 코드로 풀릴 수 가 없는 문제였다.

그래서 시간복잡도를 줄일 수 있는 해쉬로 풀면 될 것 같다는 생각이 들었다.

✨ 성공 코드

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String ownCardCount = sc.nextLine();
        String ownCardString = sc.nextLine();
        String comparerCardCount = sc.nextLine();
        String comparerCardString = sc.nextLine();

        String[] comparerCards = comparerCardString.split(" ");

        HashMap<String, String> hm = new HashMap<>();

        for (String ownCardNumber : ownCardString.split(" ")) {
            hm.put(ownCardNumber, "1");
        }

        for (int i = 0; i < comparerCards.length; i++) {
            System.out.print(hm.getOrDefault(comparerCards[i], "0"));

            if (i < comparerCards.length - 1) {
                System.out.print(" ");
            }
        }
    }
}

해쉬 맵을 선언하여 가지고 있는 카드 배열을 넣어주되 키는 카드번호, 값은 1을 넣어주었다.

비교할 배열의 카드번호를 키로 넣었을때 존재하면 1, 없으면 0이 출력되도록 하였다.