백준 17225 - 세훈이의 선물가게(Java)

www.acmicpc.net/problem/17225

17225번: 세훈이의 선물가게

 

1. 유형

우선순위큐, 구현

 

2. 자료구조

우선순위큐, 어레이리스트

 

3. 기능

- 우선순위 정하기

- 큐에 넣기

- 시작하는 시간 찾기

 

4. 풀이

일단 클래스 필드값으로 시작시간, 포장지색을 선언한다. 그리고 우선순위는 시작시간을 오름차순으로 정한다.

예외는 서브태스크 2 같은 경우다. 시작시간이 같은경우가 있다.

그때는 색깔 순서대로 상민이가 먼저 오도록 정한다.

 

큐에 넣는 것은 색깔 별로 max값을 설정해서 시작값을 설정한다.

끝.

 

코드.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int S, G, N;

	static class Pair implements Comparable<Pair> {
		int star;
		char color;

		public Pair(int star, char color) {
			// TODO Auto-generated constructor stub
			this.star = star;
			this.color = color;
		}

		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			if (this.star == o.star) {
				return o.color-this.color;
			}
			return this.star - o.star;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());

		S = Integer.valueOf(st.nextToken());
		G = Integer.valueOf(st.nextToken());
		N = Integer.valueOf(st.nextToken());
		int t, c, num;
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		int bmax = 0;
		int amax = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			t = Integer.valueOf(st.nextToken());
			c = st.nextToken().charAt(0);
			num = Integer.valueOf(st.nextToken());
			for (int j = 0; j < num; j++) {
				if (c == 'B') {
					if (bmax >= t) {
						pq.add(new Pair(bmax, 'b'));
						bmax+=S;
					}else {
						pq.add(new Pair(t, 'b'));
						bmax = t+S;
					}
				}else {
					if(amax >= t) {
						pq.add(new Pair(amax, 'a'));
						amax+=G;
					}else {
						pq.add(new Pair(t, 'a'));
						amax = t+G;
					}
				}
			}
		}
		ArrayList<Integer> blue = new ArrayList<>();
		ArrayList<Integer> red = new ArrayList<>();
		int idx=1;
		while(!pq.isEmpty()) {
			Pair cur = pq.poll();
			if(cur.color=='a') {
				red.add(idx);
			}else {
				blue.add(idx);
			}
			idx++;
		}
		System.out.println(blue.size());
		for(int k : blue) 
			System.out.print(k+" ");
		System.out.println();
		System.out.println(red.size());
		for(int k : red) 
			System.out.print(k+" ");
		System.out.println();
	}
}

5. 느낀점

왠만한 골드 문제보다 어렵게 느껴졌다.

코테에 자주 나오는 유형이니 비슷한 유형을 많이 풀어봐야겠다.