링크

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int number = Integer.parseInt(st.nextToken());
        int index = Integer.parseInt(st.nextToken()) - 1;

        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                list.add(i);
                if (number / i != i) list.add(number / i);
            }
        }
        Collections.sort(list);

        System.out.println(list.size() > index ? list.get(index) : "0");
    }
}

리뷰

약수를 구한 뒤 약수 중 K번 째 작은수를 출력하는 문제이다.

약수는 기존처럼 제곱근을 이용해 구해주었다. 그리고 오름차순으로 정렬한 뒤에 K번째 작은 수는 인덱스 상에서는 K-1 번인것을 고려하여 리스트의 사이즈와 비교한 뒤 적절한 값을 출력하도록 하는 문제이다.

링크

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num < min) min = num;
                if (num > max) max = num;
            }
            sb.append(min).append(" ").append(max).append("\n");
        }
        System.out.print(sb);
        br.close();
    }
}

리뷰

첫번째 풀이는 생략하였지만 배열로 입력받아 Arrays.sort를 이용하여 정렬을 통해 최소, 최댓값을 구하였지만 생각보다 시간이 엄청높게나왔다.

그래서 그냥 값을 입력받을 때마다 바로바로 비교하는 방식으로 바꾸어 제출하니 시간이 확줄긴했다.

배열 정렬의 경우 최악의 경우 O(N^2)의 시간복잡도를 가지게되지만 바로 비교하는 경우 O(N)이라 시간차이가 꽤나게된다.

링크

코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int pCount = 0;
        int yCount = 0;

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'p') pCount++;
            else if (s.charAt(i) == 'y') yCount++;
        }
        if (pCount != yCount) answer = false;

        return answer;
    }
}

리뷰

정말 예전에 풀었던 문제인데 리뷰 작성을 안한것을 이제야 알았다. 코드를 새로 고친 것도 아니여서 올리지 말까 고민하다가 그래도 여태 푼 문제들을 올렸는데 몇개만 빼먹고 올리자니 신경쓰여서 올리게되었다 😅

그리고 최근에 JPA 공부에 집중하다보니 알고리즘 문제를 거의 풀지못해서 새롭게 느껴졌는데 큰일이다 🥲

문제 풀이 접근방식은 결국 대문자이든 소문자이든 p와 y의 개수를 세는 것이 핵심이므로 소문자로 통합하여 문자열을 한 글자씩 읽어 두 글자의 카운트를 비교하는 방식으로 접근하였다.

링크

코드

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

public class Main {

    static int[] inputCheckArr = new int[4];
    static int[] checkArr = new int[4];
    static int checkCount;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        char[] inputArr = br.readLine().toCharArray();

        checkCount = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());

            if (checkArr[i] == 0) checkCount++;
        }
        br.close();

        int resultCount = 0;
        for (int i = 0; i < P; i++) {
            add(inputArr[i]);
        }
        if (checkCount == 4) resultCount++;

        for (int i = P; i < S; i++) {
            int j = i - P;
            add(inputArr[i]);
            remove(inputArr[j]);

            if (checkCount == 4) resultCount++;
        }
        System.out.println(resultCount);
    }

    private static void add(char value) {
        switch (value) {
            case 'A':
                inputCheckArr[0]++;
                if (inputCheckArr[0] == checkArr[0]) checkCount++;
                break;

            case 'C':
                inputCheckArr[1]++;
                if (inputCheckArr[1] == checkArr[1]) checkCount++;
                break;

            case 'G':
                inputCheckArr[2]++;
                if (inputCheckArr[2] == checkArr[2]) checkCount++;
                break;

            case 'T':
                inputCheckArr[3]++;
                if (inputCheckArr[3] == checkArr[3]) checkCount++;
                break;
        }
    }

    private static void remove(char value) {
        switch (value) {
            case 'A':
                if (inputCheckArr[0] == checkArr[0]) checkCount--;
                inputCheckArr[0]--;
                break;

            case 'C':
                if (inputCheckArr[1] == checkArr[1]) checkCount--;
                inputCheckArr[1]--;
                break;

            case 'G':
                if (inputCheckArr[2] == checkArr[2]) checkCount--;
                inputCheckArr[2]--;
                break;

            case 'T':
                if (inputCheckArr[3] == checkArr[3]) checkCount--;
                inputCheckArr[3]--;
                break;
        }
    }
}

