문제 설명
사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.
오늘 회의실에는 총 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] |
입출력 예 설명
입출력 예 #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번은 만났는지 알 수 없습니다.
풀이 방법 생각
입실, 퇴실 시에 만났는지 알 수 없을 경우 만나지 않는다는 가정하에 set을 방이라고 생각하고 순서대로 입실, 퇴실을 반복했습니다.
그래서 입실할 때 그 사람이 만나는 사람 수를 에서주고 다음 사람이 입실하게 되면 방에 있는 사람들이 만나는 사람 수를 1 증가해줬습니다.
내 코드
import java.util.HashSet;
import java.util.Iterator;
class Solution {
public int[] solution(int[] enter, int[] leave) {
int total = enter.length;
int[] answer = new int[total];
HashSet<Integer> set = new HashSet<>();
int enterCount = 0;
int leaveCount = 0;
while (enterCount < total && leaveCount < total) {
if (set.contains(leave[leaveCount])) {
set.remove((Integer) leave[leaveCount]);
leaveCount++;
} else {
set.add(enter[enterCount++]);
if (set.size() > 1) {
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
answer[it.next() - 1]++;
}
}
answer[enter[enterCount - 1] - 1] = set.size() - 1;
}
}
return answer;
}
}
다른 사람 풀이
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] solution(int[] enter, int[] leave) {
Set<Integer> set = new HashSet<>();
int[] count = new int[enter.length];
int i = -1;
int j = 0;
while(j < leave.length) {
if (set.contains(leave[j])) {
set.remove(leave[j]);
count[leave[j]-1] += set.size();
for (int s : set) count[s-1]++;
j++;
} else {
while (++i < enter.length) {
set.add(enter[i]);
if (enter[i] == leave[j]) break;
}
}
}
return count;
}
}
내 풀이와 동일하게 일단 set을 방이라고 두고 풀이했고 1 씩 증가하도록 했다.
하지만 나는 넣을 때 방에 사람 수를 더해주었지만 이 풀이는 사람이 퇴실할 때 사람 수를 더해주었다.
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
전력망을 둘로 나누기 (0) | 2021.10.07 |
---|---|
최소직사각형 (0) | 2021.10.06 |
실패율 (0) | 2021.09.13 |
후보키 (0) | 2021.09.13 |
오픈채팅방 (0) | 2021.09.13 |