알고리즘 스터디 4주차

스택 & 큐 [1874, 2164]

1874

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장
		
		Stack<Integer> stack = new Stack<>();
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			
			int value = Integer.parseInt(br.readLine());
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장한다. 
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;		// 또는 System.exit(0); 으로 대체해도 됨. 
			}
			
			stack.pop();
			sb.append('-').append('\n');
			
		}
		
		System.out.println(sb);
	}
}

 

2164

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 1; i<=n; i++)
            queue.add(i);


        while(queue.size() > 1) {
        queue.poll();
        int val = queue.peek();
        queue.poll();
        queue.add(val);
        }
        System.out.println(queue.peek());
        
    }
}

 

 

탐욕 알고리즘 [11047, 1541]

11047

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int k = sc.nextInt();

        int[] coin = new int[n];

        for(int i=0; i < n; i++) {
            coin[i] = sc.nextInt();
        }

        int count = 0;

        for(int i =n-1; i >= 0; i--) {
            if(coin[i] <= k) {
                count += (k/coin[i]);
                k = k%coin[i];
            }
        }
        System.out.println(count);
    }
}

1541

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int sum = 0;
        String[] subtraction = sc.nextLine().split("-");

        for (int i = 0; i < subtraction.length; i++) {
            int temp = 0; 

            String[] addition = subtraction[i].split("\\+");
            for(int j = 0; j < addition.length; j++) {
				temp += Integer.parseInt(addition[j]);
			}

            if ( i== 0) {
                sum += temp;
            } else {
				sum -= temp;
            }
		}
        
		System.out.println(sum);
        }
    }