나름 풀이랑 다 생각해서 풀고있었는데 A번 Hack당한거에 멘붕당해서 C번 마무리를 못하고 2시간이 끝나버렸다.
대회 끝나고 남은부분 정리해서 제출했더니 Accepted 떠서 괜히 슬펐음 (ㅠㅠ)
user가 일부 ?로 가려진 채팅내용에서 ?에 가능한 user를 규칙에 맞게 매칭시키는 것 (불가능한 경우 impossible)
규칙1. user는 대화내용(text)에 본인을 언급할 수 없다. (text에 자신의 username이 단어로 들어있으면 안됨)
규칙2. 한 user가 연속해서 말할 수 없다.
의식의 흐름대로 코드를 짜다보니 너무 길고 장황한 코드가 되어버린듯...
일단 text를 word 단위로 잘라서 어떤 username이 언급되었는지 체크를 해야한다.
이 때 사용할 수 있도록 미리 HashMap으로 username-index를 저장해 놓아야 하고...
언급된 것이나 위아래 message의 user를 제외하고 현재 ?에 들어올 수 있는 user가 누구이고 경우의 수(possibleCnt)가 몇개나 되는지 계속 기록을 해서 업데이트해나간다. possibleCnt가 0인 경우는 impossible로 처리하고 바로 다음 chat으로 넘어가고, 1인 경우는 그 1에 해당하는 user로 ?를 확정시킨다음 주변(위아래) 정보를 업데이트한다. 이과정을 계속 반복하다가, 모든 ?에 대해 possibleCnt>=2가 되면 가장 위의 ?부터 가능한 아무 user로 확정시키고 아래 정보를 업데이트하면서 내려오면 마지막 ?까지 규칙에 위배되지 않고 다 채워나갈 수 있다.
... 내가 썼지만 무슨 소린지... ㅠㅠ
아무튼 Java의 String 관련 API도 몇개 썼고 HashMap도 썼고... 최근에는 c++로 문제를 풀려고 노력하는 와중이었는데 아무래도 코드포스는 시간에 쫓기다보니 원래 익숙한 자바를 쓰게된다. 나중에 c++로 다시 풀어볼 수 있을까...
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class ProblemC {
static int N, M;
static Map<String, Integer> userMap;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t=0; t<T; t++) {
N = Integer.parseInt(br.readLine());
userMap = new HashMap<String, Integer>();
String[] users = br.readLine().split(" ");
for (int i=0; i<N; i++) {
userMap.put(users[i], i);
}
M = Integer.parseInt(br.readLine());
Message[] msgs = new Message[M];
for (int i=0; i<M; i++) {
msgs[i] = new Message(br.readLine(), N);
init(msgs[i]);
}
boolean possible = false;
boolean impossible = false;
while (!possible && !impossible) {
int unknownCnt = 0;
int min = 100;
for (int i=0; i<M; i++) {
Message cur = msgs[i];
if (cur.unknown) {
unknownCnt++;
int check = 0;
if (i != 0 && !msgs[i-1].unknown) {
int idx = msgs[i-1].userIdx;
if (cur.possible[idx]) {
cur.possible[idx] = false;
cur.possibleCnt--;
}
check++;
}
if (i != M-1 && !msgs[i+1].unknown) {
int idx = msgs[i+1].userIdx;
if (cur.possible[idx]) {
cur.possible[idx] = false;
cur.possibleCnt--;
}
check++;
}
if (cur.possibleCnt == 0) {
impossible = true;
break;
} else if (check == 2 || cur.possibleCnt == 1) {
for (int j=0; j<cur.possible.length; j++) {
if (cur.possible[j]) {
cur.user = users[j];
cur.userIdx = j;
cur.unknown = false;
break;
}
}
unknownCnt--;
}
if (cur.possibleCnt < min) {
min = cur.possibleCnt;
}
}
}
if (unknownCnt == 0) {
possible = true;
} else if (min >= 2) {
for (int i=0; i<M; i++) {
Message cur = msgs[i];
if (cur.unknown) {
for (int j=0; j<cur.possible.length; j++) {
if (cur.possible[j]) {
cur.user = users[j];
cur.userIdx = j;
cur.unknown = false;
break;
}
}
if (i < M-1 && msgs[i+1].unknown) {
if (msgs[i+1].possible[cur.userIdx]) {
msgs[i+1].possible[cur.userIdx] = false;
msgs[i+1].possibleCnt--;
}
}
}
}
possible = true;
}
}
if (impossible) {
System.out.println("Impossible");
} else if (possible) {
for (int i=0; i<M; i++) {
System.out.println(msgs[i].user + ":" + msgs[i].text);
}
}
}
}
static void init(Message msg) {
if (msg.unknown) {
msg.possible = new boolean[N];
msg.possibleCnt = N;
for (int i=0; i<N; i++) {
msg.possible[i] = true;
}
String tmpMsg = msg.text;
for (int i=0; i<msg.text.length(); i++) {
char ch = tmpMsg.charAt(i);
if (ch=='.' || ch==',' || ch=='!' || ch=='?') {
tmpMsg = tmpMsg.replace(ch, ' ');
}
}
String[] words = tmpMsg.split(" ");
for (int i=0; i<words.length; i++) {
Integer idx = userMap.get(words[i]);
if (idx != null) {
if (msg.possible[idx]) {
msg.possible[idx] = false;
msg.possibleCnt--;
}
}
}
} else {
msg.userIdx = userMap.get(msg.user);
}
}
}
class Message {
boolean unknown;
String user, text;
int userIdx;
boolean[] possible;
int possibleCnt;
Message(String msg, int userCnt) {
String[] tmp = msg.split(":");
this.user = tmp[0];
this.text = tmp[1];
this.unknown = "?".equals(this.user);
}
}