리뷰

슬라이딩 윈도우 알고리즘을 이용한 문제이다. 슬라이딩 윈도우는 투 포인터와 매우 유사하다. 오히려 같은 크기로 이동하다보니 조금 더 편한 것 같기도하다 😛

입력받은 문자열을 배열로받고 비밀번호 조건 배열과 매칭할 수 있게 입력 문자열 배열을 순차로돌며 비밀번호 조건 배열과 같은 순서로 각각의 자리에 카운트하여 조건을 만족하는지 판단하는 방식으로 구현하였다.

링크

코드

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[] numberArray = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberArray.length; i++) {
            numberArray[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        Arrays.sort(numberArray);

        int count = 0;
        for (int k = 0; k < numberArray.length; k++) {
            long findNumber = numberArray[k];
            int pointerI = 0;
            int pointerJ = numberArray.length - 1;
            while (pointerI < pointerJ) {
                if (numberArray[pointerI] + numberArray[pointerJ] == findNumber) {
                    if (pointerI != k && pointerJ != k) {
                        count++;
                        break;
                    } else if (pointerI == k) pointerI++;
                    else pointerJ--;

                } else if (numberArray[pointerI] + numberArray[pointerJ] > findNumber) pointerJ--;
                else pointerI++;
            }
        }
        System.out.println(count);
    }
}

리뷰

주어진 모든 입력에대해 좋은 수인지 판별해야하기 때문에 O(N^2)의 시간복잡도로 문제를 풀게되면 총 O(N^3)이 되어 실패하게된다.

다른 투포인터 문제와 방식은 동일하게 진행된다. 다만 유의해야 할점은 입력되는 수가 정수라는 점을 고려해야 한다.

만약 5가 좋은 수인지 확인하려는데 5와 0을 가리키면 5 + 0 = 5니까 좋은 수라고되면 안되기 때문에 우리가 좋은 수인지 찾을 때 그 숫자 자기자신이 계산에 포함되면 안되는 예외조건이 필요하다.

그래서 두 인덱스의 값의 합이 우리가 찾는 수 일 때 각각의 두 수가 그 수인지 확인하는 작업이 필요하다. 이 부분에서 실수를해서 시간초과가 되었는데 두 수가 찾는 수가 아닌지 판별하는 동시에 만약 가리키는 숫자가 찾는 수였으면 어떻게 해야할지 정해주어야한다. 까먹고 if문을 하나만 두었더니 거기에 갇혀서 나오지못해 시간초과 오류가 발생했다. 😨

링크

코드

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 M = Integer.parseInt(br.readLine());
        int[] serialArray = new int[N];

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

        int pointerI = 0;
        int pointerJ = serialArray.length - 1;
        int count = 0;
        while (pointerJ > pointerI) {
            if (serialArray[pointerI] + serialArray[pointerJ] == M) {
                count++;
                pointerI++;
                pointerJ--;
            } else if (serialArray[pointerI] + serialArray[pointerJ] > M) pointerJ--;
            else pointerI++;
        }
        System.out.println(count);
    }
}

리뷰

투포인터를 이용해 양 끝에서 시작해서 주어진 숫자의 합이 나오도록 포인터를 이동하여 count한다.

링크

코드

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

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 startIndex = 1;
        int endIndex = 1;
        int sum = 1;
        int count = 1;

        while (endIndex != N) {
            if (sum == N) {
                endIndex++;
                sum += endIndex;
                count++;
            } else if (sum > N) {
                sum -= startIndex;
                startIndex++;
            } else {
                endIndex++;
                sum += endIndex;
            }
        }
        System.out.println(count);
    }
}

