Chapter 10. Object-Oriented Thinking(2)[Java Basic]

10.D - 큐 클래스

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

정수를 저장하는 큐(Queue) 클래스를 만들어 보자. 복수의 원소를 유지한다는 점에서 스택과 큐는 유사하지만, 입력과 출력에서는 서로 다른 접근 방법을 취한다. 스택이 나중에 도착한 원소를 먼저 출력한다면, 큐는 먼저 입력된 원소를 먼저 출력한다. 여러분이 생성할 큐 클래스는 다음 내용을 포함해야 한다.

큐 안의 int값들을 저장하는 int[]형의 elements 필드를 가진다.

큐 안의 elements의 수를 저장하는 size 필드를 가진다.

배열 크기가 8인 큐를 만드는 생성자를 가진다.

큐 안으로 v를 넣는 enqueue(int v) 메소드를 가진다.

큐에서 element를 반환하고 제거하는 dequeue() 메소드를 가진다.

만약 큐가 비어있으면 true를 반환하는 empty()메소드를 가진다.

큐의 크기를 반환하는 getSize() 메소드를 가진다.

Section 10.6 gives a class for Stack. Design a class named Queue for storing integers. Like a stack, a queue holds elements. In a stack, the elements are retrieved in a last-in first-out fashion. In a queue, the elements are retrieved in a first-in first-out fashion. The class contains:

An int[] data field named elements that stores the int values in the queue.

A data field named size that stores the number of elements in the queue.

A constructor that creates a Queue object with default capacity 8.

The method enqueue(int v) that adds v into the queue.

The method dequeue() that removes and returns the element from the queue.

The method empty() that returns true if the queue is empty.

The method getSize() that returns the size of the queue.

 

INPUT

큐 클래스의 테스트를 위해서 첫째 줄에는 입력의 개수 N이 들어온다. 둘째 줄 부터는 N개의 정수가 입력으로 들어 온다. -1이 입력으로 들어올 경우 dequeue를 수행하고, 그외의 수는 큐에 enqueue 수행 한다.

* Line 1 : 명령의개수 N (1~1,000)

* Line 2 ~ N+1 : 정수형의 데이터 (-1~1,000)

 

OUTPUT

큐에 남아 있는 원소를 Sample Output의 형태로 순서대로 출력한다.

 

SAMPLE CODE

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

        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int n = sc.nextInt();
            if (n == -1) {
                if (!queue.empty()) queue.dequeue();
            } else {
                queue.enqueue(n);
            }
        }
        while (!queue.empty())
            System.out.println(queue.dequeue());
    }
}

 

YOUR_CODE

 

SAMPLE INPUT

6

5

-1

-1

2

3

4

 

SAMPLE OUTPUT

2

3

4

 

class Queue{
    private int size = 0;
    private int elements[] = new int[10000];
    public void enqueue(int v){
        elements[size++] = v;
    }
    public int dequeue(){
        int i, copy = elements[0];size--;
        for(i = 0; i < size; i++)
            elements[i] = elements[i + 1];
        return copy;
    }
    public boolean empty(){
        if(getSize() == 0)
            return true;
        return false;
    }
    public int getSize(){
        return size;
    }
}

 

 

10.E - 기하: Triangle2D 클래스

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

다음 내용을 포함하는 Triangle2D 클래스를 만들어보자.

MyPoint형의 세 점 p1, p2, p3필드를 설정하고 반환하는 메소드를 가진다. MyPoint 타입은 Programming Exercise 10.4에 정의되어있습니다.

세 점의 좌표를 각각 (0, 0), (1, 1), (2, 5)로 가지는 default 삼각형을 만드는 무(無)인자(no-arg) 생성자를 가진다.

특정한 좌표를 가지는, 삼각형을 만드는 생성자를 가진다.

삼각형의 넓이를 반환하는 getArea() 메소드를 가진다.

삼각형의 둘레를 반환하는 getPerimeter() 메소드를 가진다.

특정한 점 p가 이 삼각형 안에 있으면 true를 반환하는 contains(MyPoint p) 메소드를 가진다. (Figure 10.22a)

특정한 삼각형이 이 삼각형 안에 있으면 true를 반환하는 contains(Triangle2D t) 메소드를 가진다. (Figure 10.22b)

특정한 삼각형이 이 삼각형과 겹치면 true를 반환하는 overlaps(Triangle2D t) 메소드를 가진다. (Figure 10.22c)

Three points named p1, p2, and p3 of the type MyPoint with getter and setter methods. MyPoint is defined in Programming Exercise 10.4.

A no-arg constructor that creates a default triangle with the points (0, 0), (1, 1), and (2, 5).

A constructor that creates a triangle with the specified points.

A method getArea() that returns the area of the triangle.

A method getPerimeter() that returns the perimeter of the triangle.

A method contains(MyPoint p) that returns true if the specified point p is inside this triangle (see Figure 10.22a).

