[항해99][선택 온보딩-2] 2일차 문제풀이

백준 10250 java 호텔 https://www.acmicpc.net/problem/10250

10250번: ACM 호텔

흔한 몫과 나머지 유형으로 1일 차 문제보다 이게 더 쉬운 것 같았다.

이게 코테 문제풀이가 아니라 프로그램을 짜는 거였다면 예외처리를 어디까지 해야 하는지에 대한 의문은 있었음 (주석 참고)

static void input() throws Exception{
    
    int caseNum = scan.nextInt();
    for(int z = 0 ; z < caseNum ; z++){
        int h = scan.nextInt();
        int w = scan.nextInt();
        int n = scan.nextInt();
        // 6층인 경우
        // 1 : 101 2 : 201 .... 7 : 102
        // 호수는 n-1 에서 층수를 나눈 몫 + 1
        // 층수는 n-1 을 층수로 나눈 나머지 + 1
        int room = (n-1) / h + 1;
        int floor = (n-1) % h + 1;
        
        // 문제 조건엔 없지만 예외처리
        // 어차피 계산식에 의하여 floor는 h보다 클일이 없으므로
        // room > w 로 예외를 잡는게 좋은지, 아니면 h*w < n으로 잡는게 좋은지 고민이였는데
        // 주석달다 보니 h * w < n 으로 예외를 잡는게 좋아보인다.
        if(room > w){
            throw new Exception("만방");
        }

        
        sb.append(floor * 100 + room + "\\n");
    }
    print();
}

---

백준 1110 java 사이클 https://www.acmicpc.net/problem/1110

1110번: 더하기 사이클

while(true){
	...
}

 위의 형태를 엄청 선호하진 않지만(true 대신 반복 조건 넣기를 선호)

이 문제의 경우 시작할 때, 현재 변하고 있는 num변수와 비교할 n이 같은 상태라서

두 수가 다를 때까지만 반복하기에는, (  while(num != n )  로 처리하기에는)

1회의 시행을 while문 밖에서, 이후로는 while문 안에서 같은 행위를 해줘야 해서 (내가 보기에) 가독성 좋게 while(true)로 처리했다.

 

옳게 풀었는지 질문해 봐야겠다.

[매니저님의 답변] : while(true)를 현업에서 사용하지않는건 맞지만 문제 풀때는 본인이 이해하기 쉽게 짜기만 하면 된다.

while(true)를 사용하지 않았을 때 오히려 가독성이 나빠진다던가 하는 경우가 있을 수 있으므로 너무 고민하지 않아도 된다.

static void input() throws Exception{
    // 문제에서 1의자리의 시행을 설명하지 않아서 생각해보자
    // 8 -> 08  & 8-> 88 그냥 두개 반복이된다.
    int n = scan.nextInt();
    
    int num = n;
    int iteration = 0;
    while(true){
        
        // 일의자리의 경우에는 문제되는 부분이 num / 10 하는 부분으로 
        //어차피 0으로 계산되어 계산과정에 문제가 생기지 않아 예외처리 하지 않음
        int sum = (num / 10) + (num % 10); // 자릿수 합
        num = (num%10) *10 + sum%10; // 새로운 수로 교체
        iteration++;
        if(num == n)
            break;
    }
    System.out.println(iteration);

}

보자마자 예외처리가 필요 없음을 직감한 지금의 나와 달리 과거의 나 고생했었네..

---

 

백준 1929 java 소수 구하기 https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

척 봐도 에라토스테네스의 체 문제다 하고 풀기 시작했다.

 

[개선 전 코드(정답인데 시간이 느림)]

static void input() throws Exception{
    //에라토스테네스의 체 n root n 의 복잡도로 처리 가능?
    // 10 ^ 9 10억의 연산인데 간단하니까 할수있겟지?
    int s =  scan.nextInt();
    int e = scan.nextInt();
    int[] arr = new int[e+1];
    
    for(int i = s; i <=e ; i++)
        arr[i] = i;
    //1은 소수가 아님
    arr[1] = 0;
    double root = Math.pow(e, 0.5);
    for(int i = s; i <=e; i++)
        for(int j = 2; j <= root ; j++ )
            if(i!=j && arr[i] % j == 0)
                arr[i] = 0;

    
    for(int i = s; i <=e; i++)
        if(arr[i] > 0)
            sb.append(arr[i] + "\\n");
    print();
}

어떻게 이렇게 쉽지 하고 있었는데, 이상하게 제출한 코드가 털털거리면서 채점되고 좀 느린감이 있었다. 실제로 제출된 걸 보니까 시간이 오래 걸렸다.

근데 3656ms가 걸렸는데 2초 제한을 어떻게 통과했지?

 

의문이 생겨서 java11로 제출한 다른 사람들의 제출기록을 보니까 시간이 200ms로 엄청 빨리 푸는 법이 있는 것 같았다!

내가 에라토스테네스의 체를 느리게 돌아가도록 구현하고 있었나 보다. 문제점을 찾아보자

 

[개선해야 할 부분]

