문제
백준 20292 컨설팅 : https://www.acmicpc.net/problem/20292
Sogang ICPC Team에서는 학회원들을 돕기 위해 Sogang Program Consulting Team(이하 SPC Team)을 만들었다. SPC Team은 학회원들과 화목하게 지내게 될 날만을 상상하며 에러가 발생한 코드를 무료로 디버깅해주는 컨설팅을 바로 시작했다.
그러던 어느 날, 기세등등했던 SPC Team의 모두를 당황시킨 코드가 등장했다. 아무리 봐도 정상적인 코드인데, 원하는 데이터를 얻을 수 없었던 것이다. 하지만 포기를 모르는 SPC Team은 계속해서 디버깅을 시도한 끝에, 한 번에 여러 줄의 명령이 실행되고 있었다는 사실을 알게 되었다! 이 상황을 이해하기 위해 다음 예시를 살펴보자.
1: WRITE A TO B
2: WRITE B TO C
3: READ B
4: READ C
5: EXIT
위 코드는 문제가 된 학회원의 코드이다. 명령어가 순서대로 실행되면 전혀 문제가 없을 코드지만, 줄 1–4가 동시에 실행된다면 문제가 생긴다. 메모리 A에서 메모리 B로 데이터가 옮겨지지도 않았는데 두 번째 줄이 실행되면, 메모리 C에 무슨 데이터가 들어갈지 알 수 없다. 이러한 문제를 확인한 SPC Team은 다음과 같이 컨설팅을 해 주었다.
1: WRITE A TO B
2: WAIT
3: WRITE B TO C
4: WAIT
5: READ B
6: READ C
7: EXIT
위와 같이, 중간에 WAIT를 삽입하여 WRITE A TO B와 WRITE B TO C가 동시에 실행되는 것을 막아준다면, 메모리 C에 어떤 데이터가 들어갈지 명확해진다! 위 코드에 대한 컨설팅을 끝마친 SPC Team은 문제가 발생할 수 있는 경우를 다음과 같이 세 가지로 분류했다.
READ with WRITE
WRITE A TO B와 READ B가 동시에 실행되면, 메모리 B의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
WRITE A TO B와 WRITE B TO C가 동시에 실행되면, 메모리 C의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
WRITE with WRITE
WRITE A TO C와 WRITE B TO C가 동시에 실행되면, 메모리 C의 데이터가 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
WRITE A TO B와 다른 WRITE A TO B가 동시에 실행되는 것은 문제가 없지만, 프로그램의 안정성을 위해 두 명령어 사이에 WAIT가 있어야 한다.
교착 상태
WRITE A TO B와 WRITE B TO A가 동시에 실행되면, 메모리 A와 메모리 B의 값이 확실하지 않으므로 두 명령어 사이에 WAIT가 있어야 한다.
이 문제를 겪고 있는 학회원들이 지속적으로 SPC Team에 컨설팅 문의를
신청하고 있다. 반복되는 작업에 지친 SPC Team은 위와 같은 상황을 알아서 탐지하여 컨설팅해주는 프로그램을 만들고자 한다. 하지만 너무나도 바쁜 나머지, 유능한 프로그래머인 당신에게 프로그램의 제작을 의뢰했다. 너무나도 마음이 상냥한 당신은 이 의뢰를 거절할 수 없다!
입력
입력으로 최대 줄의 명령어가 주어지며, WRITE문, READ문, EXIT문으로 구성된다. EXIT문은 마지막에 한 번만 주어진다.
각 명령어는 다음과 같이 정의되며, 메모리 이름은 –글자의 알파벳 대문자로 구성되어 있다.
WRITE A TO B: 메모리 A의 내용을 메모리 B로 옮긴다. 이 때, 메모리 A는 READ 상태가 된다.
READ A: 메모리 A의 데이터를 읽는다.
EXIT: 프로그램을 종료한다.
WRITE A TO A같이 동일한 메모리로 WRITE를 수행하는 경우는 없다.
출력
WAIT을 최소로 사용한 컨설팅 결과를 기존 명령어들의 순서를 유지하여 출력한다.
한 줄에 하나의 명령어만 출력해야 하며, 만약 그러한 컨설팅 결과가 여러 개라면 그 중 하나를 출력한다.
예제 입력 1
WRITE A TO B
WRITE B TO C
READ B
READ C
EXIT
예제 출력 1
WRITE A TO B
WAIT
WRITE B TO C
WAIT
READ B
READ C
EXIT
예제 입력 2
WRITE EAX TO ECX
WRITE ESP TO ESI
READ EAX
WRITE EDX TO EBP
WRITE EDI TO ESI
READ ECX
WRITE ECX TO EAX
READ EBP
WRITE ESP TO EBP
WRITE EBP TO EDX
EXIT
예제 출력 2
WRITE EAX TO ECX
WRITE ESP TO ESI
READ EAX
WRITE EDX TO EBP
WAIT
WRITE EDI TO ESI
READ ECX
WRITE ECX TO EAX
READ EBP
WAIT
WRITE ESP TO EBP
WAIT
WRITE EBP TO EDX
EXIT
풀이
해당 문제를 보면 read를 하게 되는 경우(wirte a and b 일때 a/ read a)일때
a가 이전에 write를 했을 경우 wait을 넣어줘야 한다. 또 write를 할때 이전에 b를 활용한 경우가 있을 시에도 wait을 넣어 주어야 한다.이때 놓칠 수 있는 경우가 read를 이전에 한 경우가 있을 때도 wait을 넣어주어야 한다.
왜냐하면 이전에 리드한 값이 애매할 수 있기 때문이다.
이 외의 경우에는 바로 출력을 해주고
위의 경우에는 wait출력후 출력한다.
이때 wait을 했을 경우
모든 지금까지 나온 값들에 대한 내용들이 초기화 되고 현재 내가 행한 내용
(wirte a and b의 경우 a를 read 하고 b를 write했다
read a의 경우 a를 read했다.)
를 기록해준다.
그리고 계속 진행한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String ...asmr) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringBuilder ans=new StringBuilder("");
Set<String> hashR=new HashSet<>();
Set<String> hashW=new HashSet<>();
while (true){
String get=br.readLine();
if(get.equals("EXIT")){
System.out.println(ans.append("EXIT"));
return;
}
StringTokenizer st=new StringTokenizer(get);
if(st.nextToken().equals("WRITE")){
String a=st.nextToken();
st.nextToken();
String b=st.nextToken();
if(hashW.contains(a)){
ans.append("WAIT\n");
hashR.clear();
hashW.clear();
}
else if(hashW.contains(b)){
ans.append("WAIT\n");
hashR.clear();
hashW.clear();
}
else if(hashR.contains(b)){
ans.append("WAIT\n");
hashR.clear();
hashW.clear();
}
ans.append(get).append("\n");
hashR.add(a);
hashW.add(b);
}
else {
String a=st.nextToken();
if(hashW.contains(a)){
ans.append("WAIT\n");
hashR.clear();
hashW.clear();
}
ans.append(get).append("\n");
hashR.add(a);
}
}
}
}
후기
처음에는 해쉬맵을 사용했다. 근데 생각해보니 set으로도 되는거여서 set으로 바꾸었다. 조건을 파악하는게 생각보다 난해했다. 조건 파악에 힘쓰도록 하자
