[투 포인터] 백준 1764번 듣보잡 - Java

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

✅ 문제

듣도 보도 못한 사람 수 N명

보도 못한 사람 수 M명

두 명단 모두에 있는 사람을 찾아 사전 순 정렬 후 출력

 

투포인터를 사용하려면 정렬 필수!

🔑 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[] A = new String[N];
        String[] B = new String[M];

        for (int i = 0; i < N; i++) {
            A[i] = br.readLine();
        }

        for (int j = 0; j < M; j++) {
            B[j] = br.readLine();
        }

        // 정렬
        Arrays.sort(A);
        Arrays.sort(B);

        // 투포인터 알고리즘 적용
        int A_index = 0;
        int B_index = 0;
        int count = 0;

        while (A_index != N && B_index != M) {
            String A_str = A[A_index];
            String B_str = B[B_index];

            // 2개의 이름이 같으면?
            if (A_str.equals(B_str)) {
                count++;
                sb.append(A_str + "\n");
                A_index++;
                B_index++;
            } else if (A_str.compareTo(B_str) < 0) { // 사전순으로 A가 더 작을 때
                A_index++;
            } else {
                B_index++;
            }
        }
        System.out.println(count);
        System.out.println(sb);
    }
}

• A와 B는 사전순 정렬되어 있음
• 두 배열을 각각 탐색하며,
  • 동일한 이름이면 교집합이므로 출력 + 인덱스 모두 증가
  • A가 작으면 A를 한 칸 앞으로 (더 큰 값과 비교하기 위해) = A 인덱스 증가
  • B가 작으면 B를 한 칸 앞으로 = B 인덱스 증가
• 시간복잡도
  • 정렬: O(N log N + M log M)
  • 투포인터: O(N + M)
    → 총 O(N log N + M log M)으로 매우 효율적!
• 문제에서 N, M 이 최대 50만이라 HashSet 또는 투포인터 기법으로 풀이 필요
• N^2 대신 N+M 이 빠르고 메모리 효율 좋음
• 아래는 HashSet을 활용한 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashSet<String> unheard = new HashSet<>();
        List<String> result = new ArrayList<>();

        // 듣도 못한 사람 저장
        for (int i = 0; i < N; i++) {
            unheard.add(br.readLine());
        }

        // 보도 못한 사람 확인
        for (int i = 0; i < M; i++) {
            String name = br.readLine();
            if (unheard.contains(name)) {
                result.add(name); // 교집합
            }
        }

        // 사전순 정렬
        Collections.sort(result);

        // 출력
        System.out.println(result.size());
        for (String name : result) {
            System.out.println(name);
        }
    }
}