package buffer;

import java.io.*;
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 N = Integer.parseInt(st.nextToken());
        int length = String.valueOf(N).length();
        int i = 0;

        for(i = Math.max(N - length*9, 0); i < N; i++) {
            int sum = 0;
            String num = String.valueOf(i);
            for(int j = 0; j < num.length(); j++) {
                sum += Integer.parseInt(String.valueOf(num.charAt(j)));
            }
            sum += i;
            if(N == sum) break;
        }

        System.out.println(i==N?0:i);
    }
}

처음에는 0부터 N까지 반복하면서 찾아야 하나 생각이 들었다. 그럼 너무 비효율적일 것 같아서 반복 횟수를 줄이는 방법을 생각해냈다.

N이 999라고 한다면, 생성자는 무조건 세 자리수 이하일 것이다. 생성자 자기 자신 + 각 자리 수의 합이 999가 되어야 한다. 각 자리수의 합은 최대값은 9*3 인 27이 된다. (1~27) + x = 999, => 즉 972 <= x <= 998 을 가진다. 때문에 N 값에서 각 자리수 합의 최대값을 뺀 값까지만 탐색하면 된다는 판단을 내렸다.

가장 작은 생성자를 찾는 것이기 때문에, 생성자가 될 수 있는 N - (N의 최대 자리수 합) 부터 i를 반복하고 생성자를 찾을 시 종료해주면 된다.

만약 N이 한 자리수라면 i의 시작 값이 음수가 되기 때문에 예외가 발생한다. 이를 Math.max(i값, 0) 으로 처리해주면서 예외를 없애주었다.

package buffer;

import java.io.*;
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 sum = 0;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int [] arr = new int [N];
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N-2; i++) {
            for(int j = i+1; j < N-1; j++) {
                for(int k = j+1; k < N; k++) {
                    int i1 = arr[i] + arr[j] + arr[k];
                    if(M >= i1 && sum < i1) {
                        sum = i1;
                    }
                }
            }
        }
        System.out.println(sum);
    }
}

문제를 보면 배열에서 세 가지의 숫자를 뽑아서 합이 M과 가장 가까운 합을 출력하는 것이다. 중복되지 않게 3개를 뽑아야 한다. 반복문 3개를 사용해서 중복되지 않고 3개를 뽑는 코드를 작성했다. M을 넘지 않고, sum(초기값 0)보다 크다면 업데이트 하는 식으로 조건식을 작성했다.

도저히 감이 잡히지 않아서 다른 블로그를 참고했다.

방법 1. 시그마 공식 사용

$\displaystyle\sum_{i=1}^{n}{1}$ 이 식의 반복 횟수는 $n-1+1$ 이다. -> 윗끝 - 아랫끝 + 1 이라고 볼 수 있다.

해당 문제의 알고리즘을 시그마 식으로 나타내면, $\displaystyle\sum_{i=1}^{n-2}\displaystyle\sum_{j=i+1}^{n-1}\displaystyle\sum_{k=j+1}^{n}1$ 이다.

순차적으로 시그마 공식을 적용시켜 보겠다. $\displaystyle\sum_{i=1}^{n-2}\displaystyle\sum_{j=i+1}^{n-1}(n-j)$

$\displaystyle\sum_{i=1}^{n-2}\frac{(n-i-1)(n-i)}2$

$(n)(n-1)(n-2)\over 6$ 으로 정리할 수 있다.

방법 2.조합 공식 이용

(i,j,k)에 값을 넣어보며 규칙을 찾아보면 (1,2,3)...(1,2,7) (2,3,4)...(2,3,7) ... (5,6,7) -> 중복되지 않는 세 숫자가 나타난다.

$_nC_k = \frac{n!}{(n-k)!*k!}$

$_nC_3 = \frac{(n)(n-1)(n-2)} 6$

위 식과 동일하다는 것을 알 수 있다.

package buffer;

import java.io.*;
import java.util.StringTokenizer;
import java.math.BigInteger;

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

        long n = Long.parseLong(st.nextToken());

        BigInteger result = new BigInteger(String.valueOf(n*(n-1)*(n-2)/6));



        System.out.println(result.toString() + "\n" + 3);
    }
}

package buffer;

import java.io.*;
import java.util.StringTokenizer;
import java.math.BigInteger;

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

        BigInteger n = new BigInteger(st.nextToken());
        BigInteger result = n.pow(3);

        System.out.println(result.toString() + "\n" + 3);
    }
}

자바에서는 500000*3의 값을 출력할 수 있는 기본 자료형이 존재하지 않는다.

