search

enoch012 / JavaBasicStudy

Java 기초 스터디 (2023.09 ~ 10)
0 stars 1 forks source link

11월 16일 / 코딩 테스트 연습 (jaeyeon) #44

Open jaeyyyyy opened 11 months ago

jaeyyyyy commented 11 months ago

문제 1

문제

최대공약수와 최소공배수(https://school.programmers.co.kr/learn/courses/30/lessons/12940)

입출력 예

n m return
3 12 [3, 12]
2 5 [1, 10]

입출력 예 1

입출력 예 2

문제 풀이

어떻게 구해야할지 막연해서 찾아봤다..

방법 1. 1부터 n까지, 그리고 1부터 m까지 자연수 중 하나를 a라고 한다면, n과 m을 a로 나눈 나머지가 0이어야 a가 최대공약수가된다. 최소공배수는 n과 m을 곱한 값을 최대공약수로 나누면 된다.

for문을 사용해서 i가 1부터 n까지 그리고 1부터 m까지 두 가지 조건을 모두 만족하도록 했다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        for(int i = 1; i <= n && i <= m; i++) {
            if(n % i == 0 && m % i == 0) {
                answer[0] = i; // 최대공약수
                answer[1] = (n * m) / answer[0]; // 최소공배수
            }
        }

        return answer;
    }
}

방법 2. 유클리드 호제법을 이용한다. 이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구하는 방식이다.

최대공약수(Greatest Common Divisor, GCD)

class Solution {
    public int getGCD(int small, int big) {
        if(big % small == 0) { // 큰 수를 작은 수로 나눈 나머지가 0이면
            return small; // 작은 수를 반환
        } else return getGCD(big % small, small);
          // 아니라면 큰 수를 작은 수로 나눈 나머지와 작은 수를 계속해서 넣음
    }

    public int[] solution(int n, int m) {
        int gcd = getGCD(Math.min(n,m), Math.max(n,m)); // getGCD(작은수, 큰수)

        return new int[] {gcd, (n * m) / gcd}; 
    }
}

방법 3. 자바의 BigInteger 내장함수를 사용한다. 자바에서는 BigInteger 클래스에 최대공약수를 구할 수 있는 gcd() 메서드를 제공한다.

import java.math.BigInteger;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        BigInteger b1 = BigInteger.valueOf(n); //BigInteger로 n 값 넣기
        BigInteger b2 = BigInteger.valueOf(m); // BigInteger로 m 값 넣기
        BigInteger gcd = b1.gcd(b2);
        answer[0] = gcd.intValue();
        answer[1] = (n*m)/answer[0];

        return answer;
    }
}

회고

문제를 푸는 데 정말 많은 방법이 있다는 걸 새삼 깨달았던 문제. 그러나 그 방법을 생각해내는 게 어려웠다. 한 번만 풀어보는 걸로는 기억에 남지 않을테니 최대한 많이 보고 정리해봐야겠다...

jaeyyyyy commented 11 months ago

문제 2

문제

행렬의 덧셈(https://school.programmers.co.kr/learn/courses/30/lessons/12950)

입출력 예

arr1 arr2 return
[[1,2],[2,3]] [[3,4],[5,6]] [[4,6],[7,9]]
[[1],[2]] [[3],[4]] [[4],[6]]

문제 풀이

2차원 배열을 이용해야하는 문제다. 2차원 배열을 사용해서 문제를 풀어본 적이 있지만 오랜만에 보니 헷갈려서 기록한다. 2CCCCCC 2차원 배열의 대략적인 모습은 위 그림과 같다.(3행 5열의 2차원 배열) 2차원 배열은 아래처럼 선언할 수 있다.

int[][] = new int [n][m]; // n은 행, m은 열

입출력예 에서 주어진 arr1은 [[1,2],[2,3]]이므로 2행 2열이다. arr2은 [[1],[2]]이므로 2행 1열이다.

 int[][] arr1 = new int [2][2]; 
arr1 = {{1,2},
        {2,3}};

int[][] arr2 = new int[][];
arr2 = {{1},
        {2}};

arr1과 arr2의 행과 열의 길이는 고정되어 있지 않다. 2차원 배열에서 행과 열의 길이를 구하는 방법은 다음과 같다. 행의 길이 : 배열의 길이와 같다. 열의 길이 : 각 행마다 들어있는 열의 갯수가 다르다면(가변길이배열) 각 행의 길이, 각 행 별 원소의 길이를 구해야한다. 이 문제의 경우 가변배열이 아니므로 arr1[0].length이 arr1배열의 열의 길이가 된다. (0부터 마지막 행까지의 숫자를 넣어도 똑같다는 뜻)

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int row = arr1.length; // 행
        int column = arr1[0].length; // 열
        int[][] answer = new int[row][column]; //answer은 arr1이나 arr2과 같은 크기

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < column; j++) {
                answer[i][j] = arr1[i][j] + arr2[i][j];
            }    
        }

        return answer;
    }
}