리뷰

투 포인터 알고리즘을 이용한 문제풀이이다. N값의 범위가 최대 천만으로 O(N)의 시간복잡도를 가지는 방법으로 문제를 해결해야한다.

연속된 숫자의 합이 나타나는 가짓수를 구하는 문제로 startIndex와 endIndex 값을 이용해 배열을 순차적으로 진행하며 연속되는 숫자의 합이 주어진 숫자와 같아지는 경우 count한다.

생각보다 고급스러운? 알고리즘 이름에 어딘가 되게 단순해 보이는 코드이다.

아직은 알고리즘을 막 공부하기 시작해서 그런지 처음 백준, 프로그래머스 문제를 풀었었던 기분이 다시 느껴진다.

다양한 알고리즘을 배워나가는데에 설레기도 하는데 이 많은 애들을 다 이해하고 평소에 문제를 보면 이건 어떠한 알고리즘 문제로 풀면 되겠다 하는 느낌이 올 수 있나 싶은 불안감도 드는 것 같다 😬

링크

코드

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

public class Main {
    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());
        long[] sumArray = new long[N];
        long[] remainderArray = new long[M];
        long count = 0;

        st = new StringTokenizer(br.readLine());
        sumArray[0] = Integer.parseInt(st.nextToken());
        for (int i = 1; i < sumArray.length; i++) {
            sumArray[i] = sumArray[i - 1] + Integer.parseInt(st.nextToken());
        }

        for (long value : sumArray) {
            int remainder = (int) (value % M);

            if (remainder == 0) count++;
            remainderArray[remainder]++;
        }

        for (long value : remainderArray) {
            if (value > 1) count += (value * (value - 1)) / 2;
        }
        System.out.println(count);
    }
}

리뷰

인생 첫 골드문제이다 😤 이전에 풀었던 구간합 알고리즘을 활용하여 푸는 문제이다.

문제에서 원하는 결과는 무엇을 뜻하는 걸까? 배열의 구간합이 M으로 나누어 떨어지는 i, j쌍의 개수란

1 2 3 1 2 라는 값이 있을 때 어디서부터 어디까지 더하면 3으로 나누어 떨어질까? 1번부터 5번까지라고 가정하면

1번+2번, 1번+2번+3번, 1번+2번+3번+4번+5번, 2번+3번+4번, 3번, 3번+4번+5번, 4번+5번

이렇게 7가지나되는 구간이 나온다. (골드부터는 문제를 이해하는 것도 일인건가 😞)

여기서 곱셈공식처럼 한 가지 법칙이있다.

각 수의 나머지를 구하고 그 둘을 더해 다시 나머지를 구한 것과 각 수를 더하고 더한 수의 나머지를 구한 값은 같다는 것이다. 식만 봐서는 이해가 안가서 예시를 들어보면

1과 2가 있고 숫자 3으로 이를 나눈다고 생각해보자 1을 3으로 나눈 나머지는 1, 2를 3으로 나눈 나머지는 2이고 이 나머지들의 합은 1 + 2 = 3이다. 이 나머지의 합을 3으로 나눈 나머지는 0이다.

다음 방법인 1과 2를 우선 더하면 3이다. 이를 3으로 나눈 나머지는 0이다. 즉 나머지를 구하고 구하고 더하고 구하는 4번의 계산이 더하고 구하는 2번의 계산으로도 같은 결과를 얻는다.

이러한 특성을 이용하여 푸는게 이번 문제의 핵심이다. 즉 구간합 배열을 주어진 수로 나눈 나머지의 결과값을 저장한 배열을 이용하면 간단하게 문제를 해결할 수 있다.

나누는 수 : 3 1 2 3 1 2 - 입력 배열 1 3 6 7 9 - 구간합 배열 1 0 0 1 0 - 구간합을 주어진 수로 나눈 나머지배열

