2024.06.18 ( Java )

1. 카드 합체 놀이 ( BaekJoon )

Greedy ( https://www.acmicpc.net/problem/15903 )

풀이

• 최소의 합을 구하는 문제이니까 우선순위 큐 사용해서 가장 작은 수 2개씩 뽑아 더해서 다시 넣고 큐에 남아있는 수들의 합을 구했다. PriorityQueue 만 사용할 줄 알면 상당히 간단한 문제

package problem_solving.queue;

import java.util.PriorityQueue;
import java.util.Scanner;

public class BaekJoon_15903 {

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		PriorityQueue<Long> pq = new PriorityQueue<>();
		long n = Long.parseLong(sc.next());
		long count = Long.parseLong(sc.next());
		for(int i =0 ;  i< n ; i ++) {
			pq.offer(Long.parseLong(sc.next()));
		}
		
		while(count-- > 0 ) {
			long x = pq.poll();
			long y = pq.poll();
			long sum = x+y ; 
			pq.offer(sum);
			pq.offer(sum);
		}
		long answer = 0  ;
		while(!pq.isEmpty()) {
			answer+= pq.poll();
		}
		
		System.out.println(answer);
	}

}

2. 쇠막대기 ( BaekJoon )

Stack ( https://www.acmicpc.net/problem/10799 )

풀이

• (1) 만약 ( 를 만난다면 stack에 push
• (2) 만약 )를 만난다면 () 쌍이 되므로 일단 stack 마지막 ( pop
• (3) 만약 전에 기호가 ( 라면 레이저 이므로 stack 에 size만큼 개수 추가
• (4) 만약 전에 기호가 ) 이라면 단순 막대기 끝이므로 하나만 추가
• 그림 문제는 일단 적어서 출력값이 왜 나왔는지 확인하자

package problem_solving.stack;

import java.util.Scanner;
import java.util.Stack;

public class BaekJoon_10799 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		Stack<Character> st = new Stack<>();
		int answer = 0 ;
		for(int i= 0 ; i < s.length();i++) {
			if( s.charAt(i) == '(') {
				st.push(s.charAt(i));
				continue;
			}
			
			if( s.charAt(i) == ')') {
				st.pop();
			}
			
			if( s.charAt(i-1) == '(') {
				answer+=st.size();
			}else {
				answer++;
			}
			
		}
		System.out.println(answer);
	}

}