자료구조 - 1158, 1406, 2346, 5397, 2493

1158번. 요세푸스 문제 (https://www.acmicpc.net/problem/1158)

원으로 구성되어 있으므로, FIFO 구조의 Queue를 사용하여 문제를 풀 수 있다.

• Queue에 1번부터 N번까지 숫자를 저장한다.
• Queue에서 숫자를 하나씩 뽑아낸다.
  • count%N이 아닌 경우, Queue에 뽑아낸 숫자를 다시 저장한다.
  • count%N인 경우, 정답 배열에 숫자를 저장한다.

from collections import deque

n,k=map(int, input().split())
queue = deque()
for i in range(1,n+1): queue.append(i)
count = 1
result = []

while len(queue)>0:
    num = queue.popleft()
    if count%k==0:
        result.append(num)    
    else:
        queue.append(num)
    count+=1

print("<" + ", ".join(map(str, result)) + ">")

여기서 map은 Map 자료구조가 아닌 map 함수로, result라는 반복 가능한 객체(리스트 등)의 각 요소를 str 함수에 전달하여 변환한 결과를 반환한다. 

join 메서드는 문자열을 연결할 때 사용되므로, join과 map을 사용하여 result 의 int 요소들을 string으로 변환한 뒤, ","로 연결하는 결과를 낸다.

 

1406번. 에디터 (https://www.acmicpc.net/problem/1406)

커서를 기준으로 왼쪽 자료구조와 오른쪽 자료구조를 관리하며 문제를 풀 수 있다. L,D,B,P 명령어 모두 FILO 구조를 따르므로 스택 자료구조를 이용하도록 하자.

• 초기 입력되는 문자열을 커서_왼쪽 스택에 저장한다.
• 명령어를 반복한다.
  • 명령어가 L인 경우, 커서_왼쪽 스택에서 문자를 하나 꺼내 커서_오른쪽 스택에 저장한다. (단, 커서_왼쪽 스택이 비어있으면 무시한다.)
  • 명령어가 D인 경우, 커서_오른쪽 스택에서 문자를 하나 꺼내 커서_왼쪽 스택에 저장한다. (단, 커서_오른쪽 스택이 비어있으면 무시한다.)
  • 명령어가 B인 경우, 커서_왼쪽 스택에서 문자를 하나 꺼내 삭제한다. (단, 커서_왼쪽 스택이 비어있으면 무시한다.)
  • 명령어가 P인 경우,  커서_왼쪽 스택에 $를 저장한다.

inputStr = input()
m = int(input())
cursor_left = []
cursor_right = []

for char in inputStr:
    cursor_left.append(char)

for i in range(m):
    command = input()
    if command.startswith('L'):
        if len(cursor_left)==0: continue
        char = cursor_left.pop()
        cursor_right.append(char)

    if command.startswith('D'):
        if len(cursor_right)==0: continue
        char = cursor_right.pop()
        cursor_left.append(char)

    if command.startswith('B'):
        if len(cursor_left)==0: continue
        cursor_left.pop()

    if command.startswith('P'):
        command,char = map(str,command.split())
        cursor_left.append(char)

print(''.join(cursor_left)+''.join(cursor_right[::-1]))

2346번. 풍선 터뜨리기 (https://www.acmicpc.net/problem/2346)

자료구조의 왼쪽과 오른쪽에 모두 접근이 가능한 덱을 이용하여 문제를 풀 수 있다. 또한, 풍선이 가지고 있는 숫자 정보를 해시테이블에 저장하여 접근하도록 하자.

• Deque에 1번부터 N번까지 숫자를 저장한다.
• 해시테이블에 Key에는 풍선 번호를, Value에는 종이에 적힌 숫자를 저장한다.
• 해시테이블에 번호로 접근하면서, 숫자를 확인한다.
  • 숫자가 양수이면 해당 숫자만큼 popLeft(), append()를 반복한다.
  • 숫자가 음수이면 해당 숫자만큼 pop(), appendLeft()를 반복한다.
• Deque이 빌 때까지 위 과정을 반복한다.

from collections import deque

n = int(input())
queue = deque()
balloonNums = {}
count = 1
result = []

for i in range(1,n+1): queue.append(i)

for num in map(int,input().split()):
    balloonNums[count] = num
    count+=1

num = queue.popleft()
result.append(num)
paperNum = balloonNums.get(num)

while len(queue)>0:
    if paperNum>0:
        for i in range(paperNum-1):
            balloonNum = queue.popleft()
            queue.append(balloonNum)
        balloonNum = queue.popleft()
        result.append(balloonNum)
        paperNum = balloonNums.get(balloonNum)
    else:
        for i in range(-paperNum-1):
            balloonNum = queue.pop()
            queue.appendleft(balloonNum)
        balloonNum = queue.pop()
        result.append(balloonNum)
        paperNum = balloonNums.get(balloonNum)

print(' '.join(map(str,result)))

5397번. 키로거 (https://www.acmicpc.net/problem/5397)

이전 에디터 문제처럼, 커서_왼쪽 배열과 커서_오른쪽 배열로 관리하여 문제를 풀면 된다.

• 문자를 반복하여 행동한다.
  • 명령어인 경우(>,<,-)
    • > 인 경우 커서_오른쪽 스택에서 문자를 하나 꺼내 커서_왼쪽 스택에 저장한다. (단, 커서_오른쪽 스택이 비어있으면 무시한다.)
    • < 인 경우 커서_왼쪽 스택에서 문자를 하나 꺼내 커서_오른쪽 스택에 저장한다. (단, 커서_왼쪽 스택이 비어있으면 무시한다.)
    • - 인 경우 커서_왼쪽 스택에서 문자를 하나 꺼내 제거한다.
  • 입력 문자인 경우(대문자, 소문자, 숫자), 커서_왼쪽 스택에 문자를 저장한다.

T = int(input())

for i in range(T):
    cursor_left = []
    cursor_right = []

    inputStr = input()

    for char in inputStr:
        if char == '<':
            if len(cursor_left)==0: continue
            char = cursor_left.pop()
            cursor_right.append(char)

        elif char == '>':
            if len(cursor_right)==0: continue
            char = cursor_right.pop()
            cursor_left.append(char)

        elif char == '-':
            if len(cursor_left)==0: continue
            cursor_left.pop()

        else:
            cursor_left.append(char)

    print(''.join(cursor_left)+''.join(cursor_right[::-1]))

2493번. 탑 (https://www.acmicpc.net/problem/2493)

위와 같이, 해당 탑의 레이저를 수신한 탑의 인덱스를 출력하는 되는 문제이다. 단, N<100,000이고, 시간 제한은 1.5초이기 때문에, 이중 반복문으로는 시간 초과가 난다. 이를 스택을 이용해서 해결할 수 있다.

• nums 리스트에 전체 숫자를 저장한다.
• nums 리스트에서 숫자를 하나씩 뽑아 stack과 비교한다.
  • stack이 비어있거나, stack_peek 값이 더 큰 경우 : stack에 num을 push 한다.
  • stack_peek 값보다 num이 더 큰 경우 : stack 을 pop 한다.
    • stack이 빌 때까지 pop을 한 후, stack이 비거나  stack_peek 값이 더 크면 num을 push 한다.

처음에는 while stack이기 때문에 O(N^2)가 아닌가 생각을 했는데, 이 경우에는 최악의 경우가 합 N을 돈다.

이런 경우도 맨 마지막 숫자 10은 앞에서 2, 5만큼 돈 경우는 확인 안하기 때문에 최종 합이 N임을 알 수 있다. 

n = int(input())
nums = list(map(int,input().split(' ')))
indexAndNums = []
for i in range(n): 
    indexAndNums.append([i+1,nums[i]])
stack = []
result = [] 

for indexAndNum in indexAndNums:
    appendFlag = False
    index = indexAndNum[0]
    num = indexAndNum[1]
    while stack:
        peekNum = stack[-1][1]
        peekIndex = stack[-1][0]
        if peekNum < num: stack.pop()
        if peekNum >= num: 
            result.append(peekIndex)
            appendFlag = True
            break
    stack.append(indexAndNum)
    if appendFlag == False : result.append(0)

print(" ".join(map(str,result)))