나머지 배열이 0인 곳은 구간합이 나누어 떨어진다는 것이므로 0의 갯수인 3개가 결과값에 포함된다.

그리고 기존의 구간합 원리를 생각해보면 같은 나머지 값을 가지는 칸의 구간의 나머지는 0이다. 무슨 말이냐면 1이 있는 1번과 4번의 값은 입력 배열에서 1과 1+2+3+1한 값이다 즉 4번에서 1번을 뺀 2 3 1 이 구간의 합을 3으로 나누게되면 0으로 나누어 떨어진다. 같은 나머지 값을 가지고 있다는 것은 두 구간의 사이가 결국 3으로 나누어 떨어지는 수의 차이만큼 벌어져있다는 소리이다.

글로 설명하는데 한계가 있어서 뭔가 확연하게 이해하기 쉬울 수는 없을 것이라 생각되서 이 영상을 추천한다. 나도 이 문제를 이해하는데 도움을 많이 받은 영상이다.

이제 그럼 결과인 7은 어떻게 나오는 것이냐면 나머지 배열의 0의 갯수 3 + 2개의 1에서 한 구간을 뽑는 경우의 수(2C2) + 3개의 0에서 한 구간을 뽑는 경우의 수 (3C2)로 결과값인 7이 도출된다.

링크

코드

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

public class Main {
    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[][] inputArray = new int[N + 1][N + 1];
        for (int i = 1; i < inputArray.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < inputArray[i].length; j++) {
                inputArray[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] sumArray = new int[N + 1][N + 1];
        for (int i = 1; i < sumArray.length; i++) {
            for (int j = 1; j < sumArray[i].length; j++) {
                sumArray[i][j] = sumArray[i][j - 1] + sumArray[i - 1][j] - sumArray[i - 1][j - 1] + inputArray[i][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            sb.append(sumArray[x2][y2] - sumArray[x1 - 1][y2] - sumArray[x2][y1 - 1] + sumArray[x1 -1][y1 - 1])
                    .append("\n");
        }
        br.close();
        System.out.print(sb);
    }
}

리뷰

이전에 풀었던 구간합 문제는 1차원배열이고 이번 문제는 2차원배열에서의 구간합 문제이다.

복잡해보이지만 원리는 동일하다. 처음 봤을 때는 이해가 안갔는데 그림으로 이해하는 편이 쉽게 이해할 수 있는 것 같다.

구간합 배열 작성하기

2차원배열의 구간합 배열을 구하기 위해서는

1차원배열에서 이전 인덱스의 구간의 합에 본인 자리에 입력받은 배열의 값을 더해주었듯이 같은 맥락으로 생각하면 된다.

같은 행에서 이전 인덱스의 구간합 값 + 같은 열에서 이전 인덱스의 구간합 값을 더하고 겹치는 부분을 빼주고 본인 자리의 입력받은 배열값을 더해주면 되는 것이다. sumArray[i][j] = sumArray[i][j - 1] + sumArray[i - 1][j] - sumArray[i - 1][j - 1] + inputArray[i][j];

구간합 배열을 이용한 구간 사이의 합 구하기

이전에 1차원배열에서의 i부터 j구간까지의 합을 구할 때 구간합 배열에서 처음부터 j까지의 구간합 즉 배열[j] 의 값에서 필요없는 처음부터 i - 1구간을 뺐던 것처럼 생각하면 간단하다.

이차원 배열에서는

이 구간의 합을 얻고싶으면

주황색 구간합(3, D) 값에서 빨간색 부분인 구간합(3,A)와 구간합(1,D)를 빼주고 빨간색 부분에서 유일하게 겹치는 구간합(1,A) 부분을 더해주면된다.

이 공식이 코드의 sumArray[x2][y2] - sumArray[x1 - 1][y2] - sumArray[x2][y1 - 1] + sumArray[x1 -1][y1 - 1] 이 부분인 것이다.

링크

코드

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

public class Main {
    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[] sumArray = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < sumArray.length; i++) {
            sumArray[i] = sumArray[i -1] + Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < M; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            sb.append(sumArray[j] - sumArray[i - 1]).append("\n");
        }
        br.close();
        System.out.print(sb);
    }
}