때문에, java.math.BigInteger 클래스를 추가해서 무한대의 정수값을 받을 수 있도록 해줘야 한다.

math 패키지에 속하고 있기 때문에 멤버 메서드에 기본적인 수학 메서드는 다 있다.

toString()으로 출력해준다.

package buffer;

import java.io.*;
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 [] arr = new int[st.countTokens()];
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] > max) {
                max = arr[i];
                maxIndex = i;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if(i != maxIndex) {
                sum += arr[i];
            }
        }

        if(sum <= max) {
            arr[maxIndex] = sum - 1;
        }

        System.out.println(sum + arr[maxIndex]);
    }
}

세 값을 입력받는다. 배열의 세 값중 최대 값과 그 값의 인덱스를 찾는다. 만약 삼각형의 조건을 충족하지 않는다면, arr[maxIndex]값을 sum - 1로 줄인다. sum + arr[maxIndex] 값을 출력한다.

package scanner;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true) {
            int [] arr = new int[3];
            int max = Integer.MIN_VALUE;
            int maxIndex = 0;
            int sum = 0;

            for(int i = 0; i < 3; i++) {
                arr[i] = sc.nextInt();
                if(arr[i] > max) {
                    max = arr[i];
                    maxIndex = i;
                }
            }

            if (arr[0] == 0 && arr[1] == 0 && arr[2] == 0) {
                break;
            }

            for (int i = 0; i < 3; i++) {
                if(i != maxIndex) {
                    sum += arr[i];
                }
            }
            if(max >= sum) {
                System.out.println("Invalid");
            } else if(arr[0] == arr[1] && arr[1] == arr[2]) {
                System.out.println("Equilateral");
            } else if(arr[0] == arr[1] || arr[0] == arr[2] || arr[1] == arr[2]) {
                System.out.println("Isosceles");
            } else {
                System.out.println("Scalene");
            }


        }

    }
}

반복문을 사용해서 세 개의 값이 모두 0일때까지 반복한다. 세 값 중 최대 값과 최대값의 인덱스를 찾는다. 최대 값이 아닌 값들의 합을 구한다. 조건문을 사용하여 결과를 출력한다.

1. 삼각형인가?
2. 정삼각형인가?
3. 이등변 삼각형인가?
4. 부등변 삼각형인가?

코드

package buffer;

import java.io.*;
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 [] x = new int [3];

        x[0] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        x[1] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        x[2] = Integer.parseInt(st.nextToken());

        if(x[0] + x[1] + x[2] != 180) {
            System.out.println("Error");
            return;
        }

        if(x[0] == 60 && x[1] == 60) System.out.println("Equilateral");
        else if(x[0] == x[1] || x[0] == x[2] || x[1] == x[2]) System.out.println("Isosceles");
        else System.out.println("Scalene");

    }
}

삼각형 판별을 먼저 한 후, 아니라면 return 한다.

정삼각형, 이등변삼각형, 일반 삼각형 순으로 조건문을 만들고 출력한다.

코드

package scanner;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [][] arr = new int[n][2];
        int xMin = Integer.MAX_VALUE;
        int xMax = Integer.MIN_VALUE;
        int yMin = Integer.MAX_VALUE;
        int yMax = Integer.MIN_VALUE;


        for(int i = 0; i < n; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            if(arr[i][0] < xMin){
                xMin = arr[i][0];
            }
            if(arr[i][0] > xMax){
                xMax = arr[i][0];
            }

            if(arr[i][1] < yMin){
                yMin = arr[i][1];
            }
            if(arr[i][1] > yMax){
                yMax = arr[i][1];
            }
        }

        System.out.println((xMax-xMin) * (yMax-yMin));
    }
}

각 좌표의 최대 최소 값을 구해서 길이의 차를 곱해줬다.

런타임 오류 코드

반복문을 비효율적으로 사용해서 런타임 오류가 발생했다.

수정 코드

package scanner;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int [][] arr = new int[3][2];

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

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

        for(int i = 0; i < 3; i++){
            if(arr[0][0] == 0 && arr[i][0] != 0) {
                System.out.print(arr[i][0] + " ");
            }
        }
        if(arr[0][0] != 0) System.out.print(arr[0][0] + " ");

        for(int i = 0; i < 3; i++){
            if(arr[0][1] == 0 && arr[i][1] != 0) {
                System.out.println(arr[i][1]);
            }
        }
        if(arr[0][1] != 0) System.out.println(arr[0][1]);
    }
}

뭔가 비효율적이라고 생각한다. 단순히 x와 y값 중에 짝이 없는 값을 출력하는 코드를 작성했다. 다른 사람이 해결한 방식을 참고해봐야겠다.

