Chapter 8. Multidimensional Arrays(1)[Java Basic]

8.A - 한주에 얼마나 일하나?

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

요일별 직원들의 작업시간이 2차 배열에 들어 있다. 배열의 매 행에는 직원의 일주일 작업시간이 열로 구분되어 저장되어 있다. 예를 들어, 8명의 직원의 작업시간은 다음 그림처럼 저장된다. 여러분은 각 직원의 작업시간을 입력 받아서 한 주 동안 가장 많이 일한 직원부터 내림차순으로 출력하는 프로그램을 작성해야 한다.

Suppose the weekly hours for all employees are stored in a two-dimensional array. Each row records an employee's seven-day work hours with seven columns. For example, the following array stores the work hours for eight employees. Write a program that displays employees and their total hours in decreasing order of the total hours.

모든 학생이 해당 놀이를 하면서 학교에 들어갔다고 했을때, 어떤 사물함이 열려 있고 닫혀있는지 찾아내는 프로그램을 작성해보자.

After all the students have passed through the building and changed the lockers, which lockers are open? Write a program to find your answer.

 

INPUT

* Line 1 : 직원수 N (1~100)

* Line 2 ~ N+1 : 이름 시간1 시간2 시간3 시간4 시간5 시간6 시간7

- 이름: 공백을 포함하지 않은 문자열이며 길이는 100을 넘지 않는다

- 시간1~7: 정수 (0~24)

 

OUTPUT

* Line 1 ~ N : 이름 시간의_합

- 시간의 합이 같다면 순서는 이름이 입력된 순서를 따른다.

 

SAMPLE INPUT

8

Employee0 2 4 3 4 5 8 8

Employee1 7 3 4 3 3 4 4

Employee2 3 3 4 3 3 2 2

Employee3 9 3 4 7 3 4 1

Employee4 3 5 4 3 6 3 8

Employee5 3 4 4 6 3 4 4

Employee6 3 7 4 8 3 8 4

Employee7 6 3 5 9 2 7 9

 

SAMPLE OUTPUT

Employee7 41

Employee6 37

Employee0 34

Employee4 32

Employee3 31

Employee1 28

Employee5 28

Employee2 20

 

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), i, j, data[] = new int[n], sort[] = new int[n + 1];
        String name[] = new String[n];
        for(i = 0; i < n; i++){
            name[i] = input.next();
            for(j = 0; j < 7; j++)
                data[i] += input.nextInt();
            sort[i] = data[i];
        }
        Arrays.sort(sort);
        for(i = n; i > 0; i--)
            for(j = 0; j < n; j++)
                if(sort[i] == data[j] && sort[i] != sort[i - 1])
                    System.out.println(name[j] + " " + sort[i]);
    }
}

 

 

8.B - 대수: 행렬 곱1

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

행렬a와 행렬b를 곱하기 위해서는 행렬a의 열의 개수와 행렬b의 행의 개수가 일치 해야하고, 두 행렬의 각각의 원소는 동일한 자료형을 가져야 한다. 행렬c를 행렬a와 행렬b를 곱해서 만든 행렬이라고 하자. 행렬a의 열의 개수를 n이라면 행렬c의 ij원소는 ai1 * b1j + ai2 * b2j + ... + ain * bnj 이다.

To multiply matrix a by matrix b, the number of columns in a must be the same as the number of rows in b, and the two matrices must have elements of the same or compatible types. Let c be the result of the multiplication. Assume the column size of matrix a is n. Each element cij is ai1 * b1j + ai2 * b2j + ... + ain * bnj.

여러분은 두개의 3*3 행렬을 입력으로 받아, 두 행렬을 곱한 새로운 행렬을 구해야 한다.

Write a test program that prompts the user to enter two 3 * 3 matrices and displays their product.

 

INPUT

* Line 1 ~ 3 : 첫번째 행렬의 행 (공백으로 구분된 3개의 원소)

* Line 4 ~ 6 : 두번째 행렬의 행 (공백으로 구분된 3개의 원소)

- 모든 행렬의 원소는 정수이며 범위는 -1,000~1,000

 

OUTPUT

* Line 1 ~ 3 : 곱해진 행렬의 행 (행의 원소를 공백으로 구분해 출력)

 

SAMPLE INPUT

1 2 3

3 2 1

2 1 3

4 5 6

6 5 4

4 6 5

 

SAMPLE OUTPUT

28 33 29

28 31 31

26 33 31

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int i, j, k, data[][][] = new int[3][3][3];
        for(i = 0; i < 2; i++)
            for(j = 0; j < 3; j++)
                for(k = 0; k < 3; k++)
                    data[i][j][k] = input.nextInt();
        for(i = 0; i < 3; i++)
            for(j = 0; j < 3; j++)
                for(k = 0; k < 3; k++)
                    data[2][j][i] += data[0][j][k] * data[1][k][i];
        for(i = 0; i < 3; i++)
            System.out.println(data[2][i][0] + " " + data[2][i][1] + " " + data[2][i][2]);
    }
}

 

 

