[백준/20541] 앨범정리 (Python)

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

20541번: 앨범정리

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 01:50:14

 

---

 

문제 설명

 

지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든  앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. 프로그램을 실행시키면 "album" 앨범부터 시작하여 명령어들을 통해 앨범 삭제/추가, 사진 삭제/추가, 현재앨범 이동 등을 할 수 있다. 앨범정리 프로그램은 다음과 같은 명령어 들로 구성 되어 있다. 수행할 명령어의 개수 N이 주어질 때 각 명령어 수행 후 문자열 출력이 필요한 명령어에 대해서 문자열을 출력한다.

1. mkalb
* 명령어 수행후: 현재 앨범에 속해있는 앨범 중 동일한 이름을 가진 앨범이 존재하여 앨범이 생성되지 않았으면 "duplicated album name"을 출력합니다. 그렇지 않다면 아무것도 출력하지 않습니다.

* mkalb S
현재 앨범에 S의 이름을 가진 앨범을 생성합니다.
현재 앨범에 속해있는 앨범 중 동일한 이름을 가진 앨범이 존재하면 앨범을 생성하지 않습니다.

2. rmalb
* 명령어 수행후: 삭제된 앨범의 개수와 사진의 개수를 공백으로 구분하여 출력합니다.
* rmalb S

현재 앨범에 속해있는 앨범 중 S의 이름을 가진 앨범이 존재한다면, 해당 앨범을 삭제합니다.
삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.

* rmalb -1
현재 앨범에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 빠른 앨범을 삭제 합니다.
삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
* rmalb 0
현재 앨범에 속해있는 모든 앨범을 삭제 합니다.
삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.
* rmalb 1
현재 앨범에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 늦은 앨범을 삭제 합니다. 
삭제된 앨범에 속한 모든 앨범과 사진들 또한 삭제됩니다.

 

3. insert
* 명령어 수행후: 현재 앨범에 속해있는 사진 중에 동일한 이름을 가진 사진이 존재하여 사진이 삽입되지 않았으면 "duplicated photo name"을 출력합니다. 그렇지 않다면 아무것도 출력하지 않습니다.
* insert S
현재 앨범에 S의 이름을 가진 사진을 삽입합니다.
현재 앨범에 속해있는 사진 중 동일한 이름을 가진 사진이 존재하면 사진을 삽입하지 않습니다.

 

4. delete
* 명령어 수행후: 삭제된 사진의 개수를 출력합니다.
* delete S
현재 앨범에 속해있는 사진 중 S 의 이름을 가진 사진이 존재한다면, 해당 사진을 삭제합니다.
* delete -1
현재 앨범에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 빠른 사진을 삭제 합니다.
* delete 0
현재 앨범에 속해있는 모든 사진을 삭제합니다.
* delete 1
현재 앨범에 속해있는 사진이 존재한다면, 이름이 사전순으로 가장 늦은 사진을 삭제 합니다. 

 

5. ca
* 명령어 수행후: 현재 앨범 이름을 출력합니다.
* ca S
현재 앨범에 속해있는 앨범 중 S의 이름을 가진 앨범으로 이동합니다.
현재 앨범에 속해있는 앨범 중 S의 이름을 가진 앨범이 없다면 현재 앨범에 머무릅니다.

* ca ..
현재 앨범의 상위 앨범으로 이동합니다.
현재 앨범이 최상위 앨범인 "album" 앨범이라면 현재 앨범에 머무릅니다.
* ca /
최상위 앨범인 "album" 앨범으로 이동합니다.

"A가 B에 속해있다"라는 것은 A의 바로 하위에 B가 있다는 것을 의미합니다. 만약 A가 B에 속해있고, B가 C에 속해있는 경우, A는 C에 속해 있는 것이 아닙니다. 

 

입력 및 출력

 

입력

첫째 줄에 수행할 명령어의 개수 N이 주어진다.
다음줄 부터 N줄에 걸쳐 앨범정리 프로그램의 명령어가 주어진다.

 

출력

문제 본문에 나와있는 앨범정리 프로그램 명령어의 설명에 따라 적절한 문자열을 출력한다.

 

입력 예시

24
mkalb animal
mkalb insect
ca animal
mkalb sky
mkalb land
mkalb ocean
ca land
insert elephant
insert tiger
insert banana
delete banana
ca elephant
ca ..
ca ocean
insert whale
ca /
ca insect
mkalb land
mkalb sky
ca ocean
ca ..
ca ..
rmalb -1
rmalb -1

 

출력 예시

animal
land
1
land
animal
ocean
album
insect
insect
album
album
4 3
3 0

 

 

---

 

풀이

 

간만에 '재미있다'라고 생각하고 풀었던 문제. 실제 파일탐색 프로그램을 만들면 이런 기본적인 사항을 고려해야하겠거니 싶다.

시간이 발목을 잡아서 조금 아쉬웠던 문제. 내 코딩 속도가 느리다는 점을 조금 눈여겨봐야 할 것 같다.

 

기본적으로는 하나의 앨범이 여러 앨범과 파일을 거느리고 있으며, 이들 중 앨범 구조는 계층적이다. 즉 앨범을 디렉토리 트리라고 보고 구현을 시작해보자.

 

여기서 delete, rmalb 명령어를 주의할 필요가 있다. 이들 명령어는 '사전순으로 가장 앞서는' 정보 및 '사전순으로 가장 뒤에 있는' 정보를 요구한다. 즉 사전순 최솟값 및 최댓값을 앨범, 파일 단으로 효율적으로 반환할 수 있어야 한다. 파이썬의 기본적인 sort method는 극단적인 insert 및 delete 상황에서 시간 내에 풀이를 보장할 수 없다. 실제로도 많은 시행착오를 겪었었고...

 

