Rooms

Code

public class Rooms

{

    public int[] finalRooms(String[] rooms, String doors, int start) {

        int n = rooms.length;

        boolean[] pos = new boolean[n];

        int[][][] nrooms = new int[n][91][];

        for (int i = 0; i < n; i++) {

            String[] sp = rooms[i].split(" ");

            for (int j = 0; j < sp.length; j++) {

                String[] d = sp[j].substring(2).split(",");

                nrooms[i][sp[j].charAt(0)] = new int[d.length];

                for (int k = 0; k < d.length; k++)

                    nrooms[i][sp[j].charAt(0)][k] = Integer.parseInt(d[k]);

            }

        }

        pos[start] = true;

        LOOP:

        for (char d : doors.toCharArray()) {

            boolean[] next = new boolean[n];

            for (int i = 0; i < n; i++) {

                if (pos[i]) {

                    if (nrooms[i][d] == null) {pos = next; break LOOP;}

                    for (int k = 0; k < nrooms[i][d].length; k++)

                        next[nrooms[i][d][k]] = true;

                }

            }

            pos = next;

        }

        

        int cnt = 0;

        for (int i = 0; i < n; i++)

            if (pos[i]) cnt++;

        

        int[] res = new int[cnt];

        cnt = 0;

        for (int i = 0; i < n; i++)

            if (pos[i]) res[cnt++] = i;

        return res;

    }

}

Explanation

rooms배열 요소 내의 방 번호를 매번 parsing하는 건 비효율적이라 int배열을 사용해 방번호를 따로 저장한다.

pos배열은 현재 들어갈 수 있는 방을 표시한다. next배열은 다음에 들어갈 수 있는 방을 표시하기 위한 배열이다. 두 번째 for문이 종료되면 다음 방을 들어가기 위해 pos에 next를 저장한다. doors의 현재 알파벳을 현재 방이 갖고 있지 않으면, pos배열에 next 배열을 저장하고 반복문을 빠져 나온다.

References

https://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=tco03_qual_rd_1