https://programmers.co.kr/learn/courses/30/lessons/86048?language=java
코딩테스트 연습 - 7주차_입실 퇴실
사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는
programmers.co.kr
위클리챌린지를 계속 풀고 있는데 레벨 1~2 왔다갔다하는 것 같다. 3주차인가 4주차 문제가 좀 어려웠는데 나중에 순차적으로 도전해봐야겠다.
이 문제는 일단 제한조건 최대 1000으로 고정되어있었기 때문에 2중 반복문을 사용하는 데 무리가 없었을거라고 판단했고, 시간 초과가 뜨지 않았다. 신기하게 테스트케이스가 굉장히 많았다. (전체를 캡쳐해보려고 했는데 너무 많아서 중간에 짤렸다.)
1. Queue나 ArrayList 등 다른 선형구조를 이용해서 풀 수도 있을 것 같다. 나는 사람의 수만큼 2차원 배열(room)을 생성하고 거기에 사람의 출입여부를 저장했다.
1-1. 사람은 1번부터 시작하고 배열은 0번부터 인덱스가 시작하기 때문에 항상 이 부분을 유의했다.
1-2. room[i][i] : 사람이 방에 있는 지 체크 (같은 인덱스)
room[i][j] : i-1번쨰 사람이 방에 있을 때, j-1번째 사람도 방에 있는지 체크
1-3. Queue (in) : enter 배열로 받은 사람 = 방으로 들어가기 위해 기다리고 있는 사람
Queue (out) : leave 배열로 받은 사람 = 일단 방에 들어왔다가 방에서 나가는 사람
2. 반복문은 사람의 출입을 모두 더했을 때로 설정했다.
2-1. 이 때, 인덱스를 중간중간에 체크하기 위해 변수 index를 사용했다.
3. 방에서 나가려면 일단 방으로 들어와야 한다는 조건이 있기 때문에 퇴실이 우선순위가 높았다.
3-1-1. 방에서 나가려는 사람(Queue - out)의 인덱스가 현재 방에 있을 경우 계속 방에서 내보내는 처리(room[i][i]=0으로 갱신)를 해준다.
3-1-2. 이 때, 방에 남아있는 사람을 구하기 위해 isIn 메소드를 이용해서 결과 배열에 넣어준다.
3-2-1. 나갈 사람의 조건이 불만족하고, 아직 들어올 사람이 남아있는 경우(Queue-in가 empty가 아닐 때) 때에는 차례대로 방으로 들어오는 처리(room[i][i]=1으로 갱신)를 해준다.
3-2-2. 이 때, 이미 방에 들어온 사람들의 인덱스에 해당하는 배열값도 전부 1로 바꿔준다.
문제
제한조건 및 입출력
코드
import java.util.LinkedList;
import java.util.Queue;
class Solution
{
// 사람이 나갈 때 몇 명과 마주쳤는지 계산
public static int isIn(int[] arr)
{
int cnt = 0;
for(int d : arr)
{
if(d!=0)
{
cnt++;
}
}
return cnt;
}
public int[] solution(int[] enter, int[] leave)
{
// 예외 : 한 명만 있을 때
if(enter.length==1)
{
return new int[]{0};
}
// 사람 수만큼 2차원 배열생성
int[][] room = new int[enter.length][enter.length];
// 결과 출력용 배열
int[] arr = new int[enter.length];
// 루프 종료조건(들어온 횟수+나간횟수)
int total_cnt = 0;
// 들어온 사람과 나간 사람을 따로 queue로 사용
Queue<Integer> in = new LinkedList<Integer>();
Queue<Integer> out = new LinkedList<Integer>();
for(int d : enter)
{
in.add(d);
}
for(int d : leave)
{
out.add(d);
}
// 들어온 횟수+나간 횟수가 아래 처리한 횟수와 동일할 때까지 루프
while(total_cnt!=enter.length+leave.length)
{
int index = 0;
// 나간 사람을 우선처리(나갈 사람이 큐와 방 안에 있을 때만 퇴장처리 가능)
while(!out.isEmpty() && room[out.peek()-1][out.peek()-1]!=0)
{
// 인덱스 계산 후, 퇴장한 사람을 방에서 없애주는 처리를 한 후 몇 명과 만났는 지 isIn 메소드를 사용해 계산 후 출력
index = out.poll()-1;
room[index][index]--;
arr[index] = isIn(room[index]);
total_cnt++;
}
// 나갈 사람이 없고, 들어올 사람이 남아있으면 로직 처리
if(!in.isEmpty())
{
// 인덱스 계산 후, 방에 들어왔다는 표시처리 후 현재 방에 있는 사람들에 대해서 연결
index = in.poll()-1;
room[index][index] = 1;
total_cnt++;
for(int i=0; i<enter.length; i++)
{
if(room[i][i]==1)
{
room[i][index] = 1;
room[index][i] = 1;
}
}
}
}
return arr;
}
}
'[ 다먹살 ] > - Coding' 카테고리의 다른 글
[프로그래머스] 위클리챌린지 5주차 모음사전 (0) | 2021.09.29 |
---|---|
[프로그래머스] 레벨2 조이스틱 (0) | 2021.09.28 |
[프로그래머스] 위클리챌린지 8주차 최소직사각형 (0) | 2021.09.27 |
[프로그래머스] 레벨2 큰 수 만들기 (0) | 2021.09.27 |
[프로그래머스] 레벨1 체육복 (0) | 2021.09.24 |
댓글