[백준] 3052, 10811

문제 3052

문제

두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다. 

수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 열번째 줄 까지 숫자가 한 줄에 하나씩 주어진다. 이 숫자는 1,000보다 작거나 같고, 음이 아닌 정수이다.

출력

첫째 줄에, 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력한다.

 

---

 

문제 3052번 문제는 사용자가 10개의 숫자를 입력했을 때 42로 나눈 나머지 중, 다른 것이 몇 개인지 출력하는 것이다.

예를 들어, 사용자가 숫자 10개를 입력했을 때 42로 나눈 값이 {1, 0, 0, 0, 1, 0, 0, 1, 0, 1}일 경우, 서로 다른 값은 2개이다.

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        boolean[] remainders = new boolean[42];
        int count = 0;

        for (int i = 0; i < 10; i++) {
            int number = scanner.nextInt();
            int remainder = number % 42;

            if (!remainders[remainder]) {
                remainders[remainder] = true;
                count++;
            }
        }

        System.out.println(count);
        scanner.close();
    }
}

 

내가 chat gpt를 활용해 만든 정답은 위의 코드와 같다. 

 Scanner scanner = new Scanner(System.in);
        boolean[] remainders = new boolean[42];
        int count = 0;

 

우선 값들을 나누면 0~41까지의 값이 나올 수 있다.

처음에 boolean 배열을 만들면 false로 채워져 있기 때문에 0~41 인덱스의 값들은 모두 false이다. 

 

for (int i = 0; i < 10; i++) {
            int number = scanner.nextInt();
            int remainder = number % 42;

            if (!remainders[remainder]) {
                remainders[remainder] = true;
                count++;
            }
        }

 

그리고 사용자로부터 10개의 숫자를 입력받는다.

remainder에는 사용자가 입력한 값을 42로 나눈 나머지가 들어간다.

 

만약에 remainders[remainder]의 값이 true가 아니라면, 즉 false라면 값을 true로 바꿔준다.

쉽게 얘기하자면 예를 들어, remainder가 0일 경우, remainders[0], 즉, 0이 나머지인 값이 없었다면 true로 반환한다. 

그 후 count의 값을 +1 해준다. 

조건문 if를 탔을 때, remainders[0]의 값은 true가 된다. 

 

만약 그 다음 숫자를 42로 나누었을 때 0이라면, if(!remainders[remainder])을 통과하지 못한다.

왜냐하면, remainders[0]의 값은 이미 true이기 때문에 if문을 타지 못하고 빠져나간다.

 

결론적으로, count의 값은 다른 숫자인 경우에만 +1을 하게 된다.

 

문제 10811

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

 

---

문제 10811번은 바구니를 역순으로 뒤집는 것이다.

우선 N, M 값을 입력받는다.

 

여기에서 N = 바구니의 갯수, M = 역순으로 바꿀 횟수, 줄의 수이다.

 

그 다음에는 i, f 값을 입력받는다. 여기에서 i = 역순으로 바꿀 첫 번째 인덱스, j = 역순으로 바꿀 마지막 인덱스이다.

즉 총 N개의 바구니 중 i~j의 M개의 줄을 M번 역순으로 바꿔서 나오는 결과를 출력하는 것이다. 

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  
        int M = scanner.nextInt();  
        
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i + 1;  
        }

        for (int i = 0; i < M; i++) {
            int a = scanner.nextInt() - 1;  
            int b = scanner.nextInt() - 1;  
            for (int j = a; j <= a + (b - a) / 2; j++) {
                int temp = arr[j];
                arr[j] = arr[b - (j - a)];
                arr[b - (j - a)] = temp;
            }
        }

        // 결과 출력
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }

        scanner.close();
    }
}

 

전체 코드는 위와 같다.

 

Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  
        int M = scanner.nextInt();  
        
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i + 1;  
        }

 

우선 사용자로부터 바구니의 갯수인 N과, 줄의 수이면서 역순으로 바꿀 횟수인 M을 입력받는다.

그리고, N개의 바구니이기 때문에, 크기가 N인 정수 배열을 만든다.

 

바구니를 넣을 공간을 생성했으니, 본격적으로 값을 넣어줘야 한다.

배열에는 i+1 값이 들어가는데, 이유는 바구니는 +1된 값이기 때문이다.

 

예를 들어, 0번 인덱스는 첫 번째 바구니고, 첫 번째 바구니는 1이다. 

