쌉쌀한 무화과의 개발로그

[문제 설명]

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다.

입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

오늘 회의실에는 총 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의 길이

모든 사람의 번호가 중복없이 하나씩 들어있습니다.

[입출력 예]

입출력 예 설명

입출력 예 1

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

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

1번과 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번은 만났는지 알 수 없습니다.

>문제 풀이

n명이 회의실에 들어왔다가 나가는데, i번째 사람이 반드시 만난 사람이 몇명인지 사람의 번호 순서대로 answer[] 배열에 담아서 return

​

- 입실과 퇴실은 동시에 이루어지지 않는다.

- 두번 이상 입실한 사람은 없다

​

>문제 풀이

[1, 4, 2, 3] - [2, 1, 3, 4]

들어왔다가 나가는 리스트를 구해보면

: 1, 4, 2, 2, 1, 3, 3, 4 : 이렇게 됩니다.

​

ex) 1번의 입장에서는 입실 시, 방 안에 아무도 없고 이후에 4, 2 번을 만나고 퇴실합니다. 즉 2명

ex) 2번의 입장에서는 입실 시, 방 안에 있던 1, 4번을 만나고 이후에 퇴실하게 됩니다. 즉, 2명

ex) 3번의 입장에서는 입실 시, 방 안에 있던 4번을 만나고 이후에 퇴실하게 됩니다. 즉, 1명

ex) 4번의 입장에서는 입실 시, 방 안에 있던 1번을 만나고 이후에 2, 3번을 만나게 됩니다. 즉 3명

​

전에 들어와있던 애 + 앞으로 나가기 전에 들어온 애들

answer[i]= (i이 들어가기 전에 방 안에 있는 사람)+ (i가 들어오고나서 나갈 때까지 만난 사람)

>전체 코드

import java.util.LinkedList;
import java.util.HashSet;
class Solution {
    public int[] solution(int[] enter, int[] leave) {
        int[] answer = new int[enter.length];
        LinkedList<Integer> list= new LinkedList<>();
        
        //입퇴실 순서를 list에 넣기
        for(int i=0, j=0; i<enter.length||j<leave.length;){ 
            if(list.isEmpty()){
                list.add(enter[i++]);
                continue;
            }
            if(list.contains(leave[j])){
                list.add(leave[j++]);
            }else{
                list.add(enter[i++]);
            }
        }
        
        HashSet<Integer> remainSet= new HashSet<>(); //방 안에 있던 사람
        HashSet<Integer> rangeSet= new HashSet<>();  //새로 만나는 사람
        for(int i=0; i<list.size(); i++){
            int num= list.get(i);   //i번째 사람
            if(remainSet.contains(list.get(i))){ //이미 입실한 적 있으면 퇴실
                remainSet.remove(num);
                continue;
            }
            remainSet.add(num); //처음 입실
            for(int j=i+1; j<list.size(); j++){ //입실 후 퇴실까지 만난 사람들
                if(list.get(j)==num) break;
                rangeSet.add(list.get(j));
            }
            rangeSet.addAll(remainSet); //두 set을 합친다.(방안+새로만난)
            answer[num-1]= rangeSet.size()-1; //set에 나 자신도 포함됨, 빼주기
            rangeSet.clear();
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/86048

+) 나쁘지 않은 구조로 짰다고 생각했는데 더 컴팩트하게 구현하신 분들도 계시더라고요.

코드는 그냥 이 사람은 이렇게 짰구나 참고만 해주세요:)