[알고리즘 기초] - 200-자료구조1

10828_스택

⭕풀이:

import sys

input = sys.stdin.readline

n = int(input())
stack = []  #아래함수를 통해 출려된 값들을 stack이라는 리스트에 차례대로 쌓기 위해 비어 있는 리스트 stack을 작성해 둔다.

for i in range(n):  
    word = input().split()  #명령하고 싶은 함수와 명령받을 값을 띄워서 작성한다.
    order = word[0]  #명령어는 주어진 입력값 중 첫 번째 요소값이 명령어가 되게 order를 명령어로 변수선언한다.
    if order == 'push':  #명령어가 push일 경우,
        stack.append(int(word[1]))  #주어진 입력값 중 2 번째 값을 정수로 변환시켜 stack 리스트에 넣는다.
    elif order == 'top':  #명령어가 top일 경우,
        if len(stack) > 0:  #stack의 길이가 0보다 클 경우,(=stack 적어도 1개 이상의 요소갑이 있을 경우,)
            print(stack[-1])  #stack의 가장 끝에 있는 값을 출력한다. stack의 개념특성상 주어진 순서로대로 숫자가 하나씩 쌓이기 때문에 문제에서 가장 위에 있는 값은 가장 마지막에 리스트에 들어온 값과 같기 때문에 가능하다.
        else:  #그렇지 않고, stack 리스트에 요소값이 존재하지 않을 경우,
            print(-1)  #-1을 출력해라.
    elif order == 'pop':  #명령어가 pop일 경우,
        if len(stack) > 0:  #stack의 길이가 0보다 클 경우,(=stack 적어도 1개 이상의 요소갑이 있을 경우,)
            print(stack.pop())  #stack의 마지막 요소값을 stack 리스트에서 제거하고, 이를 출력한다.
        else:  #그렇지 않고, stack 리스트에 요소값이 존재하지 않을 경우,
            print(-1)  #-1을 출력해라.
    elif order == 'size':  #명령어가 size일 경우,
        print(len(stack))  #stack의 길이를 출력해라.
    elif order == 'empty':  #명령어가 empty일 경우,
        if len(stack) > 0:  #stack의 길이가 0보다 클 경우,(=stack 적어도 1개 이상의 요소갑이 있을 경우,)  
            print(0)  #0을 출력해라.
        else:  #그렇지 않고, stack 리스트에 요소값이 존재하지 않을 경우,
            print(1)  #-1을 출력해라.

📌필요지식

1) 자료구조

• 자료구조는 데이터를 표현하고 관리하고 처리하기 위한 구조를 말합니다.

2) 스택(Stack)

• 스택은 입구와 출구가 동일한 형태로 후입선출구조를 가집니다. 나중에 들어온 값이 먼저 나가는 구조입니다.

3) pop(): 리스트 요소 끄집어내기

• pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제합니다.
  
• pop(x)는 리스트의 x번 째 요소를 돌려주고 그 요소는 삭제합니다.
  

---

9093_단어 뒤집기

⭕풀이:

test_case = int(input())

for _ in range(test_case):  
    words = list(input().split())
    reversed_sentence = []
    for word in words:
        reversed_word = word[::-1]  #[::-1]을 통해 words 리스트에 있는 요소값 하나하나들(word)의 문자열의 순서를 뒤집을 수 있다.
        reversed_sentence.append(reversed_word)  #문자열의 순서를 뒤집은 요소값들을 비어 있는 reversed_list에 넣는다.
    answer = " ".join(reversed_sentence)  #요소값이 reversed_list에 ['요소값', '요소값', '요소값', '요소값',..]형태로 들어가 있기 때문에 이들을 하나의 문자열로 이어 문장으로 만들어 주기 위해 " ".join을 이용해 문자열 사이에 공백을 넣어 [요소값 요소값 요소값..요소값]형태로 만들어 준다.
    print(answer)

📌필요지식

1) slice로 문자열 뒤집기

• slice를 이용하면 매우 쉽게 문자열을 뒤집을 수 있습니다. slice에서 각각의 항목은 [start:stop:step]을 의미합니다. 문자열[::-1]처럼 반대 방향으로 리스트의 데이터를 자를 수 있습니다.
  

---

9012_괄호

⭕풀이:

test_case = int(input())

