이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec03_04 {
    public static int solution(int N, int M, int[] arr)
    {
        int count = 0, sum = 0;
        int lptr = 0;

        for (int rptr = 0; rptr < N; ++rptr)
        {
            sum += arr[rptr];
            while (sum > M) sum -= arr[lptr++];
            if (sum == M) count++;
        }

        return count;
    }

    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());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, M, arr));
    }
}

설명

• 투 포인터, 슬라이딩 윈도우 알고리즘을 복합적으로 사용해야 한다.
• lptr 포인터와 rptr 포인터를 사용하여 배열을 탐색한다.
• rptr 포인터는 배열의 처음부터 끝까지 이동하며, sum 변수에 현재 포인터가 가리키는 값을 더한다.
• sum이 M보다 클 경우, lptr 포인터를 이동시키면서 sum에서 값을 뺀다.
• sum이 M과 같아지면, count를 증가시킨다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

첫 번째 코드(중첩 for 문)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec03_03 {
    public static int solution(int N, int M, int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N - (M - 1); ++i)
        {
            int tempSum = 0;
            for(int j = i; j < N - (N - M) + i; ++j) tempSum += arr[j];

            if(tempSum > max) max = tempSum;
        }

        return max;
    }

    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());
        st = new StringTokenizer(br.readLine());
        int [] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, M, arr));
    }
}

두 번째 코드(슬라이딩 윈도우)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec03_03 {
    public static int solution(int N, int K, int[] arr) {
        int tempSum = 0;
        for(int i = 0; i < K; ++i) tempSum += arr[i];
        int max = tempSum;

        for(int i = K; i < N; ++i)
        {
            tempSum += (arr[i] - arr[i - K]);
            if(tempSum > max) max = tempSum;
        }

        return max;
    }

    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 K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int [] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, K, arr));
    }
}

설명

두 번째 코드(슬라이딩 윈도우) 에대한 설명

• tempSum을 0으로 초기화하고, 첫 번째 for 루프에서 배열의 첫 번째 K개의 요소의 합을 계산하여 tempSum에 저장한다.
• 초기 최대값 max를 첫 윈도우의 합인 tempSum으로 설정한다.
• 두 번째 for 루프에서는 슬라이딩 윈도우 기법을 사용하여 다음 요소를 더하고, 이전 요소를 빼서 새로운 윈도우의 합을 구한다. 이 합이 max보다 크면 max를 갱신한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

첫 번째 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class sec03_02 {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2) {
        ArrayList<Integer> integers = new ArrayList<>();
        HashMap<Integer, Boolean> map = new HashMap<>();

        for (int i : arr1) map.put(i, false);
        for (int i : arr2) if(map.containsKey(i)) integers.add(i);
        Collections.sort(integers);

        return integers;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr2 = new int[M];
        for(int i = 0; i < M; i++) arr2[i] = Integer.parseInt(st.nextToken());

        for (Integer i : solution(arr, arr2)) System.out.print(i + " ");
    }
}

두 번째 코드(투 포인터)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec03_02 {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2) {
        ArrayList<Integer> integers = new ArrayList<>();
        Arrays.sort(arr1); Arrays.sort(arr2);
        int ptr1 = 0, ptr2 = 0;
        
        while (ptr1 < arr1.length && ptr2 < arr2.length)
        {
            if (arr1[ptr1] == arr2[ptr2])
            {
                integers.add(arr1[ptr1]);
                ++ptr1;
                ++ptr2;
            }
            else if (arr1[ptr1] < arr2[ptr2]) ++ptr1;
            else if (arr1[ptr1] > arr2[ptr2]) ++ptr2;
        }

        return integers;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr2 = new int[M];
        for(int i = 0; i < M; i++) arr2[i] = Integer.parseInt(st.nextToken());

        for (Integer i : solution(arr, arr2)) System.out.print(i + " ");
    }
}

설명

두 번째 코드(투 포인터)에 대한 설명

• 두 배열 arr1과 arr2를 정렬한다.
• 두 배열의 포인터 ptr1과 ptr2를 초기화한다.
  
  
• 두 포인터를 이동시키면서 공통된 원소를 찾는다.
  - arr1[ptr1]와 arr2[ptr2]가 같으면 해당 원소를 결과 리스트에 추가하고 두 포인터를 모두 증가시킨다.
  - arr1[ptr1]가 arr2[ptr2]보다 작으면 ptr1을 증가시킨다.
  - arr1[ptr1]가 arr2[ptr2]보다 크면 ptr2를 증가시킨다.
  
  