8.C - 대수: 행렬 곱2 (난이도:고급)

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

n개의 행렬을 서로 곱할때는 곱하는 순서에 따라 곱셈의 횟수가 달라지곤 한다. 예를 들어 행렬 A의 크기가 10 × 30 이고, 행렬 B의 크기가 30 × 5 이고, 행렬 C의 크기가 5 × 60 라고 하자. (AB)C와 A(BC)를 계산하는데 필요한 곱셈의 횟수는 다음과 같다.

 

- (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500

- A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

여러분은 n개의 행렬의 크기를 입력받아, n개의 행렬을 모두 곱하는데 필요한 곱셈의 최소 횟수를 구하는 프로그램을 작성해야한다.

 

INPUT

* Line 1 : 행렬의 개수 n (1~1,000)

* Line 2 ~ n+1 : 행의_개수 열의_개수

- 모든 개수는 정수이며 범위는 1~1,000

입력으로 주어지는 순서로 곱하려는 상황이고,

 

i번째 행렬의 열의 개수와

 

i+1번째 행렬의 행의 개수는 같다.

 

OUTPUT

* Line 1 : 필요한 곱셈의 최소 회수

 

SAMPLE INPUT

4

40 20

20 30

30 10

10 30

 

SAMPLE OUTPUT

26000

 

 

D - 정렬된 두배열에서 가장 가까운 쌍 (난이도:고급)

DESCRIPTION

입력으로 정렬된 배열 A, B와 숫자x가 주어졌을때, x와 가장 가까운 값을 가지는 A[i] + B[j]를 찾는 프로그램을 만드세요.

 

INPUT

* Line 1 : 배열A크기 배열B크기 숫자x

- 배열A크기, 배열B크기, 숫자x: 1~1,000,000 범위의 정수

* Line 2 : 공백으로 구분된 배열A의 자연수 원소

* Line 3 : 공백으로 구분된 배열B의 자연수 원소

 

OUTPUT

* Line 1 : x와 가장 가까운 값을 가지는 A[i] + B[j]의 차(절댓값)

 

SAMPLE INPUT

4 4 30

1 4 5 7

10 20 30 40

 

SAMPLE OUTPUT

1

 

Time Limit Exceed 0
        Scanner input = new Scanner(System.in);
        int sa = input.nextInt(), sb = input.nextInt(), n = input.nextInt(), data1[] = new int[sa], data2[] = new int[sb], i, j, min = Integer.MAX_VALUE;
        for(i = 0; i < sa; i++)
            data1[i] = input.nextInt();
        for(i = 0; i < sb; i++)
            data2[i] = input.nextInt();
        for(i = 0; i < sa; i++)
            for(j = 0; j < sb; j++)
                if(Math.abs(data1[i] + data2[j] - n) < min)
                    min = Math.abs(data1[i] + data2[j] - n);
        System.out.println(min);

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int sa = input.nextInt(), sb = input.nextInt(), n = input.nextInt(), data1[] = new int[sa], data2[] = new int[sb], i, j, ia = 0, ib = sb - 1, min = Integer.MAX_VALUE;
        for(i = 0; i < sa; i++)
            data1[i] = input.nextInt();
        for(i = 0; i < sb; i++)
            data2[i] = input.nextInt();
        while(ia < sa && ib >= 0 && min != 0){
            if(Math.abs(data1[ia] + data2[ib] - n) < min){
                min = Math.abs(data1[ia] + data2[ib] - n);
            }
            if(data1[ia] + data2[ib] > n)
                ib--;
            else
                ia++;
        }
        System.out.println(min);
    }
}

반응형

 

8.E - 2차배열 정렬

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

2차 배열을 오름차순으로 정렬해서 출력하는 프로그램을 만드세요. 먼저 첫번째 원소로 오름차순으로 정렬하고, 만약 동일한 첫번째 원소를 가질 경우 두번째 원소로 오름차순으로 정렬해야 합니다. Write a program to sort a two-dimensional array. The program performs a primary sort on rows and a secondary sort on columns.

 

예를 들어 다음과 같은 2차배열이 입력으로 들어온다면 For example, the following array

{{4, 2},{1, 7},{4, 5},{1, 2},{1, 1},{4, 1}}

다음과 같이 정렬되어야 합니다. will be sorted to

{{1, 1},{1, 2},{1, 7},{4, 1},{4, 2},{4, 5}}.

 

INPUT

* Line 1 : 배열의 크기 N (1~100)

* Line 2 ~ N+1 : 첫번째원소 두번째원소 (각각 int범위의 정수)

 

