Chapter 20. Lists, Stacks, Queues, and Priority Queues[Java basic]

20.A - 2차평면의 점을 정렬하기

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

다음 요구사항을 만족하는 프로그램을 작성하라.

■ Point 클래스는 x좌표와 y좌표를 데이터를 가진다. Point 객체들을 좌표에 따라 오름차순으로 정렬하기 위해 Comparable 인터페이스를 정의하라. Point 개체들에 대해서 먼저 x좌표를 기준으로 정렬하고, 복수의 Point가 동일한 x좌표를 가진다면 y좌표로 정렬하라.

■ y좌표를 먼저 정렬하고, 그 다음 x좌표로 정렬하는 CompareY를 작성하라.

(Sort points in a plane) Write a program that meets the following requirements:

■ Define a class named Point with two data fields x and y to represent a point’s x- and y-coordinates. Implement the Comparable interface for comparing the points on x-coordinates. If two points have the same x-coordinates, compare their y-coordinates.

■ Define a class named CompareY that implements Comparator. Implement the comparemethod to compare two points on their y-coordinates. If two points have the same y-coordinates, compare their x-coordinates.

■ Randomly create 100 points and apply the Arrays.sort method to display the points in increasing order of their x-coordinates and in increasing order of their y-coordinates, respectively.

 

INPUT

* Line 1 : Point 개수 N (1~2,000 범위의 정수) 

* Line 2~N+1 : x y (x,y는 -1,000~1,000범위의 정수)

 

OUTPUT

X와 Y로 정렬된 점을 Sample Output과 같은 형식으로 출력

 

SAMPLE CODE

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

public class Main {
    // Each row in points represents a point
    private double[][] points;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Point[] points = new Point[N];
        for (int i = 0; i < points.length; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }

        System.out.println("Sort on x-coordinates");
        Arrays.sort(points);
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[i]);
        }

        System.out.println("Sort on y-coordinates");
        Arrays.sort(points, new CompareY());
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[i]);
        }
    }

    YOUR_CODE

}

SAMPLE INPUT

5

1 3 -10 -9 0 3 -2 9 0 4

 

SAMPLE OUTPUT

Sort on x-coordinates

(-10.0, -9.0) (-2.0, 9.0) (0.0, 3.0) (0.0, 4.0) (1.0, 3.0)

Sort on y-coordinates

(-10.0, -9.0) (0.0, 3.0) (1.0, 3.0) (0.0, 4.0) (-2.0, 9.0)

 

HINT

    public String toString() {
        return "(" + x + ", " + y + ")";
    }

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
 
public class Main {
    // Each row in points represents a point
    private double[][] points;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        Point[] points = new Point[N];
        for (int i = 0; i < points.length; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }
 
        System.out.println("Sort on x-coordinates");
        Arrays.sort(points);
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[i]);
        }
 
        System.out.println("Sort on y-coordinates");
        Arrays.sort(points, new CompareY());
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[i]);
        }
    }
 
    public int compareY(Point p1, Point p2) {
        double x1 = p1.getX();
        double y1 = p1.getY();
        double x2 = p2.getX();
        double y2 = p2.getY();
 
        if (y1 == y2) {
            if (x1 < x2) return -1;
            else if (x1 == x2) return 0;
            else return 1;
        }
        else if (y1 < y2)
            return -1;
        else
            return 1;
    }
 
}

 

 

20.B - 우선순위큐의 집합 연산

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

두개의 우선순위 큐 Q1과 Q2를 만들어 union, difference, intersection을 수행해 보자.

(Perform set operations on priority queues) Create two priority queues,  and find their union, difference, and intersection.

 

INPUT

* Line 1 : 공백으로 구분된 Q1의 문자열

* Line 2 : 공백으로 구분된 Q2의 문자열

 

 

OUTPUT

* Line 1 : 공백으로 구분된 Q1 union Q2의 문자열 

* Line 2 : 공백으로 구분된 Q1 difference(-) Q2의 문자열 

* Line 3 : 공백으로 구분된 Q1 intersection Q2의 문자열 

 

SAMPLE INPUT

hr rz no bk

hc up dk bk tl hs cz

 

SAMPLE OUTPUT

[bk, bk, cz, rz, dk, no, hc, up, tl, hs, hr] [hr, rz, no] [bk]

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        List<String> l1 = Arrays.asList(s.split(" "));
        s = input.nextLine();
        List<String> l2 = Arrays.asList(s.split(" "));
        PriorityQueue<String> q1 = new PriorityQueue<>(l1);
        PriorityQueue<String> q2 = new PriorityQueue<>(l2);
 
        System.out.println(union(q1, q2));
        System.out.println(difference(q1, q2));
        System.out.println(intersection(q1, q2));
    }
    private static <T> PriorityQueue<T> union(PriorityQueue<T> q1, PriorityQueue<T> q2) {
        PriorityQueue<T> ans = new PriorityQueue<>(q1);
        ans.addAll(q2);
        return ans;
    }
    private static <T> PriorityQueue<T> difference(PriorityQueue<T> q1, PriorityQueue<T> q2) {
        PriorityQueue<T> ans = new PriorityQueue<>(q1);
        ans.removeAll(q2);
        return ans;
    }
    private static <T> PriorityQueue<T> intersection(PriorityQueue<T> q1, PriorityQueue<T> q2) {
        PriorityQueue<T> ans = new PriorityQueue<>(q1);
        ans.retainAll(q2);
        return ans;
    }
}

반응형

 

20.C - 올바른 그룹 기호

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

자바 프로그램은 다음과 같은 다양한 그룹 기호를 가진다.

■ Parentheses: ( and )

■ Braces: { and }

■ Brackets: [ and ]