• 두 포인터 중 하나가 배열의 끝에 도달할 때까지 위 과정을 반복한다.
• 결과 리스트를 반환한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

첫 번째 코드(정렬 알고리즘을 이용한 방법)

package inflearn_algorithm.chapter3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec03_01 {
    public static int[] solution(int [] arr1, int [] arr2) {
        int[] mergeArr = new int[arr1.length + arr2.length];
        for (int i = 0; i < mergeArr.length; i++) {
            if(i < arr1.length) mergeArr[i] = arr1[i];
            else mergeArr[i] = arr2[i - arr1.length];
        }
        Arrays.sort(mergeArr);

        return mergeArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());

        for (int i : solution(arr1, arr2)) System.out.print(i + " ");
    }
}

두 번째 코드(투 포인터를 이용한 방법)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec03_01 {
    public static int[] solution(int[] arr1, int[] arr2) {
        int[] mergeArr = new int[arr1.length + arr2.length];
        int ptr1 = 0, ptr2 = 0, i = 0;

        while (ptr1 < arr1.length && ptr2 < arr2.length) {
            if (arr1[ptr1] <= arr2[ptr2]) mergeArr[i++] = arr1[ptr1++];
            else mergeArr[i++] = arr2[ptr2++];
        }

        while (ptr1 < arr1.length) mergeArr[i++] = arr1[ptr1++];
        while (ptr2 < arr2.length) mergeArr[i++] = arr2[ptr2++];

        return mergeArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());

        for (int i : solution(arr1, arr2)) System.out.print(i + " ");
    }
}

설명

두 번째 코드에 대한 설명

• ptr1과 ptr2는 각각 arr1과 arr2의 현재 위치를 가리키며, 두 배열의 끝에 도달할 때까지 반복된다.
• 결과 배열인 mergeArr는 arr1과 arr2의 길이를 합친 크기로 초기화된다.
• 두 배열의 요소를 비교하며 작은 값을 결과 배열에 추가하고, 포인터를 증가시킨다.
• 한 배열의 모든 요소를 처리한 후 다른 배열의 나머지 요소들을 모두 결과 배열에 추가한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec02_12 {
    public static int solution(int N, int M, int[][] arr){
        int count = 0;

        // 순위를 저장할 배열
        int[][] rank = new int[M][N + 1];

        // 각 테스트에서 학생들의 순위를 미리 계산
        for (int k = 0; k < M; ++k)
        {
            for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
        }

        // 학생 쌍 (i, j) 에 대해 비교
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j)
            {
                int temp = 0;
                for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
                if (temp == M) ++count;
            }
        }

        return count;
    }

    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());
        int[][] arr = new int[M][N];

        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        System.out.println(solution(N, M, arr));
    }
}

설명

• rank 배열은 각 테스트(M)에서 각 학생(N)의 순위를 저장한다.
• rank[k][x]는 k번째 테스트에서 x 학생의 순위를 의미한다.

for (int k = 0; k < M; ++k) {
    for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
}

• 각 테스트에 대해, 학생들의 순위를 계산하고 rank 배열에 저장한다.
• arr[k][s]는 k번째 테스트에서 s번째 순위인 학생의 번호이다.
• 예를 들어, rank[0][3] = 2라면, 첫 번째 테스트에서 3번 학생은 세 번째 순위라는 뜻이다.

for (int i = 1; i <= N; ++i) 
{
    for (int j = 1; j <= N; ++j)
    {
        int temp = 0;
        for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
        if (temp == M) ++count;
    }
}

• 모든 학생 쌍 (i, j)에 대해 i가 모든 테스트에서 j보다 높은 순위에 있는지를 확인한다.
• 각 테스트마다 rank[k][i] < rank[k][j]인 경우 temp를 증가시킨다.

return count;

• 모든 조건을 만족하는 학생 쌍의 수를 반환한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int solution(int n, int[][] arr)
    {
        int answer = 0, max = 0;

        // 각 학생 i에 대해 반복
        for(int i = 1; i <= n; ++i)
        {
            int count = 0;

            // 다른 모든 학생 j와 비교
            for(int j = 1; j <= n; ++j)
            {

                // 5년 동안 같은 반이었던 적이 있는지 확인
                for(int k = 1; k <= 5; ++k)
                {
                    if(arr[i][k] == arr[j][k])
                    { // 같은 반이었던 경우
                        count++;
                        break; // 더 이상 확인할 필요 없이 다음 학생으로 넘어감
                    }
                }
            }

            // 최대값 갱신
            if(count > max)
            {
                max = count;
                answer = i;
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][6]; // 1-based 인덱스 사용을 위해 배열 크기 설정

        for(int i = 1; i <= N; ++i)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j < 6; j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(N, arr));
    }
}

