냥냥개발펀치

소수 구하는 문제는 자주 나오기 때문에 익혀두면 편하다. 소수 구하는 방법으로는

1. for문으로 N까지 확인하여 구하기

2. for문으로 sqrt(N)까지 확인하여 구하기

3. 에라토스테네스의 체 이용하여 구하기

이렇게 총 3가지로 크게 나뉜다.

3가지 방법 중에서 가장 효율적인 에라토스테네스의 체를 이용하여 문제를 해결했다.

처음 내가 작성하여 맞은 코드다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        boolean[] isNotPrime = new boolean[10001];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for(int i = 2;i<Math.sqrt(N);i++) {
            for(int j = i*i; j< N + 1; j = j+i){
                isNotPrime[j] = true; // 소수가 아님
            }
        }

        int sum = 0;
        int min = 0;
        for(int i = M;i<N+1;i++) {
            if(min == 0) {
                if(!isNotPrime[i]){
                    sum += i;
                    min = i;
                }
            }else {
                if(!isNotPrime[i]){
                    sum += i;
                }
            }
        }

        if(sum == 0){
            System.out.println(-1);
        }else {
            System.out.println(sum);
            System.out.println(min);
        }
    }
}

M과 N 사이의 소수를 구하는 문제라 범위가 정해져 있지만, 에라토스테네스의 체를 이용하면 처음부터 N까지 소수를 구한 뒤 합계와 최솟값을 구해도 전혀 문제가 없다. 사실 주어진 범위 내의 수들만 체크해서 소수를 구해야하는 거 아닌가 라는 생각에 고민에 조금 빠졌었는데, 오히려 중간부터 구할려니 소수인지 아닌지 추가적으로 나머지값을 통해 반복문을 가지고 또 판별해줘야해서 오히려 더 비효율적이다.

위 코드를 클린 코드로 다시 짜보았다.

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

public class Main {

    public static boolean[] isNotPrime = new boolean[10001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        isCheckPrime(N); 

        int sum = getSum(M,N);
        int min = getMin(M,N);

        printSumAndMin(sum, min);

    }

    public static void isCheckPrime(int end) {
        for(int i = 2;i<Math.sqrt(end);i++) {
            for(int j = i*i; j< end + 1; j = j+i){
                isNotPrime[j] = true; // 소수가 아님
            }
        }
    }

    public static int getSum(int start, int end) {
        int sum = 0;

        for(int i = start;i<end+1;i++) {
            if(!isNotPrime[i]){
                sum += i;
            }
        }

        return sum;
    }

    public static int getMin(int start, int end) {
        int min = 0;
        for(int i = start; i < end+1; i++) {
            if(!isNotPrime[i]) {
                min = i;
                break;
            }
        }

        return min;
    }

    public static void printSumAndMin(int sum, int min) {

        if(sum == 0){
            System.out.println(-1);
        }else {
            System.out.println(sum);
            System.out.println(min);
        }

    }
}

기능마다 함수로 구현해 함수는 하나의 기능만을 수행할 수 있도록 하고, 매개인자나 함수명도 누가봐도 어떤 걸 의미하는지 알 수 있도록 지었다. 확실히 이렇게 클린 코드로 정리하니까 한 눈에 들어와 이해하기도 쉽고 효율적인 것 같다.

아래 제출이 첫번째 작성한 코드이고 위 제출이 클린 코드이다. 클린 코드로 작성한 코드가 더 긴데도 불구하고 메모리와 시간은 얼마 차이 안나긴 하지만 더 적게 든다. 이건 단순 알고리즘 문제라 성능 차이가 크게 나지 않지만 실제로 프로그램을 구현하거나 큰 규모의 작업을 진행할 땐 어마어마한 차이를 보일 거 같다. 앞으로 알고리즘 문제를 풀 때도 이렇게 클린 코드로 작성하는 훈련을 계속해야겠다.

깃허브를 관리하기로 마음먹었다.....

계속 해야지, 해야지 생각만 하다가 드디어 실행으로 옮겼다ㅜㅜ 너무 늦게 시작한 감이 없지않아 있지만

지금부터라도 열심히 관리할거다!!!!