리뷰

문제를 어느정도 풀고나니 대부분 계산 등을 이용한 구현문제가 대부분이였고 요즘 알고리즘도 하나씩 공부해야 될 것 같아 누적합(구간합) 알고리즘에 대해 공부하며 문제를 풀어보았다.

문제를 얼핏보면 입력받은 수를 배열에 넣어놓고 i부터 j까지 그냥 배열에서 바로 더해서 출력하면 되는게 아닌가 싶지만 알고리즘 문제의 경우 평소에 우리가 빠르게 풀던 반복문을 그냥 돌리는 형태로는 시간 복잡도에 의해 실패가 되는 경우가 많다.

최악의 경우 배열이 100,000의 크기를 가지고 100,000개의 질의가 들어오면 100,000 * 100,000 = 100억 100억건의 연산으로 보통 1억당 1초로보니 100초가 걸려 문제의 조건인 1초를 훨씬 뛰어넘는 시간이다.

그런데 입력받은 배열의 구간별로 합을 저장한 배열을 만들게되면 질의 1건당 O(1)의 연산이 필요해 100,000건으로 여유롭게 시간 제한안에 들어가게된다. (시간 복잡도 개념이 아직 익숙하지 않아 위의 계산들이 틀릴 수 있다.)

결론은 시간초과를 막으려면 구간합 알고리즘을 사용해야한다는 결론이다.

구간합의 값은 구간합 배열의 이전 인덱스의 값 + 입력받은 배열의 현재 인덱스 값이다. (sumArray[i] = sumArray[i - 1] + array[i]) 반복문을 통해 입력받는 동시에 바로 구간합 배열을 만들어주고 입력을 통해 들어온 구간범위에 따른 값을 출력해주면된다.

구간합은 i부터 j의 범위공식은 summArray[j] - sumArray[i - 1]이다.

[0][0][X][X][X] 3부터 5의 구간 범위를 구하고 싶으면 [X][X][X][X][X] 1부터 5의 구간합에서 [X][X][O][O][O] 1부터 2의 구간합을 빼주면 구할 수 있는 것이다. 즉 sumArray[5] - sumArray[2]로 위의 공식과 동일하다.

링크

코드

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

public class Main {
    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());

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

        System.out.println(scores[scores.length - k]);
    }
}

리뷰

N명의 학생 중 k명이 상을 받고 상을 받은 사람 중 제일 낮은 성적을 구하는 문제이다.

즉, 정렬을 한 상태의 배열에서 상을 받는 사람들 중 첫번째 인덱스를 출력하면 된다.

링크

코드

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

public class Main {
    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());

        Integer[] coins = new Integer[N];
        for (int i = 0; i < coins.length; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(coins, Collections.reverseOrder());

        int count = 0;
        for (Integer coin : coins) {
            if (K >= coin) {
                count += K / coin;
                K %= coin;
            }
        }
        System.out.println(count);
    }
}

리뷰

동전 갯수의 최솟값을 구하기위해서는 동전의 리스트를 내림차순으로 정렬하여 큰 돈 부터 교환하게끔하여 구현한다.

링크

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int count = 0;

            for (int j = 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (((j * j) + (k * k) + m) % (j * k) == 0) count++;
                }
            }
            sb.append(count).append("\n");
        }
        br.close();
        System.out.print(sb);
    }
}

리뷰

(a^2 + b^2 + m) / (a * b) 가 정수가 된다는건 해당 식의 결과가 나머지가 없이 딱 나누어 떨어져야 된다는 것이다.

즉, (a^2 + b^2 + m) % (a * b) 가 0이여야 한다는 것이다. 구현은 브루트포스 문제답게 반복문을 이용하면 된다.

