[백준 10816번] 숫자 카드2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

정답

처음에는 이진 탐색 트리를 사용해서 문제를 풀었다. 테스트 케이스를 돌렸을때 출력값은 맞았지만, 시간 초과가 떠서 고민이 많았다. 내가 아는 한 이진 탐색 트리는 빠른 탐색 방법중 하나였다. 너무 몰라서 알고리즘 분류를 보니 이분 탐색, 해시를 사용한 집합과 맵 이라고 되어있었다. 아 생각해보니 해시를 이용하면 간단하게 풀수 있었다. 정렬을 할 필요없는 문제는 해시를 사용하는게 더 빠르다는 것을 알게 되었다. 일단 정답는 해시와 이진 탐색 트리 둘다의 코드를 올리겠다.

/////해시
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        String[] cards = br.readLine().split(" ");

        //카드들을 담을 HashMap
        HashMap<String, LinkedList<Integer>> hm = new HashMap<String, LinkedList<Integer>>();
        for(int i=0; i<cards.length ; i++) {
            if(hm.containsKey(cards[i])) {//키가 존재하는 경우
                LinkedList<Integer> list = hm.get(cards[i]);
                list.add(Integer.parseInt(cards[i]));
            }else {    //키가 존재하지 않는 경우 새로운 LinkedList 만들어서 put
                LinkedList<Integer> list = new LinkedList<Integer>();
                list.add(Integer.parseInt(cards[i]));
                hm.put(cards[i], list);
            }
        }

        //찾을 카드 갯수
        int M = Integer.parseInt(br.readLine());
        String[] findcards = br.readLine().split(" ");

        for(int i=0; i<findcards.length ;i++) {
            if(hm.containsKey(findcards[i])) {//찾으려는 숫자가 존재하는 경우
                LinkedList<Integer> list = hm.get(findcards[i]);
                int size = list.size();
                sb.append(size).append(" ");
            }else {//찾으려는 숫자가 없는 경우
                sb.append("0 ");
            }
        }
        bw.write(sb.toString());

        br.close();
        bw.flush();
        bw.close();
    }

}

////이진 탐색 트리
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String [] cards = br.readLine().split(" ");

        //최상위를 가르키는 노드 생성
        Card top =null;
        for(int i=0;i<N;i++) {
            //숫자카드 먼저 생성
            Card card = new Card(Integer.parseInt(cards[i]), 1 , null, null);
            Card current,parent=null;
            current = top;
            top = insert(card,parent,current,top);

        }
        int M = Integer.parseInt(br.readLine());
        String[] findCards = br.readLine().split(" ");
        for(int j=0;j<M ;j++) {
            Card currentCard = top;
            find(Integer.parseInt(findCards[j]),currentCard);
        }

        br.close();
        bw.flush();
        bw.close();
    }
    public static Card insert(Card newCard,Card parent,Card current,Card topCard) {
        if(topCard == null) {
            topCard = newCard;
            return topCard;
        }else if(current == null){
            if(parent.getValue()>newCard.getValue()) {
                parent.setLeftCard(newCard);
            }else {
                parent.setRightCard(newCard);
            }
        }else if(current.getValue() == newCard.getValue()) {
            int count = current.getCount();
            current.setCount(++count);
            return topCard;
        }else if(current.getValue()> newCard.getValue()) {
            parent = current;
            current = parent.getLeftCard();
            insert(newCard, parent, current, topCard);
        }else {
            parent = current;
            current = parent.getRightCard();
            insert(newCard, parent, current, topCard);
        }
        return topCard;
    }
    public static void find(int value,Card current) {
        if(current == null) {
            System.out.print("0 ");
            return;
        }
        if(current.getValue() == value) {
            System.out.print(current.getCount()+" ");
            return;
        }else {
            //현재 가리키는 카드가 더 크면 왼쪽으로
            if(current.getValue()>value) {
                current = current.getLeftCard();
            }else {
                current = current.getRightCard();
            }
            find(value,current);
        }
    }
    static class Card{
        int value;
        int count;
        Card leftCard,rightCard;
        public Card(int value, int count, Card leftCard, Card rightCard) {
            this.value = value;
            this.count = count;
            this.leftCard = leftCard;
            this.rightCard = rightCard;
        }
        public int getValue() {
            return this.value;
        }
        public int getCount() {
            return this.count;
        }
        public void setCount(int count) {
            this.count = count;
        }
        public Card getLeftCard() {
            return this.leftCard;
        }
        public Card getRightCard() {
            return this.rightCard;
        }
        public void setLeftCard(Card card) {
            this.leftCard = card;
        }
        public void setRightCard(Card card) {
            this.rightCard = card;
        }
    }

}