[백준 / 실버 4] 1940 : 주몽 (JAVA)

문제

---

풀이방법

1. 탐색할 데이터를 오름차순 정렬한다.

2. 투 포인터 알고리즘 사용

• 투 포인터 i, j를 각각 제일 작은 수와 제일 큰 수에 위치시킨다.
• i와 j가 만날 때까지 포인터를 이동시키며 탐색한다.

 

---

코드

👇🏻 이중포문 사용

package boj1940;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int n = Integer.parseInt(br.readLine());
        int n2 = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] arr2 = new int[n];
        int k=0;
        int count=0;
        boolean equals=true;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j){
                    continue;
                }
                if(arr[i]+arr[j]==n2){
                    equals=true;
                    for(int u=0; u<k; u++ ){
                        if(arr2[u] == arr[i]||arr2[u] == arr[j]){
                            equals = false;
                        }
                    }
                    if(equals==true){
                        arr2[k]=arr[j];
                        k++;
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

👇🏻 투 포인터 사용

package boj1940;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int n = Integer.parseInt(br.readLine());
        int n2 = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] arr2 = new int[n];
        int l=0, r=n-1, count=0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        while(l<r){
            if(arr[l]+arr[r]==n2){
                l++;
                r--;
                count++;
            }else if(arr[l]+arr[r]<n2){
                l++;
            }else {
                r--;
            }
        }
        System.out.println(count);
    }
}

+ 두 수의 차 (투 포인터 사용)

while(l < r && r<n){
            if(arr[r]-arr[l]==n2){
                l++;
                count++;
            }else if(arr[r]-arr[l]>n2){
                l++;
            }else{
                r++;
            }
        }