Code Jam to I/O 2016 for Women - A. Cody's Jams

Problem

Cody, the owner of the legendary Cody's Jams store, is planning a huge jam sale. To make things simple, he has decided to sell every item in his store at a 25% discount — that is, each item's sale price is exactly 75% of its regular price. Since all of his regular prices happened to be integers divisible by four, his sale prices are conveniently also all integers.

To prepare for the sale, he placed an order to print new labels for all of his items at their sale prices. He also placed an order to print new labels for all of his items at their regular prices, to use once the sale is over.

Cody just came back from picking up his order. Unfortunately, the printer gave him both orders in one combined stack, sorted by price. Both the sale price and the regular price label for each item are present somewhere in the stack. However, both types of labels look the same, and since he does not remember the price of every item, he is not sure which labels are the sale price labels. Can you figure that out?

For instance, if the regular prices were 20, 80, and 100, the sale prices would be 15, 60, and 75, and the printer's stack would consist of the labels 15, 20, 60, 75, 80, and 100.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line contains a single integer N, the number of items in Cody's store. The second line contains 2N integers P₁, P₂, ..., P_2N in non-decreasing order by the price printed on each label given by the printer.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of N integers: the labels containing sale prices, in non-decreasing order.

Limits

1 ≤ T ≤ 100.
1 ≤ P_i ≤ 10⁹, for all i.
P_i ≤ P_i+1, for all i. (The prices are in non-decreasing order.)
It is guaranteed that a unique solution exists.

Small dataset

1 ≤ N ≤ 4.

Large dataset

1 ≤ N ≤ 100.

Sample

Input	Output
2 3 15 20 60 75 80 100 4 9 9 12 12 12 15 16 20	Case #1: 15 60 75 Case #2: 9 9 12 15

풀이

연습삼아 풀어봤는데

백준에있는 문제보다는 쉬운 듯 하다. 다만 문제 해석하는게 오래걸릴 뿐..^^

문제를 요약하자면

물품을 25%할인해서 정가의 75%가격으로 팔려고 하는데

라벨을 뽑았더니 정가 가격이 적힌 라벨과 75%의 가격이 적힌 라벨이 동시에 뽑혔다!

이 중 75% 가격의 라벨만 골라내는 것이다.

조건은 정가는 무조건 4로 나누어 떨어지는 수이며, 라벨은 오름차순으로 뽑혀있다.

문제에 stack 이 언급된 것에 힌트를 얻어 stack으로 풀었당

일단 라벨목록중에 가장 오른쪽에 있는 수는 무조건 정가 라벨이라는 것을 이용해서 풀었다.

코드

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack stack1, stack2, answer;
        int T = sc.nextInt(); //the number of test case
        int salePrice, index = 1;
        
        while(T-- > 0){
            int N = sc.nextInt(); //the number of items
            int size = N * 2;
            stack1 = new Stack(size);
            stack2 = new Stack(size);
            answer = new Stack(N);
            
            while(size-- > 0)
                stack1.push(sc.nextInt());
            
            while(!stack1.isEmpty()){
                salePrice = stack1.pop()/4*3;
                while(stack1.peek() != salePrice){
                    //stack1 에서 꺼내 stack2 에 넣음
                    stack2.push(stack1.pop());
                }
                answer.push(stack1.pop());
                while(!stack2.isEmpty())
                    stack1.push(stack2.pop());    
            }//end while
            
            System.out.println("");
            System.out.print("Case #" + index++ + ": ");
            while(N-- > 0)
                System.out.print(answer.pop() + " ");        
        }//end while
    }
}

public class Stack {
    int top;
    int[] stack;
    int size;
    
    public Stack(int size){
        top = -1;
        stack = new int[size];
        this.size = size;
    }
    
    public int peek(){
        if(top == -1)return -1;
        return stack[top];
    }
    
    public void push(int item){
        if(top + 1 >= size)return;
        stack[++top] = item;
    }
    
    public int pop(){
        if(top == -1)return -1;
        return stack[top--];
    }
    
    public boolean isEmpty(){
        if(top == -1)return true;
        else return false;
    }
}