링크

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] scores = new int[5];

        for (int i = 0; i < scores.length; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(scores);

        StringBuilder sb = new StringBuilder();
        sb.append((int) (Arrays.stream(scores).average().getAsDouble())).append("\n");
        sb.append(scores[2]);
        System.out.print(sb);
    }
}

리뷰

성적을 5개 입력받고 평균점수와 중앙값을 출력하는 문제이다. 5개를 입력받으면서 바로 배열을 이용해 담아주고 정렬을 하면 매우 간단하게 중앙값을 구할 수 있다.

평균은 반복문으로 구해도되고 위의 풀이처럼 스트림을 이용해 평균을 구하는 방법이 있다.

시작하게 된 계기

회고라고 하기엔 정말 짧고 글을 안쓰기에는 뭔가 그래도 노력했는데 아쉬워서 남기는 글이다.

국비지원 과정을 수강하고있으면서 자바를 거쳐 스프링, 스프링 부트를 배워가는 중에 자바를 활용하는 점이 뭔가 아쉽게 느껴졌다.

어려운 기술을 쓰고싶다기보다는 뭔가 기본기를 사용하는데 생각하는데 걸리는 시간도 많고 다양한 해결 방법이 떠오르지 않았었다.

그래서 다른 공부를 하면서 코딩테스트 준비를 조금씩 하는게 어떨까 싶었다. (실제로 도움이 되는지는 잘 모르겠지만 😅 무작정 시작해본것 같다)

그렇다고해서 일전에 아예 문제를 안풀어본것은 아니고 자바를 배울 때 과제 형식으로 몇몇 문제를 풀었었는데 그 때는 당장 배운 것을 바로 활용하려니 잘 사용하지 못해서 오히려 약간의 자괴감이 드는 듯한 기분이여서 유쾌한 경험은 아니였던 것 같다.

어떻게 문제를 해결했나?

인터넷에 흔히 코딩테스트 문제라고 올라오는 DFS, BFS, ~탐색, 등 바로 푸는 것은 힘들 것이라 판단해서 자신감도 키울겸(?) 백준에서는 단계별로 문제풀이, 프로그래머스에서는 레벨 0의 문제를 풀어보기 시작했다.

일단 제목이 프로그래머스니까 프로그래머스 위주로 작성해보면 처음에는 간단한 출력문제들이 많아서 편하게 풀었는데 가끔씩 레벨 0문제가 맞는건가 싶은 문제도 있었다.

그래도 객관적으로 보면 많은 문제는 아니지면 내 기준에서 많은 문제를 풀어보고 어느정도 맞는 방식의 공부법을 얻을 수 있었던 것 같다.

문제랑 조건들을 보고 바로 떠오르는 경우에는 바로 풀고 바로 떠오르지 않는 경우에는 조금 생각하는 시간을 가져본다.

만약 떠오르는데 코드 작성이 힘들면은 그 떠오르는 메소드나 방식을 검색을 통해 사용법을 보고 코드를 작성해보는 식으로 진행했다. 그리고 도저히 못 풀 것 같은 문제는 다른 사람들의 풀이를 최대한 다양하게 보는 방식으로 진행했다. 언어가 다르더라도 일단 확인해보았다.

언어가 다르더라도 결국 비슷한 맥락으로 돌아가고 메서드나 일부 사용법이 살짝 다를 뿐이지 문제를 해결하는 매커니즘 자체는 비슷한 것 같았다.

문제를 해결하고나서도 위와 같은 맥락으로 다른 사람들의 풀이를 살펴보는 것이 중요하다고 생각한다. 그렇게해서 스트림이나 람다같은 생소한 것들도 사용해보면서 어느정도 익힐 수 있는 좋은 기회였다고 생각한다.

후기

후기라고 해야하나 아직까진 구현 위주의 문제만 풀어봤기에 자료구조나 알고리즘 등은 잘 모르지만 조금씩 지금처럼 꾸준히 도전해 볼 생각이다.

