문제 링크
https://www.acmicpc.net/problem/21775
21775번: 가희와 자원 놀이
T턴에 걸쳐서, 각 턴에 수행된 연산 카드의 id를 한 줄에 하나씩 출력해 주세요.
www.acmicpc.net
접근 방법
일단 문제 풀이의 전체적인 프로세스는 아래와 같습니다.
공용 공간의 카드 그리고 개인이 가지고 있는 카드는 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);
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 20542 받아쓰기 (0) | 2021.01.15 |
|---|---|
| [C++] 백준 20543 폭탄 던지는 태영이 (0) | 2021.01.15 |
| [C++] 백준 19238 스타트 택시 (0) | 2021.01.12 |
| [C++] 백준 19237 어른 상어 (1) | 2021.01.12 |
| [C++] 백준 20544 공룡게임 (2) | 2021.01.10 |