회고

제대로 작성했는데 이중반복문에 같은 변수명을 적는 바람에 계속 오류가 났던 문제.. 이중반복문을 작성할 때는 다른 변수명으로 제대로 적자.

이제까지 뭐가 행인지 뭐가 열인지 모르고 걍 살아왔는데(비설 오픈) 더 이상 그렇게 살 수 없게 됨 모르면 배열 문제는 죄다 못 풀게 된다.. 지금이라도 외워라.

jaeyyyyy commented 11 months ago

문제 3

문제

같은 숫자는 싫어(https://school.programmers.co.kr/learn/courses/30/lessons/12906) 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

입출력 예

arr answer
[1,1,3,3,0,1,1] [1,3,0,1]
[4,4,4,3,3] [4,3]

문제 풀이

처음에 아래처럼 작성했는데 틀려서 다시 보니 붙어있는 중복 원소들을 제거하는 것이었다.. 

import java.util.Arrays;
import java.util.LinkedHashSet;

public class Solution {
    public int[] solution(int []arr) {
    // Integer를 담는 LinkedHashSet 선언
        LinkedHashSet<Integer> linkedhashSet = new LinkedHashSet<>();
        for(int n : arr) { // for문을 돌면서 arr의 원소를 linkedhashSet에 추가
            linkedhashSet.add(n);
        }
        int[] answer = new int[linkedhashSet.size()]; // linkedhashSet의 길이만큼 answer 배열 생성
        int index = 0; // 인덱스
        for(int n: linkedhashSet) {
            answer[index++] = n; // linkedhashSet의 값을 answer 배열에 넣음
        }

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println(Arrays.toString(answer));

        return answer;
    }
}

이렇게 작성하면 모든 중복 원소들을 제거하게 된다. 문제 카테고리가 스택이니 스택을 사용해보자.. 스택은 맨 마지막에 추가된 요소가 먼저 꺼내지는 구조다.

스택 관련 메서드

스택에 값을 하나씩 넣되, 스택의 최상단 값이 arr[i]와 동일하다면 스택에 값을 추가하지 않고, 동일하지 않은 경우(즉, 중복값이 아닌 경우에만) 스택에 값을 추가한다.

import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public int[] solution(int []arr) {
        // Integer를 담는 Stack 선언
        Stack<Integer> stack = new Stack<>();
        // arr의 길이만큼 반복문을 돌면서
        for(int i =0; i < arr.length; i++) {
            // 배열 첫번째 숫자를 stack에 넣고
            if(i == 0){
                stack.push(arr[i]);
            // 인덱스 1부터는 stack의 최상단 값이 arr[i]의 값과 일치하지 않을 경우에만 stack에 해당 값 push
            } else if (stack.peek() != arr[i]) {
                stack.push(arr[i]);
            }        
        }
        // stack의 사이즈만큼 answer 배열 생성
        int[] answer = new int[stack.size()];
        // 스택은 제일 나중에 추가한 값부터 꺼낼 수 있으므로 i값을 마이너스 해가며 뽑는다.
        for(int i = stack.size()-1; i>=0; i--) { 
            answer[i] = stack.pop();
        }

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println(Arrays.toString(answer));

        return answer;
    }
}

회고

스택...어렵다... 많이 써봐야겠다. 아직 감이 안 잡힌다