다시 관리하려고 마음을 먹으니, 깃 명령어도 많이 까먹었고해서 내가 헤맸던 부분만 명령어 위주로 먼저 정리해두려 한다.

git bash 실행(로컬 저장소 파일에서)

git init  git repository를 초기화? 즉 로딩, 준비하는 명령어라 생각하면 된다.

git config --global user.name ******  매번 푸쉬할때마다 로그인하기 귀찮기 때문에 이렇게 먼저 등록해준다.

git config --global user.email ********@*******

git status   현재 파일들의 상태를 보여주는 명령어

git add 파일명(폴더 전체를 올리고 싶다면 '폴더명/' 이렇게 해주면 된다) 커밋하고 싶은 파일만 골라서 가상공간에 추가해놓는 명령어!!! 

git commit -m "~~~~~" 추가(add) 해놓은 파일을 메시지와 함께 커밋하는 명령어

git branch -M main main은 푸쉬하고 싶은 브랜치 이름이고, 원하는 브랜치를 설정하는 명령어

git remote add origin https://~~~~~~~~~~~~~~~~ 내 깃허브 레포지토리의 주소를 origin이라는 별명으로 원격저장소에 추가해놓는 명령어

git push origin main origin이라는 별명으로 설정한 main 브랜치에 푸쉬하는 명령어

만약 여기서 오류가 난다면!!!! -> 보통 깃, 즉 원격저장소의 상태와 지금 내 로컬 상태가 일치하지 않아서 발생하는 오류가 대부분이다. 이때 pull이라는 명령어로 원격저장소와 로컬저장소의 상태를 동일하게 만들어준다.

git pull origin main

git push -u origin main

이렇게 해도 오류가 난다면 다음과 같이 강제로 원격저장소에 있던 내용을 삭제하고 지금 add 해둔 파일들만 새로 push할 수 있다.

git push -u origin +main

ㅋㅋ.. 이 문제 어려웠다..!! 이틀 내내 까진 아니지만 고민해서 풀었는데 에러나서 분명 어딘가 문제인데 그걸 어떻게 해결해야할지 몰라서 이 문제는 다른 풀이를 봐버렸다...

다른 풀이를 보니까 현타*2222222222222배 와버림. 확실히 난 아직 많이 부족하다. 알고리즘 문제 푸는 감이 부족하다 해야하나. 아니면 그냥 못 푸는 걸까.

처음에 방향을 아예 잘못 잡았다. 아, 아예 잘못된 방향인 걸 알았을 때 다 지우고 새로운 방법으로 풀면 되는데 혹시나 내가 푼 방법이 맞지 않을까라는 생각에 검색해보았다...^^ (한심ㅎ) 앞으론 아예 잘못된 거 같을 땐 처음부터 다시 풀자..^^

문제 조건에 처음 출발과 도착 직전엔 무조건 1만 이동한다고 나와있다. 이 조건을 잘못 사용한 거 같다. 어차피 1로 동일하니까 아예 구해야하는 거리에서 -2를 해버리고 남은 거리를 계산하려고 했다.

문제에 2번 째 조건으로 직전 이동한 거리-1, +0, +1 거리 중에서만 선택해서 이동할 수 있다는 조건이 있다. 이 조건에서도 선택한 직전 거리랑 앞으로 선택할 거리도 따져줘야 하고 해서 조건 판별해 구해야겠다 라고 생각했다. 최단 횟수를 구하는 문제이니 가장 큰 거리부터 선택해 구하면 되겠다라고 생각해 스택을 이용해 풀었는데 예제 테스트 케이스는 통과했지만 채점에서 에러가 나서 해결못했다. 로직에 분명한 오류가 있다. 근데 그 오류를 일일이 하나하나 다 따져서 해주기엔 코드가 너무 복잡해질 거 같다는 생각을 했다.

다음은 내가 작성한 코드이다.

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

public class Main {

    public static int restDistance;
    public static int count = 2;
    public static Stack<Integer> stack;
    public static int selectedNum = 0;