수정의 수정

반복문으로 판별하기보다는 단순히 조건문을 여러개 써서 짝이 아닌 것을 찾아보겠다.

package scanner;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int [][] arr = new int[3][2];

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

        int x, y;

        if(arr[0][0] == arr[1][0]) x = arr[2][0];
        else if(arr[0][0] == arr[2][0]) x = arr[1][0];
        else x = arr[0][0];

        if(arr[0][1] == arr[1][1]) y = arr[2][1];
        else if(arr[0][1] == arr[2][1]) y = arr[1][1];
        else y = arr[0][1];

        System.out.println(x + " " + y);
    }
}

이렇게 풀이해봤지만 조건문을 사용하는게 미세하게 더 오래걸렸다..!

Scanner가 역시 너무 느린듯 하다.

값 4개를 입력받고 x, y가 경계와 더 가까운쪽을 삼항연산자로 구한 뒤 더 작은 값을 출력했다.

1. 진법 변환 구조

10진법으로 변환한 값에 자릿수에 맞는 B의 거듭 제곱의 값을 곱해줘야 한다.

2. 알파벳 처리

조건이 대문자만 입력된다고 가정을 했으니

'A' : 65

'Z' : 90

'0' : 48

'A'는 10진법 값이 10이어야 한다. 따라서 'A' - 'A' + 10 을 해주면 10의 값을 얻을 수 있다.

알파벳 처리 => C - 'A' + 10

'0'은 10진법 값이 0이어야 한다. 따라서 '0' - '0' 을 해주면 0의 값을 얻을 수 있다.

0~9 까지의 숫자 처리 => C - '0'

​

3. 문자열을 어떻게 10진법의 숫자로 만들까?

String 메서드인 charAt()을 이용해서 char 형태로 하나씩 얻어온다.

char 변수에 char 상수를 빼는 연산을 수행하면 정수값으로 변한다.