OUTPUT

* Line 1 ~ N : 정렬된 배열의 원소

 

SAMPLE INPUT

6

4 2

1 7

4 5

1 2

1 1

4 1

 

SAMPLE OUTPUT

1 1

1 2

1 7

4 1

4 2

4 5

 

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), i, j, k, temp, count, data[][] = new int[n][2], sort1[] = new int[n];
        for(i = 0; i < n; i++){
            sort1[i] = data[i][0] = input.nextInt();
            data[i][1] = input.nextInt();
        }
        Arrays.sort(sort1);
        for(i = 0; i < n;){
            k = 0; count = 0; temp = sort1[i];
            for(j = 0; j < n; j++)
                if(temp == data[j][0])
                    count++;
            int sort2[] = new int[count];
            for(j = 0; j < n; j++)
                if(temp == data[j][0])
                    sort2[k++] = data[j][1];
            Arrays.sort(sort2);
            for(j = 0; j < k; j++)
                System.out.println(temp + " " + sort2[j]);
            while(++i < n && sort1[i] == temp);
        }
    }
}

Wrong Answer
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), i;
        String data[] = new String[n];
        input.nextLine();
        for(i = 0; i < n; i++)
            data[i] = input.nextLine();
        Arrays.sort(data);
        for(i = 0; i < n; i++)
            System.out.println(data[i]);
    }
}

 

 

8.F - 금융 쓰나미

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

전 세계 은행들은 서로 돈을 빌려주고 받아 왔습니다. 그러다 경제적으로 힘든 시기에는 은행이라도 파산할 수 있는데, 파산한 은행에 대출된 금액은 누구도 돌려 받을 수 없습니다. 은행의 총 자산은 현재 자산 + 다른 은행에 대출해준 자산으로 계산합니다(이 때 자은행에 대출한 것도 포함합니다). 아래 그림에는 문제의 다섯 은행이 보입니다. 이들 은행의 현재 자산은 25, 125, 175, 75, 181백만$ 입니다. 그림에서 보여지는 노드1에서 노드2로의 직선은, 은행1이 은행2에게 40백만$를 대출해 주었음을 나타냅니다.

Banks lend money to each other. In tough economic times, if a bank goes bankrupt, it may not be able to pay back the loan. A bank’s total assets are its current balance plus its loans to other banks. The diagram in Figure 8.8 shows five banks. The banks’ current balances are 25, 125, 175, 75, and 181 million dollars, respectively. The directed edge from node 1 to node 2 indicates that bank 1 lends 40 million dollars to bank 2.

만약 은행의 총 자산이 어떤 제한금액보다 낮아지게 되면, 은행은 불안전해 집니다. 또한 불안전해진 은행에 돈을 대출해준 은행들은 대출해준 금액만큼 총 자산이 낮아지게 됩니다. 결과적으로, 안전했던 은행이라도 연쇄적인 총 자산의 감소로 인해 불안전해 질 수 있습니다.

여러분은 모든 불안전한 은행을 찾아내는 프로그램을 작성해야 합니다. 프로그램의 입력은 다음과 같습니다. 첫번째 줄은 은행의 수 N과 제한금액 L입니다. 그 다음 N개의 줄에는 각 은행의 자산 정보가 있습니다(은행의 번호는 0부터 N-1까지 입니다) . 각 은행의 자산 정보의 첫번째 항목은 현재 자산입니다. 두번째 항목은 대출해준 은행의 수 B 입니다. 다음 B개의 쌍은 대출 은행과 그 금액입니다. 예를 들어, 위 그림을 입력으로 변환하면 다음과 같습니다. (L은 201로 가정합니다)

If a bank’s total assets are under a certain limit, the bank is unsafe. The money it borrowed cannot be returned to the lender, and the lender cannot count the loan in its total assets. Consequently, the lender may also be unsafe, if its total assets are under the limit. Write a program to find all the unsafe banks. Your program reads the input as follows. It first reads two integers N and limit L, where N indicates the number of banks and L is the minimum total assets for keeping a bank safe. It then reads N lines that describe the information for N banks with IDs from 0 to N-1. The first number in the line is the bank’s balance, the second number indicates the number B of banks that borrowed money from the bank, and the rest are pairs of two numbers. Each pair describes a borrower. The first number in the pair is the borrower’s ID and the second is the amount borrowed. For example, the input for the five banks in Figure 8.8 is as follows (note that the limit is 201):

 

5 201 25 2 1 100.5 4 320.5 125 2 2 40 3 85 175 2 0 125 3 75 75 1 0 125 181 1 2 125

은행3의 총자산은 75+125=200 이고 201(=L)보다 작으므로, 불안전한 은행입니다. 은행3이 불안전해 졌으므로, 은행1의 총자산은 125+40=165로 감소되고, 마찬가지로 불안전한 은행이 됩니다. 따라서 프로그램은 불안전한 은행으로 은행3과 은행1을 찾아낼 수 있어야 합니다.

 