    public static void main(String[] args) throws IOException {

        stack = new Stack<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            restDistance = (y-x) - 2;

            stack.push(0);
            stack.push(1);
            stack.push(2);

            while(true) {

                if(restDistance == 0){
                    break;
                }
                int n = stack.pop();
                if(isRight(n)) {
                    if(restDistance == 0){
                        break;
                    }
                    stack.push(selectedNum-1);
                    stack.push(selectedNum);
                    stack.push(selectedNum + 1);
                }

            }


            System.out.println(count);
            stack.clear();
            count = 2;
        }




    }

    public static boolean isRight(int n) {

        if(n > restDistance){
            return false;
        }else {
            selectedNum = n;
            count += restDistance / n;
            restDistance -= n * (restDistance / n);
            return true;
        }

    }

}

굉장히 부끄럽다. 하지만 점차 이런 실수를 줄여나가기 위해 코드를 올려본다. 나처럼 생각한 사람 없을까..?

확실히 문제를 제대로 분석안하고 코드를 짜니까 이렇게 구구절절한 코드가 나왔다. 결국 해결도 못하고!!!!

그래서 결국 다른 풀이를 봐버렸다. 찾아보니까 대부분 규칙성을 찾아서 금방 쉽게 해결했다. 현타가 또 왔다..^^

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

public class Main {

    public static int restDistance;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            int distance = y-x;
            int count = 0;

            int max = (int)Math.sqrt(distance);

            if(max == Math.sqrt(distance)) {
                count = 2*max - 1;
            }else if(distance <= max * max + max) {
                count = 2*max;
            }else {
                count = 2*max + 1;
            }

            System.out.println(count);
        }


    }



}

코드는 굉장히 간단하지만 규칙성을 이해하는데 좀 걸렸다. 생각해보니 문제 조건이 다 문제 해결의 핵심 키워드였다. (예전에 맨날 수학 풀 때 선생님이 문제에 답이있다!!!라고 맨날 말씀하셨었는데 선생님 저는 아직도 그걸 못하고 있네요..^^ 나이를 먹어도 왜 변하질 않죠?ㅎ)

1. 출발 시, 도착 시 이동거리는 1

2. 직전 이동 거리의 -1,+0,+1 거리 중 하나 선택하여 이동

-> 이 두 조건때문에 주어진 거리(distance)에 따라 이동한 거리에 규칙성이 생기고 이동 거리 최댓값과 count의 연관성만 알아내면 문제해결할 수 있다. (distance = 1 일때부터 손으로 직접 적어가며 나열해보면 규칙성을 발견할 것이다.)

나중에 또 풀어봐야겠다..

이 문제는 별로 어렵지 않게 풀었다.

주의해야 할 점은 0층부터 14층까지 있다는 것. -> 인덱스 주의해야한다.

다음과 같은 방식과 푼 건 최대 입력값이 14로 굉장히 작기 때문에 저렇게 다 구해놓고 바로 찾는게 가능하다.

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[][] arr = new int[15][15];
        int sum = 0;

        for(int i=0;i<arr.length;i++) {
            for(int j=1;j<=arr.length - 1;j++) {
                if(i==0) {
                    arr[i][j] = j;
                }else {
                    sum += arr[i-1][j];
                    arr[i][j] = sum;
                }
            }
            sum = 0;
        }

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

            System.out.println(arr[k][n]);
        }
    }

}

문제를 풀고 나서 다른 분이 푼 풀이도 찾아봤는데 훨씬 더 간단한 로직이 있었다. 내가 푼 방식은 일일이 계속 sum을 구하기 때문에 똑같은 행위를 반복하는 것이다. 이건 중복에 해당되므로 깨끗한 코드?라고 볼 순 없을 것 같다.

for(int i=1;i<arr.length;i++) {
    arr[0][i] = i;
    arr[i][1] = 1;
}

for(int i=1;i<arr.length;i++) {
   for(int j=2;j<arr.length;j++) {
       arr[i][j] = arr[i][j-1] + arr[i-1][j];
   }
}

