[PS] [Baekjoon] 20541. 앨범 정리

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

 

언어 : 파이썬 (Python)

시작 : 2024.12.19 03:00

종료 : 2024.12.19 08:30

티어 : Platinum V

비고 : 2020 인하대학교 프로그래밍 경진대회 (IUPC) C번

 

태그 :

구현, 문자열, 트리, 최소 힙, 정렬

문제 해석

 

문제가 굉장히 길다

간단히 설명하자면 앨범, 사진 두 가지가 있고, 앨범은 폴더에 대응되는 개념이다.

우리가 할 건 앨범 관리 프로그램을 만드는 것.

 

명령어는 총 5가지.

- 앨범 생성/삭제

- 사진 생성/삭제

- 앨범으로 이동

 

각 명령에 대한 명세는 내가 요약하기 보단 직접 읽어보는 게 훨씬 낫다. 조건이 너무 많으므로.

그러나 내가 생각하기에 유의해야할 점 3가지는...

 

1) 앨범 삭제 명령 시 해당 앨범은 물론이고 하위에 있는 사진, 앨범들까지 전부 삭제된다.

2) 앨범으로 이동(ca)하는 건 한 계단씩만 가능. A -> B -> C 구조의 앨범이라면 A -> C로 바로 이동할 순 없다.

3) 명령어의 수가 최대 10만개다! 이론상 한 앨범에서 5만개의 사진이 생성되고 지워질 수 있다. 즉, $O(N^2)$ 연산은 불가능.

풀이

 

크게 어려울 것도 없고 DFS나 BFS같은 알고리즘을 활용해야할 문제도 아닌지라,

그냥 클래스 만들어 간단하게 구현해서 제출했으나 바로 시간 초과. (풀이 1)

 

질문 게시판에서 조금 서칭을 해보니, 시간 초과는 알파벳 순에 따른 삭제에서 발생했다.

하긴 그렇긴 했다. 풀이 1은 삭제 연산마다 매번 sort를 해줬으니,

1만개의 앨범에 대해 1만번 정도만 삭제해줘도 바로 시간초과가 나올 것이다.

 

 

그래서 구상한 아이디어는 이렇다.

 

1) 생성된 앨범 이름을 저장하는 set를 만든다. 삭제와 삽입이 $O(1)$이다.

2) 앨범 이름을 저장하는 최소 힙을 2개 만든다. 하나는 알파벳 순, 하나는 그의 역순.

3) 삭제 시 해당하는 힙에서 pop한다.

4) pop된 앨범의 이름이 앨범 이름 set에 있을 때까지 pop을 계속 반복한다.

 

앨범과 사진 두 곳 모두에 적용하면 된다.

 

 

문제는 파이썬의 heapq는 최대 힙을 지원하지 않는다는 것...

int는 음수로 바꾸는 편법이 통했으나 문자열은 그게 아니므로,

구글링을 통해 string의 연산을 바꾸는 방법을 알아냈다.

이걸로 문자열도 최대 힙을 구현할 수 있다.

 

https://stackoverflow.com/questions/58714310/python-max-heap-of-strings

Python max heap of strings

 

P.S.

난이도가 플레티넘 5던데, 위 아이디어를 떠올리기 힘들어서 그런듯.

물론 클래스 개념에 익숙하지 않았다면 구현 자체도 어려웠을 것이다.

 

다른 사람이 구현한 걸 보니 이름 저장하는 구조체를 abc -> bcd -> cde ... -> hij 식으로 LinkedList처럼 구현해놨다.

이 것도 나쁘지 않은 아이디어인듯 하다.

코드

 

풀이 1) 시간 초과

import sys
input = sys.stdin.readline


class Album():
    def __init__(self, upper, name):
        self.name = name
        self.upper = upper
        self.albums = dict()
        self.pictures = set()

    def get_albums_dict(self):
        return self.albums

    def get_pictures_set(self):
        return self.pictures

    def get_album(self, name):
        if name in self.albums:
            return self.albums[name]
        else:
            return None

    def get_picture(self, name):
        if name in self.pictures:
            return True
        else:
            return None

    def create_album(self, name):
        self.albums[name] = Album(self, name)

    def clear_album(self):
        cnt_albums, cnt_pictures = 0, 0
        for name in self.albums.keys():
            a, b = self.albums[name].clear_album()
            cnt_albums += a
            cnt_pictures += b

        cnt_albums += 1
        cnt_pictures += len(self.pictures)

        self.albums.clear()
        self.pictures.clear()

        return (cnt_albums, cnt_pictures)

    def insert_picture(self, name):
        self.pictures.add(name)

    def delete_picture(self, name):
        self.pictures.remove(name)


N = int(input())

root = Album(None, "album")
now_album = root

