할 수 있다는 신념, 하면 된다는 생각

https://school.programmers.co.kr/learn/courses/30/lessons/136798

문제 풀이

핵심 Key point : 약수, number의 최대 크기 = 10^5

약수를 구하는 알고리즘과 이중 for문을 쓰되 최대한 시간복잡도가 낮은 방법을 채택하는 것이 관건이었다.

처음에 시간초과가 난 경우를 보자.

class Solution {
    public int solution(int number, int limit, int power) {
        int[] arr = new int[number];    //약수 개수를 담는 배열
        // arr에 약수 담기
        for(int i = 0; i < arr.length; i++) {
            for(int j = 1; j <= i+1; j++) {		// 문제발생!!!!!!!!!!!!!!!!!!!
                if((i+1) % j == 0)  arr[i] += 1;
            }
        }
        
        // limit 비교 및 sum 계산
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > limit) {
                arr[i] = power;
            }
            sum += arr[i];
        }
        return sum;
    }
}

이 코드는 테스트 케이스는 찾을 수 있지만, 실제 제출했을 때 시간초과가 난다. 최대 10^10번까지 계산해야 하기 때문이다.

그렇다면, 어느 부분에서 연산 횟수를 줄일 수 있을까? -> 바로 약수를 구하는 패러다임을 바꾸면 된다.

해당 링크의 방법을 사용하여 약수 구하는 과정을 최소화 시켰다.

https://www.geeksforgeeks.org/count-divisors-n-on13/

정답 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int[] arr = new int[number];    //약수 개수를 담는 배열
        // arr에 약수 담기
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            for(int j = 1; j <= Math.sqrt(i+1); j++) {
                if ((i+1) % j == 0) {
                    if((i+1) / j == j)  arr[i] += 1;
                    else    arr[i] += 2;
                }
            }
            if(arr[i] > limit)  arr[i] = power;
            sum += arr[i];
        }
        
        return sum;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/181892

1. 문제 설명

정수 리스트 num_list와 정수 n이 주어질 때, n 번째 원소부터 마지막 원소까지의 모든 원소를 담은 리스트를 return하도록 solution 함수를 완성해주세요.

2. 접근 방법

1. answer 배열의 크기가 num_list.length - n + 1 것을 파악한다.
2. num_list[n-1] 부터 num_list[n], num_list[n+1]의 수를 각각 answer[0], answer[1], answer[2] 이렇게 차례로 넣을 for 문을 만든다.

3. 코드

class Solution {
    public int[] solution(int[] num_list, int n) {
        int[] answer = new int[num_list.length - n + 1];
        
        for(int i = 0; i < answer.length; i++){
            answer[i] = num_list[n-1];
            n++;	// n을 1씩 증가시켜서 anser[i+1]에는 num_list[n]이 오도록 한다
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/181928

1. 문제 설명

정수가 담긴 리스트 num_list가 주어집니다. num_list의 홀수만 순서대로 이어 붙인 수와 짝수만 순서대로 이어 붙인 수의 합을 return하도록 solution 함수를 완성해주세요.

2. 접근 방법

1) 일단 if문으로 짝수, 홀수 나눠서 새로운 배열에 저장한다. 이떄, num_list에 있는 int 형을 String으로 변환하여 각각 짝수 문자열(even)과 홀수 문자열(odd)에 저장.

2) String으로 저장된 값을 Integer.parseInt()로 형변환 하여 두 배열의 합을 구한다.

class Solution {
    public int solution(int[] num_list) {
        int answer = 0;
        
        String even = "";
        String odd = "";
        
        for(int i = 0; i < num_list.length; i++){
            if(num_list[i] % 2 == 0){
                even = even + Integer.toString(num_list[i]);	//짝수 입력
            }
            else{
                odd = odd + Integer.toString(num_list[i]);		// 홀수 입력
            }
            
        }
        answer = Integer.parseInt(even) + Integer.parseInt(odd);
        return answer;
    }
}

3. 회고

처음에는 Integer 객체를 쓰지 않고 구현하려고 했다.  근데 너무 복잡하게 생각했던 나머지, 그냥 String으로 변환해서 풀기로 했다. 굳이 10의 제곱수를 만들기 위해 2중 for문을 안 만들어도 됐었는데.. 역시 알고리즘 풀 때는 간단하게 생각해야 하는 것 같다.

https://school.programmers.co.kr/learn/courses/30/lessons/181943

1. 문제 설명