// 초기화
for(int i = s; i <=e ; i++)
    arr[i] = i;

//1은 소수가 아님
arr[1] = 0;

double root = Math.pow(e, 0.5);
//에라토스테네스의 체
for(int i = s; i <=e; i++)
    for(int j = 2; j <= root ; j++ )
        if(i!=j && arr[i] % j == 0)
            arr[i] = 0;

먼저 눈에 보이는 문제는, arr[i] 배열이 그다지 쓸모없다는 것, 무슨 말이냐면

에라토스테네스의 체 구현부 안의 2중 for문 안에서 (i!=j && arr[i] % j == 0) 이 조건문 안에서 검사하고 있는  arr[i]값은 어차피 i 혹은 0이라는 것

 

자세히 들여다보면,

1. arr[i] = i 인 경우 : 만약 j로 나누어 떨어진다면 if문안으로 들어가 arr[i] = 0으로 바꿔준다.
2. arr[i] = 0인 경우 : j가 몇이든 일단 조건문은 통과하게 되므로 이미 arr[i] = 0인데도 불필요한 연산이 들어간다.

2번을 자세히 설명하자면 애초에 j=2일 때 2의 배수들을 모조리 검사하고 arr[짝수] 들을 다 소수가 아니므로 0으로 바꾸어 줬는데도 불구하고 j가 2보다 큰 짝수일 때 불필요하게 조건문을 통과하여 redundant한 연산을 수행한다는 것이다.

개선 방안

1. arr[i]가 i를 저장하고 있을 필요가 없다. → 소수인지 아닌지 boolean으로?
2. 이미 검사한 수에 대해서 빠르게 넘길 방법

[개선된 코드]

static void input() throws Exception{
    int s =  scan.nextInt();
    int e = scan.nextInt();
    boolean[] arr = new boolean[e+1];
    
    Arrays.fill(arr, true);

    // 1에 대하여 검사하면 모두 false가 된다.
    arr[1] = false; 
    for(int i = 2; i <=e; i++){
        // 이미 지워진 수의 배수들은 이미 지워졌었음
        if(!arr[i])
            continue;
        // 나머지가 0인지 찾는 연산보다 현재 검사하는 수의 배수를 검사하는 게 낫다
        for(int j = i * 2; j <=e ; j+=i){
            arr[j] = false;
        }
        // 위의 for문을 지나왔는데 아직 arr[i] == true라면 소수
        if(arr[i])
            sb.append(i + "\\n");
    }

    print();
}

위 코드로 제출하니 300ms 정도 걸렸다.

 

항해99의 문제풀이 가이드를 따라서 정답을 안 보고 구현해 가지고 저게 최고로 잘 짠 건지는 모르겠다.

 

---

 

백준 1011 java Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

단순 수학 Ad hoc 문제로, 규칙을 열거하다가 제곱수에서 규칙이 생긴다는 점을 알아내면 쉽게 풀 수 있다.

static void input() throws Exception{
    // 1 : 1
    // 2 : 1 1
    // 3 : 1 1 1 
    // 4 : 1 2 1
    // 5 : 1 2 1 1
    // 6 : 1 2 2 1
    // 7 : 1 2 2 1 1
    // 8 : 1 2 2 2 1
    // 9 : 1 2 3 2 1
    // 10 : 1 2 3 2 1 1 
    // 11 : 1 2 3 2 2 1
    // 12 : 1 2 3 3 2 1
    // 13 : 1 2 3 3 2 1 1
    // 14 : 1 2 3 3 2 2 1
    // 15 : 1 2 3 3 3 2 1
    // 16 : 1 2 3 4 3 2 1
    // 17 : 1 2 3 4 3 2 1 1
    // 18 : 1 2 3 4 3 2 2 1
    // 19 : 1 2 3 4 3 3 2 1
    // 20 : 1 2 3 4 4 3 2 1
    // 21 : 1 2 3 4 4 3 2 1 1
    // 22 : 1 2 3 4 4 3 2 2 1
    // 23 : 1 2 3 4 4 3 3 2 1
    // 24 : 1 2 3 4 4 4 3 2 1
    // 25 : 1 2 3 4 5 4 3 2 1 
    // 10 ~ 16  6~7
    // 17 ~ 25  8~9
    int cases = scan.nextInt();
    for(int z=0; z < cases; z++){
        int answer = 0;
        long x = scan.nextInt();
        long y = scan.nextInt();
        long distance = y - x;
        // 10과 16을 같은 범위로 분류하기 위해 -1
        int root =  (int)Math.pow(distance - 1, 0.5);
        
        //root * 2 에다가 범위중 중앙값이상인경우라면 +1
        answer += root*2;
        
        // 자연수의 제곱수의 차이의 범위의 길이는
        // 자연수가 홀 짝 번갈아가기때문에 항상 홀수이다.
        double mid = (Math.pow(root, 2) + Math.pow(root+1, 2)) / 2;
        if(distance >= mid)
            answer++;
        sb.append(answer).append('\\n');
    }
    print();
}