(자바에서 char 타입이 사실상 정수형(유니코드)을 기반으로 하기 때문.

연산자를 사용하면 char 타입은 유니코드 값을 가지며 정수형으로 반환된다.

​

4. Character.getNumericValue(char C) 활용

Character 클래스에 아주 유용한 메서드가 있었다.

그냥 문자 자체를 아스키코드가 아닌 정수로 바꿔준다.

대소문자 상관없이 az 까지는 1035까지 바꿔주고

. , ? ! 과 같은 기호는 -1로 출력된다.

방의 범위가 6, 12, 18, 24... 순으로 커진다.

i는 각 범위의 마지막 번호이다.

입력된 N보다 i가 커질 때 까지 반복하며 i와 거쳐가는 방의 수(result)를 늘려간다.

비정방형 배열로 바꾸어보면

arr[0] : 1/1

arr[1] : 1/2 2/1

arr[2] : 3/1 2/2 1/3

arr[3] : 1/4 2/3 3/2 4/1

arr[4] : 5/1 4/2 3/3 2/4 1/5

...

규칙 1 : 각 공간의 크기는 1씩 증가한다.

규칙 2 : 짝수번째 배열은 큰 수가 먼저 등장한다.

규칙 3 : 분자와 분모가 서로 반대 방향으로 1씩 크기가 변한다.

​

주어진 N으로 먼저 몇 번째 배열인지 찾으려고 시도했다.

n(n+1)/2 = N 이니까 역으로 진행하면 찾을 수 있지 않을까 라는 생각이 들었다. [규칙 1]

정수로 바꿔줘야 하지만, 소숫점 자리를 올림 처리하여 n 번째 배열임을 찾았다.

그 다음 arr[n]의 몇 번째 순서를 출력해야 하는지 찾기 위해 N - n(n - 1)/2을 해주었다.

n-1 번째까지의 모든 순서를 구하고 N에서 빼서 n번째 배열에서 몇 번째 순서인지를 offset에 저장했다.

1부터 시작하는 i와 n 부터 시작하는 j를 i가 offset과 같아질 때 까지 반복했다.

마지막으로 짝수와 홀수의 경우를 구분하여 출력하며 마무리했다. [규칙2, 3]

단순한 문제였다.

아직 BufferedReader랑 StringTokenizer 사용법을 잘 몰라서 Scanner를 썼다. StringBuilder 클래스도 쓰던데 나중에 알아봐야겠다. 약수는 나눴을 때 나머지가 없으면 된다.

첫 시도는 실패했다. 출력 예시 값은 제대로 출력되었는데, 어떤 예외가 있는지 생각이 안난다..

지피티에 도움을 요청하니 만약 i 가 1일때의 경우를 생각하지 않아서였다. i가 1이라면, ck 가 false가 되어 sum과 min에 값이 들어가게된다. 그래서 시작할 때 i가 1이라면 ck가 true가 되게 끔 설정해줬다.

하지만 소수를 찾는 방법이 굉장히 비효율적인 코드여서 공략의 힘을 빌렸다. 다른 사람들의 풀이와 지피티의 풀이도 에라토스테네스 체 알고리즘을 이용했다.

에라토스테네스 체 알고리즘

• 소수를 찾기 위한 고대 그리스 수학자 에라토스테네스가 고안한 알고리즘.
• 이 방법은 주어진 수 n 이하의 모든 소스를 빠르게 찾는 데 효율적이며, 간단하지만 강력한 소수 판별 방법으로 알려져 있다.

알고리즘 과정

1. 초기화 : 2부터 n까지 모든 수를 나열한다. 여기서 2는 소수임이 알려져 있음으로, 가장 처음 소수로 시작한다.
2. 소수 선택 : 가장 작은 소수 (처음엔 2)를 선택하고, 해당 소수의 배수를 모두 지운다. 이때, 자신은 지우지 않고 그대로 둔다.
3. 반복 : 다시 남아있는 수로 이동하여 소수로 판별하고, 그 소수의 배수를 다시 지운다.
4. 종료 조건 : $\sqrt n$ 보다 작은 수까지 확인이 끝나면 이후의 수들은 이미 소수로 판별된 상태가 된다.

에라토스테네스 체 알고리즘의 시간복잡도

• 주어진 범위 n에 대해 O($n\log\log{n}$)의 시간복잡도를 가진다.

알고리즘 구현 코드

boolean[] isPrime = new boolean[N+1];

for(int i = 2; i <= N; i++){
    isPrime[i] = true;
}

for(int i = 2; i * i <= N; i++) {
    if(isPrime[i]) {
        for(int j = i * i; j <= N; j += i) {
            isPrime[j] = false;
        }
    }
}

에라토스테네스 체 알고리즘을 적용시켜서 풀어보았다.

시간이 확실히 단축되었음을 확인할 수 있다.

만약 i로 나눠진다면 출력하고 N 값을 나눈 몫으로 바꾸는 작업을 했고, i 가 증가되지 않도록 continue 문을 넣었다.

입력받은 숫자마다 1과 자신을 제외한 약수가 존재하는지 여부를 체크하고 cnt를 증가시켜 출력함.

n전까지만 반복하여 약수인 경우 checkSum 변수에 더해가고, StringBuffer에 i 값을 집어넣어주었다. 마지막에 ' + ' 부분만 빼기 위해 sb.delete(sb.length() - 3, sb.length()); 를 해주었다.

카운트를 만들어서 n을 1부터 n까지 나누며 약수의 숫자를 계산했다. 못찾았을 경우 0을 출력하기 위해 boolean 변수를 추가했다.

1. 외관 확인

[ ] 외관 기스 확인 [ ] 자판, 트랙패드 기스 확인 [ ] 시스템 종료 후, 액정 기스 확인

2. 흔들기

[ ] 좌우로 흔들어서 내부 하드웨어 부착상태 확인하기

3. 수평확인

[ ] 맥북을 평평한 곳에 두고 모서리 네 곳을 눌러서 수평 확인

4. Port 확인

[ ] 정품 충전기 맥세이프 포트 확인 [ ] C타입 단자 확인 [ ] sd카드 단자 확인 [ ] hdmi 단자 확인 [ ] 오디오 단자 확인

5. 사양확인

[ ] 맥 좌측 상단 '이 Mac에 관하여' 클릭 후 사양 체크

6. 키보드 테스트

[ ] 메모장 열고 모든 버튼 한 번씩 눌러보기 [ ] 온라인 키보드 테스트

7. 트랙패드 테스트

[ ] 2중 터치 체크 [ ] 확대, 축소 확인 [ ] 손가락 두개로 마우스 우클릭 활성화 [ ] 파인더 앱에서 파일을 꾹 눌렀을 때 창이 뜨는지

8. 오디오 테스트

[ ] 스피커 테스트

9. 모니터 불량화소 테스트

[ ] 불량화소 테스트 [ ] Fn + cmd + F11 -> 검정화면 [ ] 트랙패드 한 번 클릭 -> 하얀 화면 [ ] 계속 트랙패드 클릭해서 모든 색상 출력 확인 [ ] 줄이 생기는지, 모니터 빛 샘 확인