항해 99 - 2023.01.28 TIL

오늘도 전 날에 이어서 알고리즘 문제풀이를 계속 진행했다.

 

 

정수 제곱근 판별

임의의 정수를 제곱근 처리하여, 1을 더하여 제곱했을 때 정수인지 판별하는 문제이다.

class Solution {
    public long solution(long n) {
        double x = Math.sqrt(n);
        if(Math.pow(x,2)==n){
            return (long)(Math.pow(x+1,2));
        }else{
            return -1;
        }
    }
}

Math 클래스의 제곱 관련 함수를 사용했다. 

 

Math.pow(수, 제곱횟수) - 지정된 횟수로 제곱하여 double 타입으로 반환한다.

Math.sqrt(수) - 수의 제곱근 값을 double 타입으로 반환한다.

 

 

 

제일 작은 수 제거하기

주어지는 배열에서 가장 작은 수를 뽑아내어 반환하는 문제이다.

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

class Solution {
    int min = 0;
    public int[] solution(int[] arr) {
        int[] answer = {};
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(arr.length > 1){
            int[] clone = arr.clone();
            Arrays.sort(clone);
            min = clone[0];
            int length = arr.length;
            for (int i = 0; i < arr.length; i++) {
                if(arr[i]==min){
                    length--;
                    continue;
                }
                list.add(arr[i]);
            }
            answer = new int[length];
            for(int i = 0; i < length; i++){
                answer[i] = list.get(i);
            }

        }else{
            answer = new int[]{-1};
        }
        return answer;
    }
}

최솟값을 어떻게 뽑아내면 좋을지 고민했는데, 결과값이 들어갈 배열의 길이를 어떻게 구할지 고민했던 문제이다.

배열의 값은 변경할 수 없기 때문에, 임의로 배열 하나를 복제하여 sort하고, 첫번째 값을 최소값으로 지정했다. 이후 list에 최솟값을 제외한 수를 순서대로 담아주었는데, 최솟값에 해당하는 경우에는 결과가 들어갈 answer 배열의 길이를 1씩 차감하도록 했다. (최솟 값이 여러 개일 경우 대비)

 

배열의 값을 다뤄야하는 경우, 배열은 한번 선언하면 변경할 수 없다는 특징 때문에 ArrayList로 받아와 사용하는 것이 편한 것 같다. 

 

 

 

콜라츠 추측

주어진 숫자를 짝수일 때 나누기 2, 홀수 일때 곱하기3 더하기1 하여 1이 나올 때까지의 횟수를 구하는 문제이다.

class Solution {
        public int solution(int num) {
            int answer = 0;
            long lnum = (long)num;
            while (lnum != 1) {
                ++answer;
                if(lnum % 2 ==0){
                    lnum = lnum / 2;
                }else{
                    lnum = lnum * 3 + 1 ;
                }
                if(answer > 500){
                    return -1;
                }
                System.out.print("num : " + lnum);
                System.out.println("횟수 : " + answer);
            }
            return answer;
        }
}

구현은 쉽게 되었는데, 원하는 결과값이 나오지 않았다. int 타입으로 계산을 진행해서, 자릿수가 초과하는 숫자를 다루게 되었을 때 값손실이 일어난 듯 했다. long타입으로 바꿔 계산을 진행하니 정상적으로 결과가 출력되었다.

 

 

 

하샤드 수

주어지는 정수 x가 x 자릿수의 합으로 나누어지면 하샤드 수라고 한다. 이를 판별하는 문제이다.

 

class Solution {
    public boolean solution(int x) {
        boolean answer = true;
        String s = x + "";
        String[] strArr = s.split("");
        int hap = 0;
        for(String s2 : strArr){
            hap += Integer.parseInt(s2);
        }
        if(x%hap!=0){
            answer = false;
        }
        return answer;
    }
}

int를 한글자씩 쪼개어 더하고, x에 나누어 주었다. 간단한 문제이다.

 

 

 

3진법 뒤집기

자연수를 3진수로 변환하여 뒤집고, 다시 자연수로 바꾸는 문제이다.

class Solution {
    public int solution(int n) {
        StringBuffer str = new StringBuffer();
        String ternaryStr = Integer.toString(n,3);
        str = str.append(ternaryStr).reverse();
        ternaryStr = str.toString();
        return Integer.parseInt(ternaryStr,3);
    }
}

문자열을 뒤집는 reverse 메소드를 사용하기 위해서 StringBuffer를 사용했다.

 

Integer.toString(int, radix) - 10진수 에서 n진수 String으로의 변환

Integer.parseInt(Str, radix) - n진수 String에서 10진수로의 변환

 

 

 

최소직사각형

2차원 배열로 주어지는 값들을 가로, 세로 값이라고 가정하고, 가로 세로 값이 모두 들어갈 수 있는 수를 산출하는 문제이다.

class Solution {
    public int solution(int[][] sizes) {
        //큰 값을 가로로, 작은 값을 세로로 고정시킨다.
        int maxlen = 0;
        int minlen = 0;
        int big = 0;
        int small = 0;
        for (int i = 0; i < sizes.length; i++) {
            maxlen = sizes[i][0];
            minlen = sizes[i][1];

            if (maxlen < minlen) {
                // 세로가 더 클 경우 가로로 바꿔준다.
                int tmp = maxlen;
                maxlen = minlen;
                minlen = tmp;
            }

            if (big < maxlen) {
                //가로 중 젤 긴 길이
                big = maxlen;
            }
            if (small < minlen) {
                //세로 중 젤 긴 길이
                small = minlen;
            }
        }
        return big * small;
    }
}