for _ in range(N):

    cmd = input().rstrip().split()

    if cmd[0] == 'mkalb':
        if now_album.get_album(cmd[1]):
            print('duplicated album name')
        else:
            now_album.create_album(cmd[1])
    elif cmd[0] == 'rmalb':
        cnt_albums, cnt_pictures = 0, 0
        album_names = now_album.get_albums_dict().keys()
        if album_names:
            target = list()
            if cmd[1] == '-1':
                target.append(sorted(list(album_names))[0])
            elif cmd[1] == '0':
                target = list(album_names)
            elif cmd[1] == '1':
                target.append(sorted(list(album_names))[-1])
            elif cmd[1] in album_names:
                target.append(cmd[1])

            for name in target:
                a, b = now_album.get_album(name).clear_album()
                del now_album.get_albums_dict()[name]
                cnt_albums += a
                cnt_pictures += b

        print(cnt_albums, cnt_pictures)
    elif cmd[0] == 'insert':
        if now_album.get_picture(cmd[1]):
            print('duplicated photo name')
        else:
            now_album.insert_picture(cmd[1])
    elif cmd[0] == 'delete':
        cnt_pictures = 0
        picture_sets = now_album.get_pictures_set()
        if picture_sets:
            target = list()
            if cmd[1] == '-1':
                target.append(sorted(list(picture_sets))[0])
            elif cmd[1] == '0':
                target = list(picture_sets)
            elif cmd[1] == '1':
                target.append(sorted(list(picture_sets))[-1])
            elif cmd[1] in picture_sets:
                target.append(cmd[1])

            for name in target:
                now_album.delete_picture(name)
                cnt_pictures += 1

        print(cnt_pictures)
    elif cmd[0] == 'ca':
        if cmd[1] == '..':
            if now_album.upper is not None:
                now_album = now_album.upper
        elif cmd[1] == '/':
            now_album = root
        elif now_album.get_album(cmd[1]):
            now_album = now_album.get_album(cmd[1])

        print(now_album.name)

 

풀이 2) 정답, 556ms

import sys
import heapq
input = sys.stdin.readline


class ReversedStr(str):
    def __lt__(self, other):
        return self.__gt__(other)

class Album():
    def __init__(self, upper, name):
        self.name = name
        self.upper = upper
        self.albums = dict()
        self.album_names = set()
        self.album_heap_min = list()
        self.album_heap_max = list()

        self.pictures = set()
        self.picture_heap_min = list()
        self.picture_heap_max = list()

    def get_albums_dict(self):
        return self.albums

    def get_pictures_set(self):
        return self.pictures

    def get_album(self, name):
        if name in self.album_names:
            return self.albums[name]
        else:
            return None

    def get_picture(self, name):
        if name in self.pictures:
            return True
        else:
            return None

    def create_album(self, name):
        self.albums[name] = Album(self, name)
        self.album_names.add(name)
        heapq.heappush(self.album_heap_min, ReversedStr(name))
        heapq.heappush(self.album_heap_max, name)

    def clear_album(self):
        cnt_albums, cnt_pictures = 0, 0
        for name in self.albums.keys():
            a, b = self.albums[name].clear_album()
            cnt_albums += a
            cnt_pictures += b

        cnt_albums += 1
        cnt_pictures += len(self.pictures)

        self.albums.clear()
        self.pictures.clear()
        self.album_names.clear()
        self.album_heap_max.clear()
        self.album_heap_min.clear()
        self.picture_heap_max.clear()
        self.picture_heap_min.clear()

        return (cnt_albums, cnt_pictures)

    def insert_picture(self, name):
        self.pictures.add(name)
        heapq.heappush(self.picture_heap_min, ReversedStr(name))
        heapq.heappush(self.picture_heap_max, name)

    def delete_picture(self, name):
        self.pictures.remove(name)



def pop_heap(heap, check):
    while heap:
        target = heapq.heappop(heap)
        if target in check:
            return target


N = int(input())

root = Album(None, "album")
now_album = root

for _ in range(N):

    cmd = input().rstrip().split()

    if cmd[0] == 'mkalb':
        if now_album.get_album(cmd[1]):
            print('duplicated album name')
        else:
            now_album.create_album(cmd[1])
    elif cmd[0] == 'rmalb':
        cnt_albums, cnt_pictures = 0, 0
        if now_album.album_names:
            target = list()
            if cmd[1] == '-1':
                target.append(pop_heap(now_album.album_heap_max, now_album.album_names))
            elif cmd[1] == '0':
                target = list(now_album.album_names)
            elif cmd[1] == '1':
                target.append(pop_heap(now_album.album_heap_min, now_album.album_names))
            elif cmd[1] in now_album.album_names:
                target.append(cmd[1])

            for name in target:
                a, b = now_album.albums[name].clear_album()
                del now_album.albums[name]
                now_album.album_names.remove(name)
                cnt_albums += a
                cnt_pictures += b

        print(cnt_albums, cnt_pictures)
    elif cmd[0] == 'insert':
        if now_album.get_picture(cmd[1]):
            print('duplicated photo name')
        else:
            now_album.insert_picture(cmd[1])
    elif cmd[0] == 'delete':
        cnt_pictures = 0
        picture_sets = now_album.get_pictures_set()
        if picture_sets:
            target = list()
            if cmd[1] == '-1':
                target.append(pop_heap(now_album.picture_heap_max, picture_sets))
            elif cmd[1] == '0':
                target = list(picture_sets)
            elif cmd[1] == '1':
                target.append(pop_heap(now_album.picture_heap_min, picture_sets))
            elif cmd[1] in picture_sets:
                target.append(cmd[1])

            for name in target:
                now_album.delete_picture(name)
                cnt_pictures += 1

        print(cnt_pictures)
    elif cmd[0] == 'ca':
        if cmd[1] == '..':
            if now_album.upper is not None:
                now_album = now_album.upper
        elif cmd[1] == '/':
            now_album = root
        elif cmd[1] in now_album.album_names:
            now_album = now_album.albums[cmd[1]]

        print(now_album.name)