A method contains(Triangle2D t) that returns true if the specified triangle is inside this triangle (see Figure 10.22b).

A method overlaps(Triangle2D t) that returns true if the specified triangle overlaps with this triangle (see Figure 10.22c).

여러분이 작성한 코드는 아래 샘플코드의 YOUR_CODE 부분에 들어가 컴파일 됩니다.

 

INPUT

* Line 1 : 테스트케이스 T (1~1,000)

* Line 2 ~ T+1 : x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x7 y7 (공백으로 구분된 14개의 실수)

- 실수의 범위는 -100 ~ 100

- x1 y1 x2 y2 x3 y3는 삼각형 r1의 정점

- x4 y4 x5 y5 x6 y6는 삼각형 r2의 정점

- x7 y7는 정점 p

- r1과 r2는 항상 삼각형

 

OUTPUT

* Line 1 ~ 4T : 각 테스트 케이스마다 샘플 출력과 같이 4줄씩 출력

- Line 3 : r1이 p를 포함하면 true 아니라면 false

- Line 4 : r1이 r2를 포함하면 contain, r1와 r2가 겹치면 overlaps, 만나지 않는다면 no overlap을 출력

 

SAMPLE INPUT

3

-2 0 0 2 2 0 -1 0 0 1 1 0 2 0

-1 0 0 1 1 0 -2 0 0 2 2 0 2 0

-2 0 0 2 2 0 -1 -1 0 -2 1 -1 –1 1

 

SAMPLE CODE

import javafx.geometry.*;
import java.awt.geom.Line2D;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            double x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6, x7, y7;
            x1 = sc.nextDouble();
            y1 = sc.nextDouble();
            x2 = sc.nextDouble();
            y2 = sc.nextDouble();
            x3 = sc.nextDouble();
            y3 = sc.nextDouble();
            x4 = sc.nextDouble();
            y4 = sc.nextDouble();
            x5 = sc.nextDouble();
            y5 = sc.nextDouble();
            x6 = sc.nextDouble();
            y6 = sc.nextDouble();
            x7 = sc.nextDouble();
            y7 = sc.nextDouble();
            Triangle2D r1 = new Triangle2D(x1, y1, x2, y2, x3, y3);
            Triangle2D r2 = new Triangle2D(x4, y4, x5, y5, x6, y6);

            System.out.printf("Area is %.1f\n", r1.getArea());
            System.out.printf("Perimeter is %.1f\n", r1.getPerimeter());
            System.out.println(r1.contains(x7, y7));
            if (r1.contains(r2)) {
                System.out.println("contain");
            } else if (r1.overlaps(r2)) {
                System.out.println("overlaps");
            } else {
                System.out.println("no overlap");
            }
        }
    }
}

YOUR_CODE

 

SAMPLE OUTPUT

Area is 4.0

Perimeter is 9.7

true

contain

Area is 1.0

Perimeter is 4.8

false

overlaps

Area is 4.0

Perimeter is 9.7

true

no overlap

 

class MyPoint{
    double x, y;
    MyPoint(double ix, double iy){
        x = ix;
        y = iy;
    }
}
class Triangle2D{
    MyPoint[] p = new MyPoint[3];
    Line2D.Double[] l = new Line2D.Double[3];
    Triangle2D(double x1, double y1, double x2, double y2, double x3, double y3){
        p[0] = new MyPoint(x1, y1);
        p[1] = new MyPoint(x2, y2);
        p[2] = new MyPoint(x3, y3);
        l[0] = new Line2D.Double(x1, y1, x2, y2);
        l[1] = new Line2D.Double(x2, y2, x3, y3);
        l[2] = new Line2D.Double(x3, y3, x1, y1);
    }
    Triangle2D(){
        p[0] = new MyPoint(0, 0);
        p[1] = new MyPoint(1, 1);
        p[2] = new MyPoint(2, 5);
    }
    public double getArea(){
        return Math.abs(p[0].x * p[1].y + p[1].x * p[2].y + p[2].x * p[0].y - p[1].x * p[0].y - p[2].x * p[1].y - p[0].x * p[2].y) / 2;
    }
    public double getPerimeter(){
        return Math.pow(Math.pow(p[0].x - p[1].x, 2) + Math.pow(p[0].y - p[1].y, 2),0.5) + Math.pow(Math.pow(p[1].x - p[2].x, 2) + Math.pow(p[1].y - p[2].y, 2),0.5) + Math.pow(Math.pow(p[2].x - p[0].x, 2) + Math.pow(p[2].y - p[0].y, 2),0.5);
    }
    public boolean contains(double ix, double iy) {
        double a = (l[0].ptLineDist(ix, iy) * Math.pow(Math.pow(p[0].x - p[1].x, 2) + Math.pow(p[0].y - p[1].y, 2),0.5) + l[1].ptLineDist(ix, iy) * Math.pow(Math.pow(p[1].x - p[2].x, 2) + Math.pow(p[1].y - p[2].y, 2),0.5) + l[2].ptLineDist(ix, iy) * Math.pow(Math.pow(p[2].x - p[0].x, 2) + Math.pow(p[2].y - p[0].y, 2),0.5)) / 2;
        if(a >= getArea() - 0.0001 && a <= getArea() + 0.0001) // a == getArea() or Double.compare : error 완전히 똑같은 값이 아닐 수 있음.
            return true;
        return false;
    }
    public boolean contains(Triangle2D t){
        if(contains(t.p[0].x, t.p[0].y) && contains(t.p[1].x, t.p[1].y) && contains(t.p[2].x, t.p[2].y))
            return true;
        return false;
    }
    public boolean overlaps(Triangle2D t){
        Line2D.Double tl[] = new Line2D.Double[3];
        tl[0] = new Line2D.Double(t.p[0].x, t.p[0].y, t.p[1].x, t.p[1].y);
        tl[1] = new Line2D.Double(t.p[1].x, t.p[1].y, t.p[2].x, t.p[2].y);
        tl[2] = new Line2D.Double(t.p[2].x, t.p[2].y, t.p[0].x, t.p[0].y);
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++)
                if(l[i].intersectsLine(tl[j]))
                    return true;
        }
        return false;
    }
}

 

 

