애정코딩 💻

알고리즘 2021.11.26 댓글 0 Joana

11월 26일 2문제 - Java : Two pointers

1. 두 배열 합치기

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.


- 후위 연산을 이용하여 a<b 에서 a가 작을 경우에 a를 add 한 후에 a증감된다. 

- 서로 다른 배열을 합칠 때 while 문 , && 조건문을 이용한다.

import java.util.ArrayList;
import java.util.Scanner;

public class Test3_01 {

  public ArrayList<Integer> solution(int first, int[] firstArr, int second, int[] secondArr) {
    ArrayList<Integer> result = new ArrayList<>();
    int pointA = 0;
    int pointB = 0;
    while (first > pointA && second > pointB) {
      if (firstArr[pointA] < secondArr[pointB]) {
        result.add(firstArr[pointA++]);
      } else {
        result.add(secondArr[pointB++]);
      }
    }

    while (first > pointA) {
      result.add(firstArr[pointA++]);
    }
    while (second > pointB) {
      result.add(secondArr[pointB++]);
    }

    return result;
  }

  public static void main(String[] args) {
    Test3_01 main = new Test3_01();
    Scanner sc = new Scanner(System.in);
    int firstNumber = sc.nextInt();
    int[] firstArr = new int[firstNumber];
    for (int i = 0; i < firstNumber; i++) {
      firstArr[i] = sc.nextInt();
    }

    int secondNumber = sc.nextInt();
    int[] secondArr = new int[secondNumber];
    for (int i = 0; i < secondNumber; i++) {
      secondArr[i] = sc.nextInt();
    }

    for (int x : main.solution(firstNumber, firstArr, secondNumber, secondArr)) {
      System.out.print(x + " ");
    }
  }
}

 

2. 공통원소 구하기

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.


 Arrays.sort 사용

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Test3_02 {
    public ArrayList<Integer> solution(int first, int[] firstArr, int second, int[] secondArr){
        ArrayList<Integer> result = new ArrayList<>();
        int pA = 0;
        int pB = 0;
        Arrays.sort(firstArr);
        Arrays.sort(secondArr);

        while (pA<first && pB<second){
            if(firstArr[pA] == secondArr[pB]){
                result.add(firstArr[pA++]);
                pB++;
            }else if(firstArr[pA]<secondArr[pB]){
                pA++;
            }else{
                pB++;
            }

        }


        return result;
    }


    public static void main(String[] args) {
        Test3_02 main = new Test3_02();
        Scanner sc = new Scanner(System.in);
        int firstNumber = sc.nextInt();
        int[] firstArr = new int[firstNumber];
        for (int i = 0; i < firstNumber; i++) {
            firstArr[i] = sc.nextInt();
        }

        int secondNumber = sc.nextInt();
        int[] secondArr = new int[secondNumber];
        for (int i = 0; i < secondNumber; i++) {
            secondArr[i] = sc.nextInt();
        }

        for (int x : main.solution(firstNumber, firstArr, secondNumber, secondArr)) {
            System.out.print(x + " ");
        }
  }
}
반응형