 문자열 my_string, overwrite_string과 정수 s가 주어집니다. 문자열 my_string의 인덱스 s부터 overwrite_string의 길이만큼을 문자열 overwrite_string으로 바꾼 문자열을 return 하는 solution 함수를 작성해 주세요.

2. 접근 방법

1) 주어진 인덱스(s)까지의 문자열 + overwriting_string 으로 구현하면 된다.

2) 이때, overwriting_string 문자열을 붙인 후에도 my_string 문자열을 추가해야 하는 경우를 생각한다.

3) 그래서, sub_st_02 (아래 코드 참고)를 사용하여 뒤에 붙여준다.

class Solution {
    public String solution(String my_string, String overwrite_string, int s) {
        String answer = "";
        
        int my = my_string.length();	
        int over = overwrite_string.length();
        
        String sub_st_01 = my_string.substring(0, s);
        String sub_st_02 = my_string.substring((s+over), my);
        
        return answer = answer + sub_st_01 + overwrite_string + sub_st_02;
    }
}

3. 회고

- 처음에는 substring 메소드 없이 구현하려고 했다. 왜냐하면, Java를 잘 몰라서 substring가 있는지 조차 몰랐기 때문이다. 그래서 my_string의 길이 - index 값이 overwring된 문자열의 길이보다 큰지, 작은지, 같은지 케이스를 모두 구분하려고 했다.

 그런데 알고보니 제한사항에 그것에 대한 답이 있었던 것... 문제를 잘 읽고, 이해하는 연습부터 해야겠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/161990

[문제 설명]

코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다.....이하 생략

우선 알고리즘 문제를 풀면서, 내가 가장 중요하게 생각하는 건 '복잡하게 생각하지 말자'이다. 물론 복잡한 알고리즘 문제도 있지만, 되려 복잡하게 생각하여 단순한 문제를 어렵게 접근하는 경우가 많았기 때문이다.

1. 주어진 wallpaper 배열의 length는 행(row)를, wallpaper 배열의 원소의 길이는 열(col)을 나타낸다.

 문제 특성상, String[] wallpaper의 원소 길이는 모두 같기 때문에 wallpaper[0]을 임의로 잡았다. 그리고 #이 존재하는 위치의 행과 열의 최소값과 최대값의 유무가 문제를 푸는데 키워드라는 것을 인지한다.

2. #이 들어가는 (최소 행, 최소 열), (최대 행 + 1, 최대 열 + 1)을 구한다.  

class Solution {
    public int[] solution(String[] wallpaper) {
        int minCol, maxCol;
        int minRow, maxRow;

        int row = wallpaper.length;
        int col = wallpaper[0].length();    //배열의 원소 길이는 같기에 wallpaper[0] 임의로 지정

        minCol = minRow = Integer.MAX_VALUE;
        maxCol = maxRow = Integer.MIN_VALUE;

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(wallpaper[i].charAt(j) == '#'){
                    minRow = Math.min(minRow, i);
                    maxRow = Math.max(maxRow, i);
                    minCol = Math.min(minCol, j);
                    maxCol = Math.max(maxCol, j);
                }
            }
        }

        return new int[]{minRow, minCol, maxRow + 1, maxCol + 1};
    }
}

프로그래머스에서 문제를 풀다가 오름차순으로 정렬할 알고리즘이 있었다.

2중 for문에 익숙한 나는, 2중 for문으로만 하려고 했는데 알고리즘을 공부하기 위해선 다양한 방법을 시도해야 했다.

그래서 Arrays.sort() 메쏘드를 사용했다.

1. 2중 for문을 사용한 오름차순 정렬

import java.util.*;