따라서 +1을 해주어야 한다.

 

 for (int i = 0; i < M; i++) {
            int a = scanner.nextInt() - 1;  
            int b = scanner.nextInt() - 1;  
            for (int j = a; j <= a + (b - a) / 2; j++) {
                int temp = arr[j];
                arr[j] = arr[b - (j - a)];
                arr[b - (j - a)] = temp;
            }
        }

 

이 부분이 가장 중요한 부분이다. 

10811번 문제를 찾아보니 풀이방식이 다르던데, 나는 내 코드에서의 오류만 수정하고 싶어 조금 복잡하게 구성했다.

 

우선 사용자로부터 a와 b를 M번 입력받는다.

그 다음 -1을 해주는데, 바구니는 인덱스 번호보다 +1된 값이기 때문이다.

 

 

그리고 j=a부터, j<= a + (b - a) / 2까지 반복해준다.

여기서 의문이 생길 것이다. 

왜 하필 a + (b - a) / 2일까?

 

우리는 1 2 3 4 5 를 역순으로 바꿀 때, 1과 5, 2와 4를 바꾼다.

즉, 전체 값 중에서 2까지만 바꾸면 된다. 

그 이후로 4나 5는 이미 한 번 바뀌었기 때문에 바꿀 필요가 없다.

 

2는 (b - a) / 2인 위치에 있는 값이다. 

a~b까지의 숫자를 바꾸기 때문에, 중간의 수는 (b-a)/2이다. 

우리는 1 2 3 4 5를 배열로 설정했으므로, (4-0)/2 -> 즉 전체값에서 두 번째에 있는 수까지 바꾸면 된다.

 

하지만, 그것이 위치이지, 인덱스를 나타내는 것은 아니다. 

예를 들어 3 4 5를 역순으로 바꾼다고 생각해보자.

그러면 a = 3 - 1 = 2이고, b = 5 - 1 = 4가 된다.

(4-2)/2 = 1이다. 따라서 첫 번째라는 의미이다.

하지만 우리는 1번 인덱스를 갖고 있지 않다. 1번 위치의 인덱스는 있다.

따라서 a를 더해주어야 한다.  a로부터 얼마만큼 떨어져있는지 알기 위해서이다. 

우리가 설정한 a는 2이기 때문에 +1해주면 3이 된다.

그래서 우리가 원하는 3이라는 인덱스가 도출된다. 

 

 

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

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i + 1; // 배열은 0부터 시작하기 떄문에 arr[0]에 1을 넣기 위해 1을 더해줌
        }

        for (int i = 0; i < M; i++) { // M개의 줄
            int left = sc.nextInt() - 1; // 배열 0부터 시작
            int right = sc.nextInt() - 1;

            while (left < right) {
                int temp = arr[left];
                arr[left++] = arr[right];
                arr[right--] = temp;
            }
        }
        sc.close();

        for (int baguni:arr)
            System.out.print(baguni + " ");
    }
}

 

더 간단한 코드는 바로 이것이다.

 for (int i = 0; i < M; i++) { // M개의 줄
            int left = sc.nextInt() - 1; // 배열 0부터 시작
            int right = sc.nextInt() - 1;

            while (left < right) {
                int temp = arr[left];
                arr[left++] = arr[right];
                arr[right--] = temp;
            }
        }

 

나머지는 동일하기 때문에 이 부분만 설명해보겠다.

우선 left와 right는 아까의 a, b라고 생각하면 된다.

 

사용자로부터 입력받는 숫자는 바구니를 나타내기 때문에 1을 빼주어야 한다.

그리고 left가 right보다 작을 때까지, 

즉 바꾼 숫자를 또 바꾸지 않기 위한 조건을 설정해준다.

 

temp에 left 값을 넣어주고, left는 1 증가시키고, right는 1 감소시키며 위치를 바꿔준다.

예를 들어서 1 2 3 4 5라고 가정해보자.

그러면 0 1 2 3 4 가 되고, a는 0, b는 4가 된다.

 

temp = arr[0];
arr[0] = arr[4];
arr[4] = temp;

4 1 2 3 0

temp = arr[1];
arr[1] = arr[3];
arr[3] = temp;

4 3 2 1 0

temp = arr[2];
arr[2] = arr[2];
arr[2] = temp;

4 3 2 1 0

 

이 다음부터는 left 값이 3이 되고, right 값이 1이 되어 값이 역전된다.

 

생각해보면, 첫 번째 값은 마지막 값, 두 번째 값은 그거보다 1 작은 값, 이렇게 정확한 규칙이 있었는데 조금 어렵게 푼 느낌이다. 

 

앞으로는 시간복잡도가 적은 알고리즘을 짜도록 더 생각해보아야겠다.