[프로그래머스] 입실 퇴실 -위클리 챌린지 7주차

• 입실 퇴실

문제 설명

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지 번호가 하나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 이때, 각 사람별로 반드시 만난 사람은 몇 명인지 구하려 합니다.

예를 들어 입실 명부에 기재된 순서가 [1, 3, 2], 퇴실 명부에 기재된 순서가 [1, 2, 3]인 경우,

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 2번과 3번은 반드시 만났습니다.

또 다른 예로 입실 순서가 [1, 4, 2, 3], 퇴실 순서가 [2, 1, 3, 4]인 경우,

• 1번과 2번은 반드시 만났습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 1번과 4번은 반드시 만났습니다.
• 2번과 3번은 만났는지 알 수 없습니다.
• 2번과 4번은 반드시 만났습니다.
• 3번과 4번은 반드시 만났습니다.

회의실에 입실한 순서가 담긴 정수 배열 enter, 퇴실한 순서가 담긴 정수 배열 leave가 매개변수로 주어질 때, 각 사람별로 반드시 만난 사람은 몇 명인지 번호 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ enter의 길이 ≤ 1,000
• 1 ≤ enter의 원소 ≤ enter의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.
• leave의 길이 = enter의 길이
• 1 ≤ leave의 원소 ≤ leave의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

---

입출력 예

enterleaveresult

[1,3,2]	[1,2,3]	[0,1,1]
[1,4,2,3]	[2,1,3,4]	[2,2,1,3]
[3,2,1]	[2,1,3]	[1,1,2]
[3,2,1]	[1,3,2]	[2,2,2]
[1,4,2,3]	[2,1,4,3]	[2,2,0,2]

---

입출력 예 설명

입출력 예 #1

만약, 다음과 같이 회의실에 입실, 퇴실했다면

회의실설명

[1]	1번 입실
[1, 3]	3번 입실
[3]	1번 퇴실
[2, 3]	2번 입실
[3]	2번 퇴실
[]	3번 퇴실

• 1번과 2번은 만나지 않습니다.
• 1번과 3번은 만납니다
• 2번과 3번은 만납니다.

만약, 다음과 같이 회의실에 입실, 퇴실했다면

회의실설명

[1]	1번 입실
[]	1번 퇴실
[3]	3번 입실
[2, 3]	2번 입실
[3]	2번 퇴실
[]	3번 퇴실

• 1번과 2번은 만나지 않습니다.
• 1번과 3번은 만나지 않습니다.
• 2번과 3번은 만납니다.

위 방법 외에 다른 순서로 입실, 퇴실 할 경우 1번과 2번이 만나도록 할 수도 있습니다. 하지만 2번과 3번이 만나지 않도록 하는 방법은 없습니다.

따라서

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #2

문제의 예시와 같습니다.

입출력 예 #3

• 1번과 2번은 만났는지 알 수 없습니다.
• 1번과 3번은 반드시 만났습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #4

• 1번과 2번은 반드시 만났습니다.
• 1번과 3번은 반드시 만났습니다.
• 2번과 3번은 반드시 만났습니다.

입출력 예 #5

• 1번과 2번은 반드시 만났습니다.
• 1번과 3번은 만났는지 알 수 없습니다.
• 1번과 4번은 반드시 만났습니다.
• 2번과 3번은 만났는지 알 수 없습니다.
• 2번과 4번은 반드시 만났습니다.
• 3번과 4번은 만났는지 알 수 없습니다.

package weekly_challenge;

import java.util.LinkedList;
//입실 퇴실
//https://programmers.co.kr/learn/courses/30/lessons/86048
public class enter_leave {

	public static void main(String[] args) {
		int[] enter = {1, 3, 2, 4, 6, 5, 8, 7, 9, 10};
			//{1, 10, 9, 2, 3, 8, 7, 4, 5, 6};
		int[] leave = {9, 5, 1, 10, 7, 4, 8, 6, 2, 3};
			//{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		//기댓값 8, 9, 9, 9, 8, 9, 9, 9, 8, 6
		//기댓값 9, 7, 7, 5, 5, 5, 3, 3, 1, 1
		int leaveIndex = 0;

		LinkedList<Integer> list = new LinkedList<>();
		int[][] graph = new int[enter.length][enter.length];

		for(int i=0; i<enter.length; i++) {
			list.add(enter[i]);

			while( !list.isEmpty() && list.contains(leave[leaveIndex])) {

				int leavingPerson = leave[leaveIndex];
				list.remove( list.indexOf(leavingPerson) );

				for(int j=0; j<list.size(); j++) {
					graph[ leavingPerson-1 ][ list.get(j)-1 ] = 1;
					graph[ list.get(j)-1 ][ leavingPerson-1 ] = 1;
				}

				leaveIndex++;
			}

		}

		int[] answer = new int[enter.length];
		for(int i=0; i<graph.length; i++) {
			int meet = 0;
			for(int j=0; j<graph.length; j++) {
				if(graph[i][j] != 0) {
					meet++;
				}
			}

			answer[i] = meet;
		}

		for(int x:answer)
		System.out.print(x+" ");

	}

}