The total assets of bank 3 are (75 + 125), which is under 201, so bank 3 is unsafe. After bank 3 becomes unsafe, the total assets of bank 1 fall below (125 + 40). Thus, bank 1 is also unsafe. The output of the program should be Unsafe banks are 3 1

 

INPUT

* Line 1 : 은행의수N 제한금액L (N:1~100범위의 정수)

* Line 2~N+1 : 현재자산 대출해준은행수B {대출은행 대출금액}*B

- 제한금액, 현재자산, 대출금액은 1~1,000 범위의 실수

 

OUTPUT

* Line 1 : 불안전한 은행의 번호를 오름차순으로 공백으로 구분해 출력

SAMPLE INPUT

5 201

25 2 1 100.5 4 320.5

125 2 2 40 3 85

175 2 0 125 3 75

75 1 0 125

181 1 2 125

 

SAMPLE OUTPUT

1 3

 

HINT

Use a two-dimensional array borrowers to represent loans. borrowers[i][j] indicates the loan that bank i loans to bank j. Once bank j becomes unsafe, borrowers[i][j] should be set to 0.

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), l = input.nextInt(), i, j, k, t;
        double data[][] = new double[n][n * 2 + 2];
        for(i = 0; i < n; i++){
            data[i][0] = input.nextDouble();
            data[i][1] = input.nextDouble();
            for(j = 0; j < data[i][1] * 2; j += 2){
                data[i][j + 2] = input.nextDouble();
                data[i][j + 3] = input.nextDouble();
                data[i][0] += data[i][j + 3];
            }
            for(j = 0; j <= i; j++){
                if(data[j][0] < l){
                    for(k = 0; k < n; k++){
                        for(t = 0; t < data[k][1] * 2; t += 2){
                            if(data[k][t + 2] == j){
                                data[k][0] -= data[k][t + 3];
                                data[k][t+3] = 0;
                            }
                        }
                    }
                }
            }
        }
        j = 0;
        for(i = 0; i < n; i++){
            if(data[i][0] < l){
                if(j == 0){
                    System.out.print(i);
                    j++;
                }
                else System.out.print(" " + i);
            }
        }
    }
}

 

 

8.G - 패턴: 연속적으로 4번 반복된 수

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

2차원 배열을 입력으로 받아 배열안에 수평, 수직, 대각선으로 동일한 숫자가 연속적으로 4번 반복되는 경우가 몇번 있는지 찾아내는 프로그램을 작성하세요. 아래 그림은 동일한 숫자가 연속적으로 4번 반복되는 경우의 예를 보여주고 있습니다. (동일 숫자가 서로 다른 연속에 포함 될 수 있으므로 주의해야 합니다. 예를 들어 연속적으로 6번 반복된 수가 있을 경우, 숫자의 4번 반복은 +3으로 계산해야합니다)

Write a test program that prompts the user to enter the number of rows and columns and a two-dimensional array and then displays the number of four consecutive numbers with the same value, either horizontally, vertically, or diagonally. Here are some examples of the four consecutive numbers.

INPUT

* Line 1 : 행의수N 열의수M (N, M은 4~100범위의 정수)

* Line 2 ~ N+1 : 공백으로 구분된 M개의 원소 (원소는 0~9 범위의 정수)

 

OUTPUT

* Line 1 : 동일한 숫자가 연속적으로 4번 반복되는 경우의 수

 

SAMPLE INPUT

5 5

0 0 0 0 0

2 3 0 2 9

3 6 6 0 9

7 7 3 0 0

6 3 8 8 7

 

SAMPLE OUTPUT

3

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), m = input.nextInt(), i, j, data[][] = new int[n][m], count = 0;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                data[i][j] = input.nextInt();
 
        for(i = 0; i < n || i == 0; i++){
            for(j = 0; j < m || j == 0; j++){
                if(j < m - 3)
                    if(data[i][j] == data[i][j+1] && data[i][j] == data[i][j+2]&& data[i][j] == data[i][j+3])
                        count++;
                if(i < n - 3)
                    if(data[i][j] == data[i+1][j] && data[i][j] == data[i+2][j]&& data[i+3][j] == data[i][j])
                        count++;
                if(i < n - 3 && j < m - 3)
                    if(data[i][j] == data[i+1][j+1] && data[i][j] == data[i+2][j+2]&& data[i][j] == data[i+3][j+3])
                        count++;
                if(i >= 3 && j < m - 3)
                    if(data[i][j] == data[i-1][j+1] && data[i][j] == data[i-2][j+2]&& data[i][j] == data[i-3][j+3])
                        count++;
            }
        }
        System.out.println(count);
    }
}