[코드트리] 코딩톡

일어난 상황에 대해서 추론을 하여  적합한 답을 출력하는 문제다.

 

메신저를 보낸사람과, 그 메시지를 보지않은 사람의 수들의 목록이 주어졌을때, 특정시점에서 해당 메시지를 읽지 않을 가능성이 있는사람을 출력하는 문제이다..

 

어려움 난이돈데 금방 풀어서 기분이 좋고,, 아직 배우지는 않았지만 역탐색을 이용해서 처음 푼 문제이기때문에 기록한다.

 

---

n명의 프로그래머들이 서로 채팅으로 대화할 수 있는 메신저방인 코딩톡에 초대되었습니다. 코딩톡 사람들의 이름은 'A'부터 n개의 대문자 알파벳이 순서대로 붙여져 있으며, 서로 대화를 하고 있습니다. 누군가 메신저방에 들어오게 되면, 이전에 보내진 모든 메세지를 읽게 됩니다. 각 프로그래머들이 언제 들어왔다가 나갔는지에 대한 정보는 전혀 없지만, 총 m개의 해당하는 메세지 정보가 주어졌을 때, p번째 메세지를 읽지 않았을 가능성이 있는 사람들의 이름을 찾아내는 프로그램을 작성해보세요. m개의 메세지 정보는 시간 순서대로 주어지며, 각 상황마다 어떤 사람이 해당 메세지를 보냈고 그 메세지를 최종적으로 읽지 않은 사람의 수가 몇 명인지가 주어집니다.

 

입력 형식

첫 번째 줄에는 코딩톡 방에 있는 사람 수 n, 코딩톡 방에 올라온 메세지 정보의 수 m과 확인이 필요한 메세지 번호 p가 주어집니다.

두 번째 줄 부터는 m개의 줄에 걸쳐 메세지 정보 c, u가 공백을 사이에 두고 주어집니다. 사람 c가 올린 메세지이며, 아직 해당 메세지를 읽지 않은 사람 수가 u임을 의미합니다. c는 대문자 알파벳으로만 주어지며, 사람 이름은 'A'부터 시작하여 순서대로 n개로 붙여져 주어짐을 가정해도 좋습니다.

• 1 ≤ n ≤ 26
• 1 ≤ p ≤ m ≤ 100
• 0 ≤ u ≤ n - 1

출력 형식

p번째 메세지를 읽지 않았을 가능성이 있는 사람들의 이름을 사전순으로 정렬하여 공백을 사이에 두고 출력합니다.

 

입출력 예제

예제1

입력:

6 6 2
D 0
C 1
B 2
B 2
A 2
F 4

 

출력:

D E

 

예제 설명

2번째 메세지 이후에 A, B, F가 메세지를 보냈으므로 A, B, F는 확실히 2번째 메세지를 읽었습니다. 또한 2번째 메세지는 C가 보냈으므로 확실히 메세지를 읽은 사람은 A, B, C, F 입니다. 따라서 메세지를 읽지 않았을 가능성이 있는 사람은 D, E 뿐입니다.

 

---

내 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //데이터 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        
        String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        HashMap<String, Integer> map = new HashMap<>();
        String[] arr = Arrays.stream(alphabet.substring(0, n).split("")).toArray(String[]::new);
        for(String temp : arr){
            map.put(temp, 0);
        }

        String[] message = new String[m];
        for(int i = 0; i < m; i++){
            message[i] = sc.next() + sc.nextInt();
        }
        //데이터 입력

        for(int i = 0; i < m; i++){
            String talk = message[i].split("")[0];
            int left = Integer.parseInt(message[i].split("")[1]);

            //p번째인데 left가 0이면 안읽은 사람은 존재할 수 없다.
            if(i+1 == p){
                if(left == 0){
                    return;
                }else{
                    //p번째 부터 역탐색, 계속 p랑 같으면 같은 사람들은 전부 읽은사람들이다. p와 같지않다면 거기까지이므로 break;
                    for(int j = p-1; j >= 0; j--){
                        String tempTalk = message[j].split("")[0];
                        int tempLeft = Integer.parseInt(message[j].split("")[1]);
                        if(tempLeft == left){
                            map.put(tempTalk, -1);
                        }else{
                            break;
                        }
                    }
                }
            }

            //p번째 이후 메세지를 보낸사람들은 전부 p번째 메세지를 읽었다.
            if(i+1 >= p){
                map.put(talk, -1);
            }
        }

        //값이 -1이 아니면 읽지 않은 사람들이다 -> 출력한다.
        for(String key : map.keySet()){
            if(map.get(key) > -1){
                System.out.print(key + " ");
            }
        }
    }
}

 

기분이좋다~~^^