이러한 그룹 기호들의 범위는 서로 인접하거나, 포함 될 순 있어도,  (a{b)} 와 같이 걸쳐서는 안된다. 그룹 기호들이 올바르게 표현되어 있는지 확인하는 프로그램을 만들어 보자.

 

(Match grouping symbols) A Java program contains various pairs of grouping symbols, such as:

■ Parentheses: ( and )

■ Braces: { and }

■ Brackets: [ and ]

Note that the grouping symbols cannot overlap. For example, (a{b)} is illegal. Write a program to check whether a Java source-code file has correct pairs of grouping symbols. 

 

INPUT

* Line 1 : 자료의 개수 N (1~1,000 범위의 정수) 

* Line 2~N+1 : N개의 자바 소스코드 라인

 

OUTPUT

* Line 1~N : 자바 소스코드 라인안에서 그룹이 올바르면 T 그렇지 않다면 F

 

SAMPLE INPUT

3

()( )

((a))

)()(

 

SAMPLE OUTPUT

T T F

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        Stack<Character> s = new Stack<>();
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        input.nextLine();
        for(int t = 0; t < n; t++){
            String line = input.nextLine();
            int c1 = 0 ,c2 = 0;
            for (int i = 0; i < line.length(); i++) {
                char c = line.charAt(i);
                if (c == '(' || c == '{' || c == '[') {
                    s.push(c);
                    c1++;
                }
                else if (c == ')' || c == '}' || c == ']') {
                    check(s, c);
                    c2++;
                }
            }
            System.out.println(s.isEmpty() && c1== c2 ? "T" : "F");
            s.clear();
        }
    }
    private static void check(Stack<Character> s, Character ch) {
        try {
            if ((s.peek() == '(' && ch == ')') || (s.peek() == '[' && ch == ']') || (s.peek() == '{' && ch == '}')) {
                s.pop();
            } else if ((s.peek() != '(' && ch == ')') || (s.peek() != '[' && ch == ']') || (s.peek() != '{' && ch == '}')) {
                return;
            }
        }
        catch(Exception e){
            return;
        }
    }
}

 

 

20.D - 후위 표기법

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

후위 표기법은 괄호를 사용하지 않는 수식 표현 방법이다.  1+2를 하고 그 결과에 *3을 하고자 한다면 괄호를 사용해 (1 + 2) * 3 와 같이 수식으로 표현하는데, 후위 표기법에서는 스택을 이용해 괄호 없이도 1+2 계산이 *3보다 먼저 이루어 지게 할 수 있다. 후위 표기법에서 수식을 계산하는 방법은 수식에서 왼쪽에서 오른쪽으로 순차적으로 읽으면서 다음을 반복한다.

• 숫자일 경우 스택에 집어 넣는다
• 연산자일 경우 스택에서 2개의 숫자를 빼 연산을 수행한후, 그 결과를 다시 스택에 집어 넣는다. 

(1+2)*3을 후위 표기법으로 변경하면 1 2 + 3 * 로 하면된다. 여러분은 후위 표기법으로 표현된 수식을 읽어 들여 그 계산결과를 출력하는 프로그램을 작성해야 한다.

 

(Postfix notation) Postfix notation is a way of writing expressions without using parentheses. For example, the expression (1 + 2) * 3 would be written as 1 2 + 3 *. A postfix expression is evaluated using a stack. Scan a postfix expression from left to right. A variable or constant is pushed into the stack. When an operator is encountered, apply the operator with the top two operands in the stack and replace the two operands with the result. The following diagram shows how to evaluate 1 2 + 3 *.

Write a program to evaluate postfix expressions. 

 

INPUT

* Line 1 : 수식의 개수 N (1~1,000 범위의 정수) 

* Line 2~N+1 : 공백으로 구분된 수식 (상수는 -1000~1000범위의 정수, 계산 도중 int의 범위를 넘지 않음)

 

OUTPUT

* Line 1~N : 계산된 값. 만약 값을 계산 할 수 없다면 Wrong expression을 출력

 

SAMPLE INPUT

3

1 2 +

1 2 + 3 *

1 2 1 /

 

SAMPLE OUTPUT

3

9

Wrong expression

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int i;
        input.nextLine();
        for(i = 0; i < n; i++){
            String s = input.nextLine();
            try{
                System.out.println(evaluateExpression(s));
            }catch(Exception e){
                System.out.println("Wrong expression");
            }
        }
    }
    public static int evaluateExpression(String s) throws Exception {
        Stack<Integer> stack = new Stack<>();
        String[] t = s.split(" ");
        int i = 0;
        if(!Character.isDigit(t[0].charAt(0)))
            throw new Exception("Wrong expression");
        else if(t.length == 1)
            return Integer.parseInt(t[0]);
        else if(t.length == 2)
            throw new Exception("Wrong expression");
        for (String token: t) {
            if(i > 0 && i % 2 == 1 && !Character.isDigit(token.charAt(0)))
                throw new Exception("Wrong expression");
            if (token.charAt(0) == '+' || token.charAt(0) == '-'|| token.charAt(0) == '*' || token.charAt(0) == '/') {
                cal(stack, token.charAt(0));
            }
            else if (Character.isDigit(token.charAt(0))){
                stack.push(Integer.parseInt(token));
            }
            else
                throw new Exception("Wrong expression");
            i++;
        }
        return stack.pop();
    }
    public static void cal(Stack<Integer> stack, char o) {
        int n1 = stack.pop();
        int n2 = stack.pop();
        switch (o) {
            case '+': stack.push(n2 + n1); break;
            case '-': stack.push(n2 - n1); break;
            case '*': stack.push(n2 * n1); break;
            case '/': stack.push(n2 / n1);
        }
    }
}