설명

• 주석 참고

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec02_10 {
    public static int solution(int N, int[][] arr) {
        int count = 0;
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= N; ++j)
            {
                if((arr[i - 1][j] < arr[i][j]) && (arr[i][j - 1] < arr[i][j]) &&
                    (arr[i][j + 1] < arr[i][j]) && (arr[i + 1][j] < arr[i][j]))
                {
                    ++count;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 2][N + 2];
        for (int i = 1; i <= N; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(N, arr));
    }
}

설명

• count 변수를 초기화하여 조건을 만족하는 요소의 개수를 세기 시작한다.
• 중첩된 for 루프를 사용하여 배열의 모든 요소를 검사한다. 루프의 시작 인덱스를 1로 설정하여 배열의 경계를 초과하지 않도록 한다.
• 각 요소 arr[i][j]가 상하좌우의 요소보다 큰지 확인하는 조건문을 사용한다.
• 조건을 만족하는 경우 count를 1 증가시킨다.
• 모든 요소를 검사한 후 count 값을 반환한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

처음 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec02_09 {
    public static int solution(int N, int[][] numArr) {
        int rightUp = 0;
        for(int i = 0; i < N; ++i)
        {
            int colSum = 0;
            for(int j = 0; j < N; ++j)
            {
                colSum += numArr[j][i];
                if(i + j == N - 1) rightUp += numArr[i][j];
            }
            numArr[N][i] = colSum;
        }
        int max = 0;
        for(int i = 0; i < N; ++i) if(max < numArr[i][N]) max = numArr[i][N];
        for(int i = 0; i < N; ++i) if(max < numArr[N][i]) max = numArr[N][i];
        if(max < rightUp) max = rightUp;
        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];
        int rightDown = 0;
        for(int i = 0; i < N; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int rowSum = 0;
            for(int j = 0; j < N; ++j)
            {
                arr[i][j] = Integer.parseInt(st.nextToken());
                rowSum += arr[i][j];
                if(i == j) rightDown += arr[i][j];
            }
            arr[i][N] = rowSum;
        }
        arr[N][N] = rightDown;
        System.out.println(solution(N, arr));
    }
}

개선한 코드

package inflearn_algorithm.chapter2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec02_09 {
    public static int solution(int N, int[][] numArr) {
        int max = 0;
        int rightUp = 0;
        int rightDown = 0;

        for (int i = 0; i < N; ++i)
        {
            int rowSum = 0;
            int colSum = 0;
            for (int j = 0; j < N; ++j)
            {
                rowSum += numArr[i][j];
                colSum += numArr[j][i];
                if (i == j) rightDown += numArr[i][j];
                if (i + j == N - 1) rightUp += numArr[i][j];
            }
            max = Math.max(max, rowSum);
            max = Math.max(max, colSum);
        }

        max = Math.max(max, rightDown);
        max = Math.max(max, rightUp);

        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][N];

        for (int i = 0; i < N; ++i)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(N, arr));
    }
}

개선된 코드에 대한 설명

• 초기 변수 설정
  max 변수는 최댓값을 저장하기 위해 사용된다.
  rightUp 변수는 오른쪽 위 대각선의 합을 저장한다.
  rightDown 변수는 오른쪽 아래 대각선의 합을 저장한다.
  
  
• 이중 반복문을 통한 합 계산
  외부 반복문 for (int i = 0; i < N; ++i)는 행을 기준으로 반복한다.
  내부 반복문 for (int j = 0; j < N; ++j)는 열을 기준으로 반복한다.
  rowSum 변수는 현재 행의 합을 계산한다.
  colSum 변수는 현재 열의 합을 계산한다.
  if (i == j) 조건문을 통해 오른쪽 아래 대각선(rightDown)의 합을 계산한다.
  if (i + j == N - 1) 조건문을 통해 오른쪽 위 대각선(rightUp)의 합을 계산한다.
  
  
• 최대값 갱신
  각 행의 합(rowSum)과 각 열의 합(colSum)을 계산한 후, 현재의 max 값과 비교하여 최대값을 갱신한다.
  
  
• 대각선의 합과 비교
  오른쪽 아래 대각선의 합(rightDown)과 오른쪽 위 대각선의 합(rightUp)을 계산한 후, 현재의 max 값과 비교하여 최대값을 갱신한다.
  
  
• 최종 결과 반환
  최종적으로 계산된 최대값(max)을 반환한다.