초이의 끄적끄적

유형별 문제 풀이 - 기본 자료구조 - 02. 핵심 유형 문제풀이

# 1874 스택 수열 (실버3)

-> 문제 유형 : 스택, 그리디

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

ex)
n = 8
data = 4, 3, 6, 8, 7, 5, 2, 1

result = + + + + - - + + - + + - - - - -
stack  = 1 2 3 4  4 3 5 6 6 7 8 8 7 5 2 1 

n = int(input())

count = 1
stack = []
result = []

for i in range(n): # 데이터 개수만큼 반복
    data = int(input())
    while count <= data: # 입력받은 데이터에 도달할 때까지 삽입
        stack.append(count)
        result.append('+')
        count+=1
    if stack[-1] == data: # 스택의 최상위 원소가 데이터와 같을 때 
        stack.pop()
        result.append('-')
    else: # 불가능한 경우
        print('NO')
        exit(0)
        
print('\n'.join(result)) # 가능한 경우

# 1966 프린터 큐 (실버 3)

-> 문제 유형 : 큐, 구현, 그리디

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

tc = int(input()) # 테스트케이스 개수

for i in range(tc):
    n,m = list(map(int, input().split())) # n : 문서의 개수, m : 확인하고 싶은 문서
    queue = []
    for index, i in enumerate(list(map(int, input().split()))):
        queue.append((index, i)) # (문서의 index, 중요도) 저장
    count = 0 # 인쇄한 문서 갯수

    while True:
        if queue[0][1] == max(queue, key=lambda x :x[1])[1] : # 맨앞의 문서가 현재 리스트중 중요도가 가장 높다면
            count += 1
            if queue[0][0] == m: # 그것이 확인하고 싶은 문서라면 출력
                print(count)
                break
            else: # 아니라면 갯수만 추가하고 pop 해준다
                queue.pop(0)
        else:   # 맨앞의 문서가 현재 리스트중 중요도가 높지 않다면 뒤로 보낸다
            queue.append(queue.pop(0))

# 5397 키로거 (실버 3)

-> 문제 유형 : 스택, 구현, 그리디

Point. 스택 2개를 만들어 스택 두개의 중간 지점을 커서로 간주한다.

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.

ex) <<BP<A>>Cd-

tc = int(input()) # 테스트케이스 개수

for i in range(tc):
    left_stack = [] # 스택 두개를 만들어, 스택 두개의 중간 지점을 커서로 간주합니다.
    right_stack = []
    data = input()
    for i in data:
        if i == '-': # 왼쪽 스택에서 원소를 삭제합니다
            if left_stack:
                left_stack.pop()
        elif i == '<': # 왼쪽 스택에서 오른쪽 스택으로 원소를 이동합니다.
            if left_stack:
                right_stack.append(left_stack.pop())
        elif i == '>': # 오른쪽스택에서 왼쪽 스택으로 왼소를 이동합니다.
            if right_stack:
                left_stack.append(right_stack.pop())
        else: # 왼쪽 스택에 원소를 삽입합니다.
            left_stack.append(i)
    left_stack.extend(reversed(right_stack)) # 오른쪽 스택을 뒤집어서 왼쪽 스택에 더해줍니다
    print(''.join(left_stack))