for _ in range(test_case):
    bracket = input()  #괄호 문자열 
    bracket_list = list(bracket)  #괄호 문자열을 bracket_list에 넣어 (()()())를 ['(', '(', ')', '(', ')', '(', ')', ')']의 형태로 만들어 리스트에 요소값(괄호 문자) 하나하나를 for문으로 반복한다.
    cnt = 0
    for i in bracket:
        if i == '(':  #문자열이 '('이면 
            cnt += 1  #cnt에 1을 더하고 
        elif i == ')':  #문자열이 ')'이면 
            cnt -= 1  #cnt에 1을 뺀다.
        if cnt < 0:  #위 과정을 통해 cnt가 0보다 작아질 경우,(='(' 보다 ')'이 많아질 경우,)
            print('NO')  #올바른 문자열이 되지 못하므로, 'NO'를 출력하고,
            break  #해당 괄호 문자열의 반복문을 종료한다.
    if cnt > 0:  #위 과정(for문)을 통해 cnt의 값이 1보다 크면,(= '(' 보다 ')'이 적을 경우,)
        print('NO')  #올바른 문자열이 되지 못하므로, 'NO'를 출력하고,
    elif cnt == 0:  #그렇지 않고, cnt가 0이면,(= '('와 ')'의 갯수가 동일하므로,)
        print('YES')  #올바른 문자열이므로, 'YES'를 출력한다.

---

1874_스택 수열

⭕풀이:

test_case = int(input())
stack = []
answer = []
flag = 0
cur = 1

for i in range(test_case):
    num = int(input())
    while cur <= num:
        stack.append(cur)
        answer.append("+")
        cur += 1
    if stack[-1] == num:
        stack.pop()
        answer.append("-")
    else:
        print("NO")
        flag = 1
        break
if flag == 0:
    for i in answer:
        print(i)

---

1406_에디터

⭕풀이:

import sys

st1 = list(input())  
n = int(input())

for i in range(n):
    order = sys.stdin.readline().split()
    if order[0] == 'L' and st1:  #order 중 명령어가 L이고, 입력된 값(st1)에 요소값이 있다면,
        st2.append(st1.pop())  #st1을 pop한 값을 st2에 마지막 값 뒤에 붙인다.    
    elif order[0] == 'D' and st2:
        st1.append(st2.pop())
    elif order[0] == 'B' and st1:
        st1.pop()
    elif order[0] == 'P':
        st1.append(order[1])

print(''.join(st1 + list(reversed(st2))))

⭕풀이설명:

1) append와 pop 활용

• 리스트의 마지막 요소값 뒤에 요소값을 추가하는 append와
  리스트의 마지막 요소값을 떼어 내는 pop를 활용해

• 주어진 문자열을 커서를 기준으로 문자열을 스택 두개 st1, st2에 나누어 담았습니다.

• list(문자열) = st1 + st2로 작성해
  커서를 왼쪽으로 움직이면, st1를 pop해 st2로 옮기고,
  커서를 오른쪽으로 움직이면, st2를 pop해 st1로 옮기는 것과 같습니다.
  

2) 입력값: abcde

입력값: abcde
L -> st1 = ['a', 'b', 'c', 'd'], st2 = ['e']  ->  ['a', 'b', 'c', 'd'] | ['e']
L -> st1 = ['a', 'b', 'c'],      st2 = ['e', 'd']  ->  ['a', 'b', 'c'] | ['e', 'd']
D -> st1 = ['a', 'b', 'c', 'd'], st2 = ['e']  ->  ['a', 'b', 'c', 'd'] | ['e']

3) 입력값: abc

입력값:
abc
9
L
L
L
L
L
P x
L
B
P y

시작 값
stack_l = [a, b, c]
stack_r = []

L 입력
stack_l = [a, b]
stack_r = [c]

L 입력
stack_l = [a]
stack_r = [c, b]

L 입력
stack_l = []
stack_r = [c, b, a]

L 입력
stack_l의 값이 없어서 조건 불충족

L 입력
stack_l의 값이 없어서 조건 불충족

P x 입력
stack_l = [x]
stack_r = [c, b, a]

L 입력
stack_l = []
stack_r = [c, b, a, x]

B 입력
stack_l의 값이 없어서 조건 불충족

P y 입력
stack_l = [y]
stack_r = [c, b, a, x]

