[백준/Python] 23349번: 졸업 사진

문제

https://www.acmicpc.net/problem/23349

23349번: 졸업 사진

---

문제 요약

한국항공대학교 졸업식에 참가하는 모든 사람은 비행기가 보이게 사진을 찍고 싶어한다.

 

n개의 학생 이름, 장소, 시간대 정보들이 입력 받아, 최대한 많은 사람이 촬영할 수 있도록 예상되는 혼잡 장소와 시간대를 공지한다.

 

1. 가장 많은 사람이 제출한 (장소, 시간대) 쌍을 선택한다.

2. 1번에 해당하는 장소가 여러 개라면, 사전 순으로 가장 앞에 오는 장소를 선택한다.

3. 2번에 해당하는 시간대가 여러 개라면, 그 중 가장 빠른 시간대를 선택한다.

---

코드

n = int(input()) # 제출 수

infor = {}

names = [] # 이름 중복을 체크할 배열

maxplace = [] # 동시에 곂치는 부분이 가장 큰 장소 저장 (여러 개일 경우 모두 저장)

for _ in range(n):
    name, place, start_time, end_time = input().split()
    
    # 이름 중복 체크
    if name in names:
        continue
    
    names.append(name)
    
    # infor에 입력 받은 장소 정보가 없다면, 크기 50001 리스트 할당
    if infor.get(place) is None:
        infor[place] = [0] * 50001
        
    # 입력 받은 시간 정보를 infor에 저장
    for i in range(int(start_time), int(end_time)):
        infor[place][i] += 1
        
    # maxplace가 비어 있으면 현재 입력 받은 정보를 저장 
    if not maxplace:
        maxplace.append([place, 1])
    
    # maxplace에 내용이 존재하면 꺼내서 비교 후 저장
    else:
        maxplacename, cnt = maxplace.pop() 
        # 현재까지 가장 많이 겹친 시간대가 존재하는 장소 이름, 겹친 최대 횟수
        
        # 더 많이 겹친 장소 발생 시 갱신
        if cnt < max(infor[place]):
            cnt = max(infor[place])
            maxplacename = place
            
            # 더 많이 겹친 시간대가 존재하는 장소가 발생했으므로 maxplace 비우기
            while maxplace:
                maxplace.pop()
            
        # 현재까지 겹친 최대 횟수와 입력 받은 장소의 겹친 횟수가 같을 경우
        elif cnt == max(infor[place]):
            maxplace.append([place, max(infor[place])]) # 추가로 저장
            
        maxplace.append([maxplacename, cnt])
 
# maxplace에 겹친 횟수가 같은 여러 값이 들어있을 경우, 장소 이름 순으로 정렬
maxplace = sorted(maxplace, key = lambda x:x[0])

res_place = maxplace[0][0]
res_cnt = maxplace[0][1]

for i in range(50001):
    if infor[res_place][i] == res_cnt:
        start = i
        break
for i in range(start, 50001):
    if infor[res_place][i] != res_cnt:
        end = i
        break
    
print(res_place, start, end)

---

코드 설명

1. 각 정보들을 차례로 입력 받는다.

 

2. 입력 받은 이름을 저장하는 배열 names를 생성하여 중복 입력을 방지한다.

 

3. 입력 받은 정보를 딕셔너리 infor에 Key값으로 장소 이름을, Value값으로 크기 50001 배열을 저장한다.

 

+ Value값(배열)을 모두 0으로 초기화하여 생성하고, 해당 시간대에 해당하는 부분에 1을 더해 겹친 횟수를 체크한다.

 

4. n번의 입력을 받을 때마다, 현재까지 가장 많이 겹친 시간대가 존재하는 장소와 겹친 횟수를 갱신한다.

 

4 - 1. maxplace(배열)이 비어있을 경우, [입력 받은 장소 이름, 1]을 저장한다.

 

4 - 2. 더 많이 겹친 시간대가 발생할 경우, maxplace를 새로 갱신한다.

 

4 - 3. 겹친 횟수가 같은 장소가 발생할 경우 추가로 그 장소도 maxplace에 저장한다.

 

5. 조건에 맞게 정보를 장소의 이름 순으로 정렬하고, 가장 앞에 있는 정보의 장소와 해당 시간대를 출력한다.

 

 

 

아래 블로그를 참고하여 코드를 작성했습니다.

https://0422.tistory.com/125