코딩테스트가 일종의 토익이라는 말처럼 실제 실무에서는 쓰기 애매한 경우도 있다고는 하지만 코드 작성의 경험을 늘리는데는 확실한 동기부여와 약간의 성취감을 주는 좋은 재료라고 생각한다. (이제 레벨 100문제 풀고 백준도 막 실버에 도착한 수준에 이런 말은 무모할 수 있지만 😁)

링크

코드

class Solution {
    public int solution(int[] common) {
        if (common[1] - common[0] == common[2] - common[1]) {
            return common[common.length - 1] + (common[1] - common[0]);
        }
        else return common[common.length -1] * (common[1] / common[0]);
    }
}

리뷰

등차수열인지 등비수열인지 판단해서 다음에 올 숫자를 출력하도록 한다.

등차수열은 앞의 항에 일정한 수를 더하여 얻어지는 수열 등비수열은 앞의 항에 일정한 수를 곱하여 얻어지는 수열 이렇게 구분할 수 있다.

그럼 이 둘을 어떻게 구분할까? 간단한건 등차수열인지 알아보면 된다. 일정한 수를 더하여 얻어지는 수열이라고 정의되어있듯이

첫 번째 인덱스와 두 번째 인덱스의 차이와 세 번째 인덱스와 두 번째 인덱스의 차이가 같다면 등차수열이다. 그러므로 자연스럽게 같지않으면 등비수열이되기 때문에

마지막 인덱스에 등차수열이면 차이값을 더해주고 등비수열이면 곱해주면 문제를 해결할 수 있다.

링크

코드

class Solution {
    public int[] solution(int num, int total) {
        int[] answer = new int[num];
        int middleValue = total / num;
        int startNumber = middleValue - ((total % num == 0) ? num / 2 : (num / 2) - 1);

        for (int i = 0; i < num; i++) {
            answer[i] = startNumber + i;
        }

        return answer;
    }
}

리뷰

링크

코드

class Solution {
    public int solution(int M, int N) {
        return (M * N) - 1;
    }
}

리뷰

공통되는 규칙이 있지만 뭔가 설명하기는 애매한 문제같다 😁 어떤 종이든 겹치지않게 1 X 1 형식으로 자른다. 가로 세로를 나누어서 생각해보자 만약 도화지가 2 X 5라면 우선 길이가 긴 세로인 5를 1칸씩 자른다고 생각하면 4번의 가위질을 하면 5개의 1이 나온다.

거기에 가로가 2이므로 5개를 한번씩 가위질하면 총 9번이 된다.

결국 종합하면 M X N 의 도화지의 경우 (M * N) - 1의 가위질을 하게된다.

링크

코드

풀이 1.

class Solution {
    public int solution(String A, String B) {
        int count = 0;

        String word = A;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A.length(); i++) {
            if (word.equals(B)) return count;
            sb.append(word.substring(word.length() - 1))
                    .append(word, 0, word.length() -1);
            word = sb.toString();
            sb.setLength(0);
            count++;
        }
        return -1;
    }
}

풀이 2.

class Solution {
    public int solution(String A, String B) {
        return (B + B).indexOf(A);
    }
}

리뷰

첫번째 풀이방식은 반복문을 돌며 substring()을 통해 단어의 맨뒤를 잘라 새로운 단어의 맨 앞에 붙이고 나머지 단어를 뒤에 이어붙혀 한 칸씩 이동하는 새로운 단어를 만들어주며 B와 같은 값이 나오는지 확인한다.

두번째 풀이방식은 풀고나서 보게된 풀이방법인데 이렇게 간단한 방법이 있을 줄은 생각못했다 😳

링크

코드

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

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

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for (int value : arr) {
            sb.append(value).append("\n");
        }
        System.out.print(sb);
    }
}

리뷰

입력받은 숫자를 오름차순으로 정렬하는 문제로 배열에 담아 정렬하면 간단하게 구현할 수 있다.