냥냥개발펀치

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

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);
        }

    }
}

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

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

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

다른 풀이를 보니까 현타*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];
   }
}

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

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

하지만 마지막에 출력을 위해 입력받은 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);
}
}
}

이 문제는.... 쉬울 거 같은데 은근 생각이 안났다. 처음 문제를 읽었을 때 내가 눈으로 보면 당연히 바로 구할 수 있지만 이걸 어떻게 코드로 구현하지..? 이런 생각이 들었다.

 이 문제는 '벌집' 자체가 핵심이다. 육각형으로 이루어진 것에서 규칙을 생각해 그대로 구현하면 되는 문제다. 1을 중심으로 주변을 둘러쌀 때 2칸, 3칸 등 칸이 증가할수록 둘러싸는 개수는 6개씩 증가한다. 이걸 생각해내는 게 첫 번째 포인트이다.

 두 번째로 막혔던 부분이다. 처음엔 수열공식을 생각해 

1 : 1칸

2~7 : 2칸

8~19 : 3칸

20~37 : 4칸

.

.

.

이런 식으로 경계값을 이용해 해당 범위 내에 있으면 칸을 구하게끔 로직을 짜서 했다. 하지만 어째서인지 채점 마지막 100% 직전에 틀렸습니다 하고 오답처리가 됐다. 아무리 생각해도 이해가 안되서 그럼 1,7,19,37 ... 등 구간의 마지막 수를 이용해 칸의 개수를 구해보자 라고 생각이 들어 로직을 짜보았다. 난 왜 여기서 공식을 생각해내는 데 오래걸렸을까? 바보 멍청이이기 때문이다.

마지막 수를 기억해 다음에 더해주면 되는데 이걸 생각못해서 조금 생각하는 시간이 길었다.  첫번째 방법으로 풀었을 때보다 훨씬 로직이 간단해서 이 방법을 채택했다. 결국 문제를 풀었고 또 하나의 교훈점을 얻어가는 문제였다.

(역시 아직도 알고리즘 문제풀 때 뭔가 불안?해서 그런지 뇌가 굳는다. 왜 생각이 안나지 이상하다.) 

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 num = Integer.parseInt(br.readLine());
int prev = 1;

if(num == 1) {
System.out.println("1");
return;
}
int n=1;
while(true) {
int pNum = 6*n + prev;
if(num <= pNum) {
System.out.println(n+1);
break;
}else {
prev = pNum;
}
n++;
}

}


}

이 문제를 풀면서 다시 한 번 새기고 간 개념 네 가지.

int의 범위는  -21억~21억까지이다.

제한 시간이 1초 미만이고 숫자가 크다면 반복문으로 해결할 수 없다.

BufferedReader의 개념

StringTokenizer의 사용

BufferedReader는 버퍼를 이용하는 대표적인 i/o 클래스이다.

스페이스와 엔터 둘 다 경계값으로 인식하는 Scanner와 다르게 엔터만을 경계값으로 인식한다.

또한 버퍼가 가득 차거나 엔터값이 들어왔을 때까지 입력값을 버퍼에 저장해뒀다 한 번에 전송한다. 입력값이 많이 않을 때는 Scanner와 속도 차이가 별로 없지만 값이 많아질수록 속도, 성능 면에서 BufferedReader가 훨씬 효율적이다.

BufferedReader로 입력받을 때 한 줄로 입력받고 공백으로 값을 구분할 때 StringTokenizer를 이용하는 것이 좋다. 단지 공백만을 없애고 값을 바로바로 인식하기 때문에 내부적으로 복잡한 split보다 훨씬 속도가 빠르다. (물론 구분자 설정을 아무것도 안해주었을 때 공백을 구분자로 인식한다는 말이다.) split은 인덱스로 접근해야 될 때 사용하면 훨씬 효율적이다.

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 fix = Integer.parseInt(st.nextToken());
int variable = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());


if(price <= variable) {
System.out.println("-1");
}else {
System.out.println(fix/(price - variable) + 1);
}

}


}

 이 문제 풀때는 '손익분기점'에 대해 좀 알아야했던 거 같다. 그리고 입력값의 범위가 크기 때문에 일일이 반복문으로 합계를 구해서 하면 시간초과로 틀린다. 그래서 위와 같은 방법으로 풀었다.

 단순한 개념을 이용한 문제인데 흠칫 했던 거 같다. 정신 차려!!!!!!!!!