[백준] no1764: 듣보잡

문제

입력되는 듣잡과 보잡중 중복되서 듣보잡인 놈들만 추리기

문제 링크 : https://www.acmicpc.net/problem/1764

---

원리

첫 줄에 입력되는 두 수를 각각 듣잡, 보잡의 수로 받고,

그 뒤로 순차적으로 입력되는 사람을 듣잡과 보잡으로 나누어 저장

둘을 비교해서 완전 듣보잡을 찾기

* ArrayList를 Collections으로 sort할 때, String도 사전순 정렬이 가능하다.

---

풀이방법

1. ArrayList를 사용하는 방법

2. HashSet을 사용하는 방법

3. Deque를 사용하는 방법

 

---

나의 코드

1. ArrayList를 사용하는 방법 [ 백준에서 시간 초과 ]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int hear = Integer.parseInt(st.nextToken());
    int see = Integer.parseInt(st.nextToken());
    List<String> notHear = new ArrayList<>();
    List<String> notSee = new ArrayList<>();
    List<String> notHearAndSee = new ArrayList<>();

    while(hear-->0) notHear.add(br.readLine());
    while(see-->0) notSee.add(br.readLine());

    for(String person : notHear) if(notSee.contains(person)) notHearAndSee.add(person);
    Collections.sort(notHearAndSee);

    bw.write(""+notHearAndSee.size()+"\n");
    for(String person : notHearAndSee) bw.write(person+"\n");

    bw.close();
}

 

2. HashSet을 사용하는 방법 [ 26424kB , 332ms ]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int hear = Integer.parseInt(st.nextToken());
    int see = Integer.parseInt(st.nextToken());
    Set<String> notHear = new HashSet<>();
    List<String> notHearAndSee = new ArrayList<>();

    while(hear-->0) notHear.add(br.readLine());
    while(see-->0) {
        String notSee = br.readLine();
        if(notHear.contains(notSee)) notHearAndSee.add(notSee);
    };

    Collections.sort(notHearAndSee);

    bw.write(""+notHearAndSee.size()+"\n");
    for(String person : notHearAndSee) bw.write(person+"\n");

    bw.close();
}

 

3. Deque를 사용하는 방법 [ 마찬가지로 시간 초과 ]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int hear = Integer.parseInt(st.nextToken());
    int see = Integer.parseInt(st.nextToken());
    Deque<String> notHear = new ArrayDeque<>();
    List<String> notHearAndSee = new ArrayList<>();

    while(hear-->0) notHear.add(br.readLine());
    while(see-->0) {
        String notSee = br.readLine();
        if(notHear.contains(notSee)) notHearAndSee.add(notSee);
    };

    Collections.sort(notHearAndSee);

    bw.write(""+notHearAndSee.size()+"\n");
    for(String person : notHearAndSee) bw.write(person+"\n");

    bw.close();
}

 

---

레퍼런스 코드