본문 바로가기
[ 다먹살 ]/- Coding

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

by 엉망으로살기 2021. 9. 27.
반응형

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;
    }
}

 

 

반응형

댓글