10.F - 기하: 바운딩 사각형

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

좌표축에 정렬된 바운딩 사각형은 2차 좌표계의 n개의 점이 주어졌을때, 사각형의 각 변이 X와 Y축에 평행하면서 주어진 n개의 점을 포함하는 최소 크기의 사각형을 말한다. 2차 좌표계의 n개의 점이 주어졌을 때 그림 10.24d에 보이는 것처럼 바운딩 사각형을 구하는 프로그램을 만들어 보자.

A axis-aligned bounding rectangle is the minimum rectangle that encloses a set of points in a two-dimensional plane, as shown in Figure 10.24d.

 

INPUT

* Line 1 : 점의개수 N (1~1,000)

* Line 2 ~ N+1 : 점의 x y 좌표 (공백으로 구분된 2개의 실수)

 

OUTPUT

* Line 1 : 샘플 출력처럼 사각형의 중심을 출력

* Line 2 : 샘플 출력처럼 사각형의 width와 height를 출력

 

SAMPLE CODE

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double[][] points = new double[N][2];
        for (int i = 0; i < N; i++) {
            points[i][0] = sc.nextDouble();
            points[i][1] = sc.nextDouble();
        }
        MyRectangle2D boundingRectangle = MyRectangle2D.getRectangle(points);
        System.out.printf("x, y: %.1f, %.1f\n", boundingRectangle.getX(), boundingRectangle.getY());
        System.out.printf("w, h: %.1f, %.1f\n", boundingRectangle.getWidth(), boundingRectangle.getHeight());
    }
}

YOUR_CODE

 

SAMPLE INPUT

3

3 1

-5 -5

0 7

 

SAMPLE OUTPUT

x, y: -1.0, 1.0

w, h: 8.0, 12.0

 

class MyRectangle2D{
    double maxX, minX, maxY, minY;
    MyRectangle2D(){}
    public static MyRectangle2D getRectangle(double[][] p){
        MyRectangle2D m = new MyRectangle2D();
        m.maxX = m.minX = p[0][0]; m.maxY = m.minY = p[0][1];
        for(int i = 1; i < p.length; i++){
            if(m.maxX < p[i][0])
                m.maxX = p[i][0];
            if(m.minX > p[i][0])
                m.minX = p[i][0];
            if(m.maxY < p[i][1])
                m.maxY = p[i][1];
            if(m.minY > p[i][1])
                m.minY = p[i][1];
        }
        return m;
    }
    public double getX(){
        return (maxX + minX) / 2;
    }
    public double getY(){
        return (maxY + minY) / 2;
    }
    public double getWidth(){
        return maxX - minX;
    }
    public double getHeight(){
        return maxY - minY;
    }
}

 

10.G - 100019로 나누어지 떨어지는 가장 작은 정수

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

50의 자리수를 가지는 숫자 A가 주어질 때, A보다 크면서 100019로 나누어지떨어지는 가장 작은 정수를 출력하라.

Find the minimum number is bigger than 50 decimal digits A and divided by 100019.

 

INPUT

* Line 1 : 정수 A (자리수:50)

 

OUTPUT

* Line 1 : A보다 크면서 100019로 나누어지떨어지는 가장 가장 작은 수

 

SAMPLE INPUT

10000000000000000000000000000000000000000000000000

 

SAMPLE OUTPUT

10000000000000000000000000000000000000000000032356

 

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        BigInteger n = input.nextBigInteger(), k = new BigInteger("100019");
        BigInteger x = n.divide(k).subtract(BigInteger.ONE).multiply(k);
        while(x.compareTo(n) < 0)
            x = x.add(k);
        System.out.println(x);
    }
}