이전 인덱스의 값들을 이용해 쉽게 구할 수 있다. 그림으로 생각해보면 [자기 왼쪽 호의 값 + 자기 바로 아래 층의 값]이라고 생각하면 된다.

 알고리즘 문제를 풀다가, 백준의 자바 버전은 11인데 내가 로컬에서 사용하는 자바는 8 버전이었어서 버전 차이로 인해 문제가 틀린 걸까봐 찾다가 알게 된 내용들이다. 

 java 11은 8에 비해 달라진 점은 많지만 써보지도 않았는데 달달 외우는 건 의미없겠다 싶어 아는내용, 직접 써 본 개념들로만 정리해보려한다.

1. 문자열 함수 추가

2. java 명령어만으로 .java 파일 실행 가능 ( JEP 330 )

<1>

 자바는 다른 언어들에 비해 문자열 다루기가 쉽지 않은 언어이다. 근데 이번에 알게되고 나서 많이 좋아졌다는 생각이 들었다. 

 11에 이런 메소드들이 추가되었으니 지금은 17 버전이 제일 최신 버전이니까 훨씬 더 많은 문자열 함수가 있지 않을까 싶다.

• strip() : 공백 제거 함수
• stripLeading() : 앞 공백 제거 함수
• stripTailing() : 뒤 공백 제거 함수
• isBlank() : 공백 체크 함수, 문자열이 비어있거나 공백만 포함되어 있을 경우 true 반환
• lines() : 문자열을 라인 단위로 쪼개는 스트림을 반환
• repeat(n) : 문자열을 n번 반복

-> 문자열 문제를 풀어서 함수 사용에 익숙해져야겠다.

<2>

 자바 파일을 명령어 방식으로 실행시킬 때 꼭 컴파일 명령어 이후에 실행했었어야 했다. 근데 11 버전부터는 'java' 명령어로 한 번에 된다니 간편하고 좋은 것 같다. 즉 'java' 명령어 하나면 11 버전에서는 컴파일 + 실행 둘 다 한 번에 가능하다는 말이다.

(여기서, 컴파일이란? - 컴퓨터 언어에서 기계가 이해할 수 있는 기계 언어로 변환하는 과정을 말한다!)

•  JEP(JDK Enhancement Proposal) : 자바 버전이 업그레이드 될 때 마다 향상된 기능을 정리해놓은 문서? 같다.
• 자바런처가 java 소스 코드의 단일 파일로 제공되는 프로그램을 실행할 수 있도록 향상시킬 목적을 가지고 있다. -> java 언어 스펙을 변경하고자 함. 예를 들어 public static void main(String[] args) 메소드 필요성 제거와 같이 간단한 프로그램 작성방법을 수용할 수 있게 하기 위한 목적을 가지고 있다.

이걸 알게되고 나서 자바 언어 자체가 굉장히 까다롭고 지켜줘야할 부분이 많은 언어이기 때문에 버전이 업그레이드 될 수록 뭔가 좀 더 간단하게? 쉽게? 할 수 있는 방향을 추구한 것 같은 느낌을 받았다.

이 문제는 딱 봤을 때 문제가 길어보이지만 로직은 어렵지 않은 문제다. 금방 해결할 수 있었다.

하지만 마지막에 출력을 위해 입력받은 int 값을 String으로 변환하기 위해서 String의 valueOf라는 메소드를 사용하였는데 여기서 문제가 있어서 자꾸 틀렸습니다라고 결과가 나왔다.

알고보니 내가 메소드를 잘못 사용한 것이었는데 처음엔 어디서 문제인지 몰라서 조금 헤맸다. 하지만 금방 해결할 수 있었다.

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        String[] arr = new String[t];
        int i = 0;
        int room = 0;
        int floor = 0;

        while(i < t) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
           
            if(n % h == 0) {
               room = n / h;
               floor = h * 100;
            }else {
               room = n / h + 1;
               floor = (n % h) * 100;
            }
            
            System.out.println(floor + room);

            i++;
        }

    }

}

