[Java] 백준 21775 가희와 자원 놀이

문제 링크

---

https://www.acmicpc.net/problem/21775

21775번: 가희와 자원 놀이

 

접근 방법

---

일단 문제 풀이의 전체적인 프로세스는 아래와 같습니다.

 

 

 

 공용 공간의 카드 그리고 개인이 가지고 있는 카드는 HashMap을 사용하여 정보를 저장합니다.

 

또한 문제를 해결하기 위해 저는 2가지의 Class(구조체)를 정의하였습니다. 

1. Info(int id, String action, int num) -> 카드의 id, (next, acquire, release) 중 한 가지, 자원의 번호

2. UserPlace(HashMap myCards, boolean flag, Info info) -> 개인카드 덱, 수행할 acquire의 존재 유무, 존재한다면 수행해야 할 acquire의 정보

 

 이 두 가지의 자료구조와 위의 프로세스를 따라간다면 구현할 수 있는 문제였습니다.

자세한 내용은 아래 소스코드에 주석처리 하겠습니다.

 

소스 코드

---

import java.*;
import java.util.*;

public class boj21775 {
	
	static int[] turns;
	static ArrayList<Info> infos = new ArrayList<Info>();
	
	public static class Info {
		int id; String action; int num;
		
		public Info(int id, String action, int num) {
			this.id = id;
			this.action = action;
			this.num = num;
		}
	}
	
	public static class UserPlace {
		
		HashMap<Integer, Boolean> myCards;
		boolean flag;
		Info info;
		
		public UserPlace(HashMap myCards, boolean flag, Info info) {
			this.myCards = myCards;
			this.flag = flag;
			this.info = info;
		}
	}
	
	public static void solve(int n, int t) throws Exception {
		
		HashMap<Integer, Boolean> common = new HashMap<Integer, Boolean>(); //공용공간
		ArrayList<UserPlace> Users = new ArrayList<UserPlace>(); //각각의 유저들(idx로 참조)
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<n;i++) 
			Users.add(new UserPlace(new HashMap<Integer, Boolean>(), false, null));
		
		int pointer = 0; //더미 포인터
		
		for(int i=0;i<t;i++) {
			
            // 현재 유저
			UserPlace now = Users.get(turns[i]);
			
            //수행해야 할 acquire가 존재한다면
            if(now.flag) {
				boolean isContain = common.get(now.info.num);
				if(isContain) { //공용 공간에 acquire 자원이 있다면
					common.put(now.info.num, false); //공용공간의 자원 false
					now.myCards.put(now.info.num, true); //개인공간의 자원 true
					now.flag = false; //acquire 해제
				}
				sb.append(now.info.id + "\n");
			} //수행해야 할 acquire가 없다면
			else {
				
                //더미 포인터를 통해 수행해야할 연산을 가져옴
				Info info = infos.get(pointer);
				
				if(info.action.charAt(0) == 'n') //next인 경우
					sb.append(info.id + "\n");
				else if(info.action.charAt(0) == 'r') { //release인 경우
					now.myCards.put(info.num, false); //개인공간의 자원 false
					common.put(info.num, true); //공용공간의 자원 true
					sb.append(info.id + "\n");
				}
				else { //acquire인 경우
                	// 공용공간에 key가 없다는 것은 한 번도 해당 자원을 참조하지 않았다는 뜻
					if(!common.containsKey(info.num)) {
						common.put(info.num, false); //공용공간에 자원을 추가하며 사용불가 false
						now.myCards.put(info.num, true); //개인 공간의 자원 true
					}
					else { // 공용 공간에 자원이 참조된 적이 있을 때
						if(common.get(info.num)) { //공용공간에서 사용가능하다면
							common.put(info.num, false); //공용공간의 자원 false
							now.myCards.put(info.num, true); //개인 공간의 자원 true
							now.flag = false; //acquire flag 해제
						}
						else { //공용공간에서 사용불가능 하다면
							now.flag = true; // 수행해야 할 acquire true
							now.info = info; // 현재의 acquire 정보를 user에 update
						}
					}
					sb.append(info.id + "\n");
				}
                //더미 포인터 증가
				pointer++;
			}
		}
		
		bw.write(sb.toString());
		bw.close();
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		
		int n = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		
		str = br.readLine();
		st = new StringTokenizer(str," ");
		turns = new int[t];
		for(int i=0;i<t;i++) {
			turns[i] = Integer.parseInt(st.nextToken()) - 1; //추 후 index로 참조하기위해 -1
		}
		
		for(int i=0;i<t;i++) {
			str = br.readLine();
			st = new StringTokenizer(str," ");
			int id = Integer.parseInt(st.nextToken());
			String action = st.nextToken();
			int num = 0; //0번 자원은 존재하지 않기 때문에 next인 경우 임시로 0번 자원 저장
			if(action.charAt(0) != 'n')
				num = Integer.parseInt(st.nextToken());
			infos.add(new Info(id, action, num)); 
		}
		br.close();
		
		solve(n, t);	
	}
}