금요일에 푼 문제를 이제야 포스팅한다 ! 이번 문제는 이번주차, 즉 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의 길이
- 모든 사람의 번호가 중복없이 하나씩 들어있습니다.
입출력 예
| enter | leave | result |
|---|---|---|
| [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] |
풀이 방법
문제를 보자마자 접근 방법이 바로 생각나서 금방 풀 수 있었다 ~
퇴실 순서가 담긴 배열을 기준으로 한 명씩 퇴장 시키며 만난 사람의 수를 계산한다. 이 때, 현시점에 들어와있는 사람을 저장할 리스트를 만들어 사용하였다.
현재 계산할 퇴실시킬 사람이 입장해있는지, 즉 in 리스트에 포함되어있는지 확인한다.
만일 들어있다면, 이 사람은 현재 in 리스트에 있는 사람의 수에서 자기자신을 뺀 수만큼의 사람을 반드시 만났다. 이를 결과 배열에 반영한다. 또한 in 리스트에 남아있는 사람들도 현재 나가는 사람을 만났기 때문에 각 사람들이 만난 사람을 결과 배열에 1증가시켜준다.
만일 in 리스트에 없다면, 입실 순서가 담긴 배열을 탐색하며 현재 나가야 할 사람이 입장할 때까지 사람들을 in 리스트에 넣어준다. 즉 퇴실 시켜야 할 순서의 사람이 들어온 시점까지 입장한 사람을 모두 입장시키는 것 ! 그 후에 위의 과정을 똑같이 반복시켜주면 된다.
결국은 퇴실 명단을 기준으로 순서대로 각 사람이 퇴실할 시점에 들어와있는 사람이 in 리스트에 담기는 것이다. 현 퇴실할 사람보다 먼저 들어온 사람은 모두 반영되어있고, 퇴실 명단 순서대로 탐색하기 때문에 먼저 나간 사람 역시 모두 반영되는 것이다 !
코드
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public int[] solution(int[] enter, int[] leave) {
int[] answer = new int[enter.length];
Arrays.fill(answer, 0);
int inIndex = 0;
int outIndex;
ArrayList<Integer> in = new ArrayList<>();
for (int target : leave) {
if (!in.contains(target)) {
for (int j = inIndex; j < enter.length; j++) {
in.add(enter[j]);
if (enter[j] == target) {
inIndex = j + 1;
break;
}
}
}
outIndex = in.indexOf(target);
answer[target - 1] += in.size() - 1;
in.remove(outIndex);
for (Integer person : in) {
answer[person - 1]++;
}
}
return answer;
}
}