따라서 항시 O(logN) 시간복잡도 내에 최솟값 혹은 최댓값을 반환하는 힙 자료구조를 눈여겨보게 됬다. 힙 자료구조는 그 특성상 최상위 노드 삭제 및 재정렬, 그리고 새로운 노드의 삽입에 평균 logN의 시간이 소요된다. 따라서 insert 및 delete 상황에 유연하게 대처할 수 있다.

 

하지만 힙 하나로는 최댓값 혹은 최솟값 하나만으로 정렬 가능하므로, 우리는 최대 힙 및 최소 힙을 동시에 사용할 필요가 있다. (파이썬의 heapq 모듈은 최소 힙만 지원하므로, 스트링 비교연산자를 거꾸로 반환하는 클래스를 선언하여 최대 힙을 구현하였다. 힙의 정렬기준은 비교연산으로 진행되고, 이 비교연산 결과만 정의되면 두 클래스간의 비교를 진행할 수 있다.

 

그렇다면 다음 상황을 가정해야한다. 최소 힙에서 이미 삭제된 노드의 경우 최대 힙에서 반환할 때 어떻게 접근해야 할까? 일일히 노드를 반영하는 것은 O(NlogN)의 비싼 비용이 든다. 따라서 다음 편법으로 파일 집합 구조를 선언하였다. 공통적으로 인자 검사 ('node in set')에 O(1)의 시간복잡도가 소요되며, 최소 힙 및 최대 힙에서 원소를 꺼낼 때 파일 집합 구조에 있는 원소가 나올 때까지 원소 삭제를 진행한다. 즉 느린 업데이트를 하는 셈이다.

 

이상의 요소들을 고려하여 문제를 풀이할 수 있겠다.

 

풀이 코드

from heapq import heappush, heappop, heapify
import sys

input = sys.stdin.readline


class maxstr():
  def __init__(self, string):
    self.string = string

  def __lt__(self, other):
    return self.string.__gt__(other.string)

  def __le__(self, other):
    return self.string.__ge__(other.string)

  def __eq__(self, other):
    return self.string.__eq__(other.string)


class directory():

  def __init__(self, S, parent, base):
    self.name = S
    
    self.maxfiles = list()
    self.minfiles = list()
    self.file_set = set()
    
    self.childs = dict()
    self.maxchild = list()
    self.minchild = list()
    self.parent = parent
    self.base = base

  def mkalb(self, S):
    if S in self.childs:
      return False
    else:
      heappush(self.minchild, S)
      heappush(self.maxchild, maxstr(S))
      self.childs[S] = directory(S, self,
              self.base if self.base is not None else self)
      return True

  def _rmalb(self, ):
    dir_result, file_result = 1, len(self.file_set)
    for key in self.minchild:
      if key not in self.childs :
        continue
      tdir, tfile = self.childs[key]._rmalb()
      dir_result += tdir
      file_result += tfile
      del self.childs[key]
    return dir_result, file_result

  def rmalb(self, option):
    dir_result, file_result = 0, 0
    if option in ['-1', '1']:
      if self.childs:
        if option == '-1':
          key = heappop(self.minchild)
          while key not in self.childs and self.minchild :
            key = heappop(self.minchild)
        else:
          key = heappop(self.maxchild).string
          while key not in self.childs and self.maxchild :
            key = heappop(self.maxchild).string
        dir_result, file_result = self.childs[key]._rmalb()
        del self.childs[key]
    elif option == '0':
      for key in self.minchild:
        if key not in self.childs :
          continue
        tdir, tfile = self.childs[key]._rmalb()
        dir_result += tdir
        file_result += tfile
        del self.childs[key]
      self.minchild = list()
      self.maxchild = list()
      self.childs = dict()
    else:
      if option in self.childs:
        dir_result, file_result = self.childs[option]._rmalb()
        del self.childs[option]
    return dir_result, file_result

  def insert(self, filename):
    if filename in self.file_set:
      return False
    else:
      heappush(self.minfiles, filename)
      heappush(self.maxfiles, maxstr(filename))
      self.file_set.add(filename)
      return True

  def delete(self, option):
    delete_num = 0
    if option in ['-1', '1']:
      if self.file_set:
        if option == '-1':
          key = heappop(self.minfiles)
          while key not in self.file_set and self.minfiles :
            key = heappop(self.minfiles)
        else:
          key = heappop(self.maxfiles).string
          while key not in self.file_set and self.maxfiles :
            key = heappop(self.maxfiles).string
        self.file_set.discard(key)
        delete_num += 1
    elif option == '0':
      delete_num += len(self.file_set)
      self.minfiles = list()
      self.maxfiles = list()
      self.file_set = set()
    else:
      if option in self.file_set:
        self.file_set.discard(option)
        delete_num += 1
    return delete_num

  def ca(self, option):
    if option == '..':
      return self.parent if self.parent != None else None
    elif option == '/':
      return self.base if self.base != None else None
    else:
      if option not in self.childs:
        return None
      else:
        return self.childs[option]


N = int(input())
base_album = directory('album', None, None)
cur_dir = base_album
for _ in range(N):
  func, option = input().split()
  if func == 'mkalb':
    result = cur_dir.mkalb(option)
    if not result:
      print('duplicated album name')
  elif func == 'rmalb':
    dir_result, file_result = cur_dir.rmalb(option)
    print(dir_result, file_result)
  elif func == 'insert':
    result = cur_dir.insert(option)
    if not result:
      print('duplicated photo name')
  elif func == 'delete':
    result = cur_dir.delete(option)
    print(result)
  elif func == 'ca':
    result = cur_dir.ca(option)
    if result is not None:
      cur_dir = result
    print(cur_dir.name)

풀이 완료!