출력 (stack_l + list(reversed(stack_r)))
[y, x, a, b, c]

https://seongonion.tistory.com/53
https://velog.io/@tkdduf727/%EB%B0%B1%EC%A4%80-%EA%B4%84%ED%98%B8-1406%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

---

10845_큐

⭕풀이:

from sys import stdin

N = int(stdin.readline())
Que = []

for i in range(N):
    A = stdin.readline().split()
    order = A[0]

    if order == 'push':
        Que.append(A[1])
    elif order == 'pop':
        if Que:
            print(Que.pop(0))
        else:
            print(-1)
    elif order == 'size':
        print(len(Que))
    elif A[0] == 'empty':
        if len(Que) == 0:
            print(1)
        else:
            print(0)
    elif order == 'front':
        if len(Que) == 0:
            print(-1)
        else:
            print(Que[0])
    elif order == 'back':
        if len(Que) == 0:
            print(-1)
        else:
            print(Que[-1])

📌필요지식

1) 큐(Queue)

• 선입선출의 형태로 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 자료구조이지만 한쪽 끝에서는 삽입, 반대쪽 끝에서는 삭제가 이루어지는 자료구조입니다.

2) 큐(Queue) 특징

• 한쪽 끝을 front로 정해 삭제 연산만 수행하도록하고 다른 쪽 끝은 rear로 정해 삽입 연산만 수행하도록 제한해 만든 자료구조입니다.
  front 원소는 가장 먼저 큐에 들어온 첫 번째 원소이고, 리어 원소는 가장 늦게 들어온 마지막 원소입니다.
  

https://leejinseop.tistory.com/36

---

1158_요세푸스 문제

⭕풀이:

N, K = map(int, input().split())
N_list = [i for i in range(1, N+1)]
answer = []
num = 0

for _ in range(N):
    num += K-1  #num을 다음과 같이 변수선언한 이유는 첫 번째 반복에서 N_list의 num번째를 pop을 하면 pop을 한 자리를 기준으로 K번째 사람이 pop이 이루어져야 하기 때문에 계속해서 num에 k-1을 더해주어야 한다.
    if num >= len(N_list):  #for문 반복을 통해 num의 값이 N_list의 길이보다 커지거나 같을 경우,(=한바퀴를 돌고 그다음으로 돌아올때를 대비해 값을 나머지로 바꿈)
        num = num % len(N_list)  #num은 num을 N_list의 길이로 나눈 나머지 값으로 변경되야 한다.

    answer.append(str(N_list.pop(num)))
print("<", ", ".join(answer)[:], ">", sep='')

⭕풀이설명:

1) 제거될 때마다 원을 다시 그려봅니다.

• K번째 사람이 계속해서 제거되고, 나간 사람 기준으로 원을 따라 다시 배열됩니다.
• K번째 사람이 계속해서 나가는 제거하는 것이기 때문에 N_list의 배열을 제거한 문자열(=pop을 한 사람) 기준으로 다시 배열하면 다음과 같습니다.

1 2 3 4 5 6 7

pop: 3
남은 큐: 4 5 6 7 1 2

pop: 3, 6
남은 큐: 7 1 2 4 5

pop: 3, 6, 2
남은 큐: 4 5 7 1

pop: 3, 6, 2, 7
남은 큐: 1 4 5

pop: 3, 6, 2, 7, 5
남은 큐: 1 4

https://infinitt.tistory.com/213

---

10866_덱

⭕풀이:

import sys

input = sys.stdin.readline

n = int(input())
Deque = []

for i in range(n):
    word = input().split()
    order = word[0]
    if order == 'push_front':
        Deque.insert(0, int(word[1]))
    elif order == 'push_back':
        Deque.append(int(word[1]))
    elif order == 'pop_front':
        if len(Deque) > 0:
            print(Deque.pop(0))
        else:
            print(-1)
    elif order == 'pop_back':
        if len(Deque) > 0:
            print(Deque.pop())
        else:
            print(-1)
    elif order == 'size':
        print(len(Deque))
    elif order == 'empty':
        if len(Deque) > 0:
            print(0)
        else:
            print(1)
    elif order == 'front':
        if len(Deque) > 0:
            print(Deque[0])
        else:
            print(-1)
    elif order == 'back':
        if len(Deque) > 0:
            print(Deque[-1])
        else:
            print(-1)

---