[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]

---

💡 문제 풀이

 

이번 문제는 그리디 문제인것 같다. 제한 사항이 널널해서 이중 반복문으로 풀었다.

1. 회의실에 퇴실할 사람이 존재하지 않으면 => 입실, 2번으로 이동
    1-1. 존재하면 => 퇴실
2. 마주친 사람을 딕셔너리로 관리(key: 배열의 인덱스, value: 마주친 사람)
     2-1. 입실한 사람이 회의실에 처음 들어오면 자기 자신을 제외한 회의실에 있는 모든 사람을 마주침
     2-2. 이미 존재하는 사람은 기존에 마주친 사람들에서 새로 들어온 사람(1명)이 추가됨
3. 2에서 구한 딕셔너리를 key 기준 오름차순 정렬 후 모든 value 값 반환
4. 위 과정을 회의실에 enter에 있는 값이 모두 들어올 때까지 반복함

 

def solution(enter, leave):
    room = []
    info = {}
    e, l = 0, 0 #입실, 퇴실
    
    #4
    while e < len(enter):
        #1
        if leave[l] not in room:
            room.append(enter[e])
            
            #2
            for i in range(len(room)):
                #2-1
                if room[i] not in info:
                    info[room[i]] = len(room) -1
                #2-2
                else:
                    info[room[i]] +=1
            e+=1
        
        #1-1
        else:
            room.remove(leave[l])
            l+=1 
     
    #3
    sortedInfo = dict(sorted(info.items(), key = lambda x:x[0]))
    return list(sortedInfo.values())

---

📜 후기

 

이번주 위클리 문제는 방에 이미 존재하는 사람들이 마주치는 사람 수를 구하는 부분에서 살짝 헤맸다.

하다가 잠이 너무 와서 중단하고 저녁에 다시 풀었는데 10분 만에 위와 같은 방식으로 해결했다 :)