나는 입장순서와 높이를 가지고 방 번호를 구했다. 여기서 100을 곱하지 않고도 room이 10보다 작은지 아닌지 조건문으로 한 자리 수 앞에 0 표기를 해결할 수도 있다. 하지만 조건문을 한 번 더 써야하는 게 더 복잡하다고 생각되어 100을 곱하는 것으로 바꾸었다.

 문제를 풀고 나서 아예 다르게 푼 분의 풀이를 보았다. 되게 신선한 방법이었다. 훨씬 코드도 짧고 간결했다. 큰 사이즈의 배열을 만들고 거기에 제일 가까운 순서대로 방번호를 넣어주고 찾는 방법이었는데 괜찮은 방법이었다. 역시 알고리즘 문제 풀 때는 여러 방식으로 풀 수 있는 것 같다.

이 문제는 수월하게 해결할 수 있었다. 

다만, 주의할 점은

 1. 입력값 범위는 큰 데 주어진 시간이 짧으므로 반복문으로 해결이 안될 수 있다.

 2. '정상에 도착하면 다시 미끄러지지 않는다.' 라는 문제 조건을 잘 활용해야 한다.

처음에 반복문으로 했다가 시간 초과가 나서 통과하지 못했다. 그래서 다시 수정한 코드로 통과했다.

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));
StringTokenizer st = new StringTokenizer(br.readLine());

int afternoon = Integer.parseInt(st.nextToken());
int night = Integer.parseInt(st.nextToken());
int tree = Integer.parseInt(st.nextToken());

int oneDay = afternoon - night;
int start = tree - afternoon;

int days = start / oneDay;

if(start % oneDay > 0) {
days = days + 1;
}

System.out.println(days + 1);

}


}

이 문제... 보자마자 감 안왔다. 엥 이걸 어떻게 구하지 대체. 근데 분명 방법이 있을텐데 내가 모르는 거고 문제를 딱 읽었을 때 아 이렇게 하면 되겠다 라는 감이 보통 오는데 안왔다. 브론즈1 문제인데도 몰라서 한숨이 나왔다. 하지만 어떻게든 풀어보자 라는 생각으로 로직 생각을 시작했다.

 처음 접근 방법을 순서 값에 규칙이 있지 않을까 싶어서 '몇 번째 순서' 여기에 초점을 맞췄다. 행이 0이거나 열이 0인 칸들을 제외하고 나머지들은 오른쪽 대각선 방향으로 4n만큼 증가한다. 즉 2/2는 5번째로, 1/1(1번째)에서 +4이다. 이렇게 접근하니 문제를 해결할 수 없었다. 위->아래 방향 또는 아래 -> 위 방향 이렇게 고정된 것이 아닌 번갈아가면서 대각선 방향이 바뀌기 때문에 규칙을 찾긴 찾아도 값을 얻기 위한 계산이 매우 복잡했다.

아무리 생각해도 모르겠어서 구글링 해 보았다. 힌트를 조금 얻었다. n까지의 개수를 이용해 구하는 방식이었다. 그래서 최종적으로는

 n까지의 개수, 짝수/홀수의 대각선 방향, 그에 따른 분모,분자값의 증가/감소를 이용해 해결할 수 있었다.

 이 문제에서의 교훈. '문제에서 접근 힌트를 얻자' 이다. 지그재그 방향... 짝수 인덱스에서는 올라가고 홀수 인덱스에서는 내려간다는 것을 알아채면 조금 더 빨리 해결할 수 있지 않았을까 싶다. 처음에 아예 잘못된 방향으로 갔더니 다른 방향을 생각해보지 않았다. 이것도 고쳐야할 점이다. 잘못됐다 싶으면 아예 다른 방식의 로직 생각해보기.

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 x = Integer.parseInt(br.readLine());
int line = -1;
int n = 0;
int prev = 0;
int rest = 0;

if(x == 1) {
System.out.println(x + "/" + x);
return;
}

while(true) {
if( x <=(n*(n+1)/2)) {
prev = n*(n-1)/2;
rest = x - prev;
break;
}
line++;
n++;
}

if(line % 2 == 1) {
int mm = line + 1 - (rest - 1);
int nn = 1 + (rest - 1);
System.out.println(nn + "/" + mm);
}else {
int mm = 1 + (rest - 1);
int nn = line + 1 - (rest - 1);
System.out.println(nn + "/" + mm);
}
}
}