public class HelloJava {
    public static void main(String args[]) {
        
        int[] a = new int[]{1,5,4,3,2};
        int k;

        for(int i = 0; i < a.length - 1; i++){
            for(int j = i + 1; j < a.length; j++){
                if(a[i] > a[j]){
                    k = a[i];
                    a[i] = a[j];
                    a[j] = k;       
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

2. Arrays.sort()를 사용하여 오름차순 정렬

import java.util.*;

public class HelloJava {
    public static void main(String args[]) {
        
        int[] a = new int[]{1,5,4,3,2};
        
       	Arrays.sort(a);
        
        System.out.println(Arrays.toString(a));
    }
}

여기서 만약에

System.out.println(a);

로 값을 출력한다면 [I@24d46ca6 와 같은 배열 a의 주소값이 나올 것이다.

배열은 참조변수이므로, 배열의 원소값을 나타내기 위해서는 toString 메소드를 사용한다면 파라미터를 통해 원소 값을 문자열로 변환 후, 원소를 출력할 수 있다.

개발 공부를 꾸준히 해야하는데... 계속 달렸다가 멈췄다가 무한반복 굴레에 빠졌다!!

얼른 악순환을 끊고 다시 공부해야지!

<2020 카카오 인턴십 코딩테스트 문제 - 키패드 누르기>

class Solution {
    //        0부터 9까지 좌표 {y,x}
    int[][] numpadPos = {
            {3,1}, //0
            {0,0}, //1
            {0,1}, //2
            {0,2}, //3
            {1,0}, //4
            {1,1}, //5
            {1,2}, //6
            {2,0}, //7
            {2,1}, //8
            {2,2}  //9
    };
    //초기 위치
    int[] leftPos = {3,0};
    int[] rightPos = {3,2};
    String hand;
    public static void main(String[] args){
        
    }
    public String solution(int[] numbers, String hand) {
        this.hand = (hand.equals("right")) ? "R" : "L";

        String answer = "";
        for (int num : numbers) {
            String Umji = pushNumber(num);
            answer += Umji;

            if(Umji.equals("L")) {leftPos = numpadPos[num]; continue;}
            if(Umji.equals("R")) {rightPos = numpadPos[num]; continue;}
        }
        return answer;
    }

    //num버튼을 누를 때 어디 손을 사용하는가
    private String pushNumber(int num) {
        if(num==1 || num==4 || num==7) return "L";
        if(num==3 || num==6 || num==9) return "R";

        // 2,5,8,0 일때 어디 손가락이 가까운가
        if(getDist(leftPos, num) > getDist(rightPos, num)) return "R";
        if(getDist(leftPos, num) < getDist(rightPos, num)) return "L";

        //같으면 손잡이
        return this.hand;
    }

    //해당 위치와 번호 위치의 거리
    private int getDist(int[] pos, int num) {
        return Math.abs(pos[0]-numpadPos[num][0]) + Math.abs(pos[1]-numpadPos[num][1]);
    }
}

사실 클론 코딩이나 다름없다. 왜냐하면 프로그래머스에 있는 답을 보고 그대로 따라적었으니까..!

그래도 클론 코딩하면서 모르는 부분이 있어서 몇 가지 찾아봤다

자바에서 "?" 연산자가 뭐였더라..?

헐.. 알고리즘 공부를 안하니까 연산자 조차 까먹은 것이다!

다시 찾아보니 if/else 관계를 나타낼 때 쓰는 연산자였다

예를 들면 이렇다

import java.util.*;

public class Pratice {
    public static void main(String[] args){
        int[] array = {1,2,3,5,6};

        for(int i = 0; i < array.length; i++){
            System.out.println(array[i] + "는" + (array[i] % 2 == 0 ? "짝수" : "홀수"));
            // ?를 사용하여 if/else의 문장을 확 줄였다!
        }
    }
}

출력 결과는

1는홀수
2는짝수
3는홀수
5는홀수
6는짝수

코딩 공부는 꾸준히 하자... 요즘엔 초등학생도 코딩하던데.. 대학생이 되어서야 시작한 나는 계속 달려야 한다