인프런 두 배열 합치기

문제

나의 풀이

import java.util.*;

public class MergeTwoArrays {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 = 0, p2 = 0;
        while(p1 < n && p2 < m) {
            if(a[p1] < b[p2]) {
                answer.add(a[p1++]);
            } else {
                answer.add(b[p2++]);
            }
        }
        while(p1 < n) {
            answer.add(a[p1++]);
        }
        while(p2 < m) {
            answer.add(b[p2++]);
        }
        return answer;
    }
    public static void main(String[] args) {
        MergeTwoArrays T = new MergeTwoArrays();
        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 m = sc.nextInt();
        int b[] = new int[m];
        for(int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        for(int x : T.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}

서로 다른 배열에 포인터들을 두어서 포인터를 증가시켜가며 푸는 전형적인 투 포인터 알고리즘을 이용해서 풀 수 있는 문제다.

결과

인프런 공통원소 구하기

문제

나의 풀이

import java.util.*;

public class CommonElements {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(a);
        Arrays.sort(b);
        int p1 = 0, p2 = 0;
        while(p1 < n && p2 < m) {
            if(a[p1] == b[p2]) {
                answer.add(a[p1++]);
                p2++;
            } else if(a[p1] < b[p2]) {
                p1++;
            } else {
                p2++;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        CommonElements T = new CommonElements();
        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 m = sc.nextInt();
        int b[] = new int[m];
        for(int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        for(int x : T.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}

먼저 두 배열을 오름차순 정렬을 시킨다. a의 p1이 가리키는 원소와 b의 p2가 가리키는 원소가 같으면 answer에 넣어주고나서 p1과 p2를 둘 다 증가시킨다. b의 p2가 더 크다면 p1을 증가시킨다. a의 p1이 더 크다면 p2를 증가시킨다. 이러한 과정을 한쪽이 끝나면 끝나도록 구현하면 된다.

결과

인프런 연속된 자연수의 합

문제

나의 풀이

import java.util.Scanner;

public class ConsecutiveNumbers {
    public int solution(int n) {
        int answer = 0, sum = 0, lt = 0;
        int m = n / 2 + 1; // 연속된 자연수의 합을 구하기 위해 확인해볼 원소는 n / 2 + 1한 값 까지만
        int arr[] = new int[m];
        for(int i = 0; i < m; i++) {
            arr[i] = i + 1;
        }
        for(int rt = 0; rt < m; rt++) {
            sum += arr[rt];
            if(sum == n) {
                answer++;
            }
            while(sum >= n) {
                sum -= arr[lt++];
                if(sum == n) {
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        ConsecutiveNumbers T = new ConsecutiveNumbers();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}

N에 대하여 N을 2로 나눈 몫의 1을 더한 값까지만 확인해보면 된다. 처음에 lt와 rt가 첫번째 인덱스를 가리킨다. lt와 rt의 원소의 합(sum)이 n이면 경우의 수를 증가시키고 lt를 증가시킨다. sum이 n보다 작으면 rt를 증가시킨다. sum이 n보다 크면 lt가 가리키는 값을 빼주고 lt를 증가시킨다.

결과

인프런 모임 장소

문제

나의 풀이

import java.util.ArrayList;

public class MeetingPlace {
    public static int solution(int[][] board) {
        int answer = 0;
        int n = board.length;
        ArrayList<Integer> row = new ArrayList<>();
        ArrayList<Integer> col = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 1) { // 사람이 위치한 경우
                    row.add(i); // 행 위치 저장
                    col.add(j); // 열 위치 저장
                }
            }
        }
        col.sort((a, b) -> a - b); // 열은 오름차순 정렬
        int x = row.get(row.size() / 2); // 행의 중값 위치값 구하기
        int y = col.get(col.size() / 2); // 열의 중간 위치값 구하기
        // (x, y)가 사람들이 만나야할 지점이다.
        for(int p : row) {
            answer += Math.abs(x - p); // 각각의 사람들의 행의 위치와 만나야할 지점의 행의 위치 절댓값 구해서 이동거리에 더해주기
        }
        for(int p : col) {
            answer += Math.abs(y - p); // 각각의 사람들의 열의 위치와 만나야할 지점의 열의 위치 절댓값 구해서 이동거리에 더해주기
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(MeetingPlace.solution(new int[][]{{1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}}));
    }
}

각 사람의 행의 위치를 저장하는 row배열과 각 사람의 열의 위치를 저장하는 col배열을 만들어서 1을 만나면 값을 저장시킨다. col 배열은 정렬을 해주어야 한다. 그런 다음 각각의 배열의 크기에 2를 나누어서 그 값에 해당하는 인덱스에 해당하는 값을 사람들이 모여야 할 지점으로 잡는다. 그런 다음 그 지점에 대하여 각각의 사람들이 얼마나 움직여야 하는지 row배열과 col배열의 각각 원소들의 차를 절댓값으로 구해서 이들을 합해주면 정답이 된다.

결과