[코딩 테스트 문제 풀이 시리즈] 배열 기초 + 투 포인터 개념 정복 (백준 10807, 10871, 3273)

 

문제 개요

오늘은 백준에서 배열 문제 2문제, 조건 출력 1문제, 그리고 투 포인터 알고리즘을 활용하는 대표 문제를 풀어보았다.

 

문제를 단순히 푸는 것에 그치지 않고, 배열의 기본 패턴과 효율적인 쌍 찾기 방법인 Two Pointer까지 이해하려는 게 목표였다.

---

1. 백준 10807번 - 개수 세기

문제 설명

정수 N개가 주어진다. 그중에서 특정 정수 v가 몇 개 포함되어 있는지를 출력하는 간단한 문제이다.

 

문제 조건

• 1 ≤ N ≤ 100
• -100 ≤ 각 정수 ≤ 100

풀이 방식

입력받은 수열을 배열에 저장한 뒤, 반복문을 통해 v와 같은 값이 몇 개인지 카운팅하면 된다. 배열과 반복문의 가장 기초적인 사용법을 익힐 수 있는 문제다.

코드

import java.util.Scanner;

public class _10807_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
        int V = sc.nextInt();

        int count = 0;
        for (int i = 0; i <  N; i++) {
            if (a[i] == V){
                count++;
            }
        }
        System.out.println(count);
    }
}

 

---

2. 백준 10871번 - X보다 작은 수

문제 설명

정수 N개가 주어지고, 기준값 X가 주어졌을 때, 배열에서 X보다 작은 수를 모두 출력하는 문제다.

문제 조건

• 1 ≤ N, X ≤ 10,000

풀이 방식

배열에 값을 입력받고, 다시 반복문을 돌면서 현재 값이 X보다 작으면 공백으로 구분하여 출력하면 된다. 문제의 핵심은 조건 분기와 출력을 정확하게 해내는 것.

코드

import java.util.Scanner;

public class _10871_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            if (A[i] < X) {
                System.out.print(A[i] + " ");
            }
        }
    }
}

 

---

3. 백준 3273번 - 두 수의 합

문제 설명

수열에서 두 수를 더했을 때 특정 값 X가 되는 서로 다른 수의 쌍이 몇 개 있는지를 구하는 문제다. 단순한 이중 반복문 방식은 시간 초과가 발생한다.

 

문제 조건

• 1 ≤ N ≤ 100,000
• 1 ≤ 배열의 값 ≤ 1,000,000
• 1 ≤ X ≤ 2,000,000

풀이 방식

배열의 값 존재 여부를 체크할 수 있는 boolean 배열을 만들고, (i, X-i) 형태의 조합이 존재하는지만 확인해서 쌍을 찾는 방식으로 시간 복잡도를 줄였다. 중복을 방지하기 위해 i는 1부터 (X-1)/2까지만 확인한다.

 

코드

import java.util.Scanner;

public class _3273_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextInt();
        int X = sc.nextInt();

        boolean[] exist = new boolean[1000001];
        for (int i = 0; i < N; i++)
            exist[a[i]] = true;

        int ans = 0;
        for (int i = 1; i <= (X - 1) / 2; i++) {
            if (i <= 1000000 && X - i <= 1000000)
                ans += (exist[i] && exist[X - i]) ? 1 : 0;
        }
        System.out.println(ans);
    }
}

 

---

4. 알고리즘 개념 정리 - Two Pointer

Two Pointer란?

정렬된 배열에서 두 개의 포인터를 양 끝에서 시작해 가운데로 이동하며 조건을 만족하는 값을 찾는 탐색 방식이다. 대표적으로 합이 특정 값을 만족하는 쌍 찾기, 부분합 문제, 슬라이딩 윈도우 등에 자주 사용된다.

 

작동 원리

1. 배열이 정렬되어 있어야 한다.
2. left는 0에서 시작, right는 N-1에서 시작.
3. 두 수의 합이 목표보다 작으면 left++, 크면 right–.
4. 합이 정확히 일치하면 count 증가 후 두 포인터 이동.

예시

int left = 0;
int right = arr.length - 1;

while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == X) {
        count++;
        left++;
        right--;
    } else if (sum < X) {
        left++;
    } else {
        right--;
    }
}

 

시간 복잡도

• O(N log N): 정렬
• O(N): 포인터 이동
• → 총 O(N log N)

언제 쓰면 좋은가?

• 두 수 또는 구간의 합이 조건을 만족할 때
• 특정 길이의 구간을 찾거나 최솟값, 최댓값을 찾을 때
• 정렬된 배열 기반 문제에서 시간 줄이고 싶을 때

---

마무리

이번 학습을 통해 다음과 같은 내용을 배울 수 있었다.

• 배열 문제는 반복문과 조건문 연습에 가장 적합하다
• 수의 개수를 세거나 조건에 따라 필터링하는 문제는 배열의 기초
• N이 매우 크다면 브루트포스 방식은 시간 초과가 발생하므로 효율적인 알고리즘이 필요하다
• Two Pointer는 정렬된 배열에서 탐색을 빠르게 수행할 수 있는 강력한 도구다

 

오늘 풀었던 문제들은 모두 기초 문제지만, 배열과 포인터 개념을 탄탄히 잡는 데 매우 도움이 되었고, 앞으로 풀 문제들에 기반이 될 것 같다.