처음에 문제를 어떻게 풀어나가면 좋을지 막막했는데, 힌트를 하나 얻을 수 있어서 방향을 잡을 수 있었다. 지정된 가로 세로 값을 비교하여, 더 긴 것을 가로로 고정시켜주고, 가로 중에 가장 긴 값, 세로 중의 가장 긴 값을 구하였다.

 

알고리즘 문제를 풀면서 느낀 바로는 도형 문제가 나왔을 때 이해가 잘 되지 않고 어렵게 느껴지는 것 같다. 도형 문제가 나왔을 때 괜히 위축되지 않도록 많은 문제를 접해보아야겠다.

 

 

 

같은 숫자는 싫어

주어진 배열 안의 요소에 연속된 값이 있을 경우, 삭제하는 문제이다.

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

public class Solution {
    public int[] solution(int []arr) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0; i < arr.length-1; i++){
            if(arr[i]!=arr[i+1]){
                list.add(arr[i]);
            }
            if(i==arr.length-2){
                list.add(arr[arr.length-1]);
            }
        }
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

값을 비교하여 삭제하는 것까지는 좋았는데, 배열 인덱스 범위가 벗어나서 에러가 발생했다. 배열의 끝에서는 조건문을 추가하여 list에 추가할 수 있도록 했다.

 

 

 

두 개 뽑아서 더하기

배열 안의 값을 한개씩 더해서 나올 수 있는 수를 반환하는 문제이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int[] solution(int[] numbers) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < numbers.length; i++) {
            int tmp = numbers[i];
            for (int j = 0; j < numbers.length; j++) {
                if(i==j){
                    continue;
                }
                if(!(list.contains(tmp + numbers[j]))){
                    System.out.println(tmp + numbers[j]);
                    list.add(tmp + numbers[j]);
                }
            }
        }
        Collections.sort(list);
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

구구단 예제를 떠올리면서 구현해보았는데, 배열의 같은 요소끼리 더할 일은 없으므로 조건문으로 예외 처리를 해주었다.

list에 요소끼리 더한 값이 존재하지 않을 경우 추가하는 방식으로 구현했다.

 

Collections.sort(list) - list의 정렬

 

 

 

로또의 최고 순위와 최저 순위

문제 지문이 너무 길어서 당황했던 문제였다. 주어지는 로또 번호에 0이 존재하는데, 당첨 번호와 비교했을 때 몇 개가 맞는지 0을 포함시켜 최대 순위를 구하고, 0을 제외한 숫자로 비교하여 몇 개가 맞는지 최저 순위를 구하는 문제이다.

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

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        ArrayList<Integer> winList = new ArrayList<>();
        for (int i : win_nums){
            winList.add(i);
        }
        int maxRank = 0;
        int minRank = 0;
        int cnt = 0;
        int zero = 0;
        for (int i = 0; i < lottos.length; i++) {
            if(winList.contains(lottos[i])){
                cnt++;
            }
            if(lottos[i]==0){
                zero++;
            }
        }
        maxRank = cnt + zero == 6 ? 1 :
                (cnt + zero == 5) ? 2 : (cnt + zero == 4) ? 3 : (cnt + zero == 3) ? 4 : (cnt + zero == 2) ? 5 : 6;
        minRank = cnt == 6 ? 1 :
                (cnt == 5) ? 2 : (cnt == 4) ? 3 : (cnt == 3) ? 4 : (cnt == 2) ? 5 : 6;

        int[] answer = {maxRank, minRank};
        return answer;
    }
}

당첨 숫자를 담기위한 cnt와 주어진 로또 번호의 0의 갯수를 담을 zero를 선언해주었다.

cnt와 zero를 더한 수를 최대 갯수로, 최저 갯수는 cnt로 할당하여 삼항 연산자를 이용해 순위를 산출했다.

 

 

 

문자열 내 마음대로 정렬하기

주어지는 문자열 배열의 요소 중에, n번째 글자를 기준으로 정렬하는 문제이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = new String[strings.length];
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < strings.length; i++) {
            list.add((strings[i].charAt(n)+"")+strings[i]);
        }
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i).substring(1,list.get(i).length());
        }
        return answer;
    }
}

list로 문자열 앞에다가 n번째 문자를 추가해준 뒤에 정렬을 진행하고, 이후에 각 문자열의 첫번째 글자를 삭제하여 answer 배열에 담아주었다.

 

 

 

느낀 점

어제 풀었던 문제보다 덜 막막하게 느껴지고 어느정도 방향을 잡을 수 있게 된 것 같다. 형변환이나 배열의 요소들을 조작해야할 때 List와 내장 함수들을 보다 잘 활용할 수 있게된 것 같다.

오늘 풀지 못했던 문제가 있는데, '모의고사' 라는 문제이다. 다음 주에 팀원들과 상의해 볼 예정이다.

 

알고리즘 시험에 풀었던 문제를 설명하는 영상을 제작하여 업로드하는 것도 포함이 되어있다고 한다. 

오늘은 페어 프로그래밍을 진행하지 않았는데, 다음 주에는 페어 프로그래밍 연습을 필히 진행해보아야겠다.