02. 기본 자료구조 - 핵심 유형 문제풀이 - 스택, 큐

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

1874번: 스택 수열

• 스택, 그리디

 

 

1. 입력 4일 때 ++++ >>1234
2. 4 읽기 -  >> 123
3. 입력 3일 때 3 읽기 - >>12
4. 입력 6일 때  34 는 없으므로 ++ >>1256
5. 6읽기 - >> 125
6. 입력 8일 때 ++ >>12578
7. 8읽기 - >>1257
8. 7읽기 - >> 125
9. 5읽기 - >> 12
10. 2읽기 - >>1
11. 1읽기 - >> empty

출력 결과 = ++++--++-++-----

• 한번에 두개씩 못 뺌

n = int(input())
count = 1
stack = []; result = []

for i in range(1, n+1): # 데이터 개수만큼 반복

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

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

1966번: 프린터 큐

for _ in range(int((input()))):
    n, m = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    queue = [(i, idx) for idx, i in enumerate(arr)]


# n, m  = 4, 2 
# arr = [1,2,3,4]

# n, m  = 6, 0 
# arr = [1,1,9,1,1,1]

# queue = [(i, idx) for idx, i in enumerate(arr)] # [(1, 0), (2, 1), (3, 2), (4, 3)] 인덱스 맵핑
# temp = max(queue, key=lambda x:x[0])[0] # (4, 3) -> 4
# print(queue, temp)
    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x:x[0])[0]: # 제일 높은 중요도 값
            count += 1 
            if queue[0][1] == m:
                print(count)
                break
            else:
                queue.pop(0)
        else:
            queue.append(queue.pop(0))

• 큐, 구현, 그리디
• 문제의 핵심은 중요도가 높은 순서데로(ex)4, 3, 2, 1) 몇 바퀴를 돌렸을 때 그 값을 카운팅 함
  • 입력 받은 배열을 그대로 큐로 인덱스와 함꼐 튜플 형태로 맵핑시킴 "queue = [(i, idx) for idx, i in enumerate(arr)]" 
  • 맵핑된 결과 "[queue[0][0]]" 는 중요도, "queue[0][1]" 은 인덱스 맵핑 당시 책 위치임
  • 현재 배열" queue"에서 가장 높은 중요도를 찾음  "max(queue, key=lambda x:x[0])[0]" 
    • 조건문을 통해 위 값과 배열의 매 첫번 째 값과 비교하여 값이 일치할 때까지 회전을 시키며 "count +=1"
    • 일치 한다면 "if queue[0][1] == m" (처음 입력받은 m 값의 자리를 비교)
      • 현재까지 카운트된 값을 출력하고 반복문 종료
      • 일치 하지만 위치가 맞지 않다면, 그 값은 제거
    • 그렇지 않다면 회전을 시킴
      • 회전 방법"queue.append(queue.pop(0))"

 

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

5397번: 키로거

 

단순히 구현만해서는 못품

 

• 스택, 구현, 그리디
• 2개의 스택을 통해 구현하는 문제
• "<"  커서 왼쪽이동, ">" 커서 오른쪽 이동 "-" 앞에 문자열 있을경우 제거
• 기억하기 좋은 라이브러리는 두 개 
  • "extend(reversed(right_stack))" 리스트간 합칠 때 사용. reversed도 사용 가능.
  • "        print(' '.join(left_stack))               " 리스트 내 쉼표 제거 시 사용.

test = int(input())

for _ in range(test):
    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)) # append()가 아닌 extend()를 통해 확장해서 뒤집어 넣어줌
    print("".join(left_stack)) #개별 리스트 쉼표 제거 후 출력