[백준] 23294 - 웹 브라우저 1

1. 문제

23294번: 웹 브라우저 1

2. 개요

큐, 덱 활용 문제.

큐 배울 때 예시로 많이 나오는 웹페이지 뒤로 가기, 앞으로 가기 + 접속, 압축까지 구현하면 된다.

3. 코드 및 추가내용

import sys
from collections import deque

N, Q, C = map(int, sys.stdin.readline().split())

caps = list(map(int, sys.stdin.readline().split()))

usingcash = 0
_blist, _flist = deque(), deque()
_now = 0

def backward(page):
    if len(_blist) == 0:
        return page

    _flist.appendleft(page)
    now = _blist.popleft()

    return now

def frontward(page):
    if len(_flist) == 0:
        return page

    _blist.appendleft(page)
    now = _flist.popleft()

    return now

def access(page, next, cash, flag):
    cash -= sum([caps[f-1] for f in _flist])
    _flist.clear()

    now = next
    cash += caps[now-1]

    if flag and page != 0:
        _blist.appendleft(page)
        
        while cash > C:
            cash -= caps[_blist.pop()-1]

    return now, cash

def compress(cash):
    tmplist = deque()

    for b in _blist:
        if len(tmplist) == 0 or tmplist[-1] != b:
            tmplist.append(b)
        else:
            cash -= caps[b-1]
    
    return cash, tmplist

flag = False
for i in range(Q):
    command = sys.stdin.readline().split()

    if command[0] == 'B':
        _now = backward(_now)

    elif command[0] == 'F':
        _now = frontward(_now)

    elif command[0] == 'A':
        _now, usingcash = access(_now, int(command[1]), usingcash, flag)
        if flag == False: flag = True

    else:
        usingcash, _blist = compress(usingcash)

    
print(_now)
print(*_blist) if _blist else print(-1)
print(*_flist) if _flist else print(-1)

사용 중인 캐시용량, 현재 페이지를 0으로 초기값을 잡고,

앞으로 가기, 뒤로 가기 리스트를 각각 큐(덱)으로 만든다.

앞, 뒤로가기의 경우 각각의 큐가 비어있다면 현재 페이지를 그대로 반환해 사실상 아무런 작동도 하지 않고, 큐에 뭔가 있다면 현재 페이지를 반대쪽 큐에 넣고 큐에서 뽑아온 페이지를 현재 페이지로 갱신한다.

Access의 경우 Flag가 False라면 웹 페이지 접속이 처음이라는 뜻으로 현재 페이지를 갱신하고 캐시 사용 용량을 늘려주고 Flag를 True로 갱신한다.

다음부터 [Flag가 True인 경우] 현재 페이지를 뒤로가기 큐에 넣고 만약 캐시 용량이 초과되었다면 가장 오래된 페이지 (큐 삽입을 appendleft로 했으니 pop으로 빼온 페이지)를 없애고 그만큼의 캐시 용량을 줄여주는 것을 사용중인 캐시 용량이 최대용량 이하가 될 때 까지 반복한다.

Compress의 경우 임시 리스트를 만들고 뒤로가기 큐의 페이지들을 탐색하면서 페이지를 임시 리스트에 넣는데, 마지막 페이지와 같다면 넣지 않고 용량을 빼주는 작업을 진행한다.

작업이 끝났다면 이 임시 리스트를 반환해 뒤로가기 큐로 바꿔준다.

명령에 맞게 함수들을 실행하고 출력하면 끝.