[파알문] 5. 자료구조 활용

Nam_JU·2023년 8월 8일
0

Algorithm

목록 보기
18/20

2023.08.08


5-1. 가장큰수 - 스택

파이썬 숫자문자열 숫자 리스트 변환

"""
n = 5276823
"""
n = input() '5276823'
n = int(input()) 5276823
#숫자 문자열을 숫자 리스트로 변환
n = list(map(int, str(n))) # [5, 2, 7, 6, 8, 2, 3]
  • 정답코드
"""
5276823 3
"""
n, m = map(str, input().split())
#숫자 문자열을 숫자 리스트로 변환
n = list(map(int, n))
stack = []

for x in n:
    while stack and m>0 and stack[-1]<x:
        stack.pop()
        m-=1
    stack.append(x)
if m!=0:
    stack=stack[:-m]
print(stack)


23.08.12


5-2. 쇠막대기


5-3. 후위표기식

연산자를 스택에 넣어서 활용

  • 정답
"""
3+5*2/(7-2)
"""
s = input()
stack = []
answer = ""
for x in s:
    if x.isdigit():
        answer+=x
    else:
        if x=='(':
            stack.append(x)
        elif x=="*" or x=="/":
            while stack and (stack[-1]=='*' or stack[-1]=='/'): #스택을 돌면서 연산자 우선순위 확인
                answer +=stack.pop()
            stack.append(x)
        elif x=='+' or x=='-':
            while stack and stack[-1]!='(': #순위가 가장 밑이기 때문에 다 출력 but (여는 괄호 전까지
                answer+=stack.pop()
            stack.append(x)
        elif x==')':
            while stack and stack[-1]!='(':
                answer+=stack.pop()
            stack.pop()
while stack:
    answer+=stack.pop()

print(answer)

5-4. 후위 연산

  • 정답
"""
352+*9-
"""

import sys
input = sys.stdin.readline

a = input()
stack = []
for x in a:
    if x.isdecimal():
        stack.append(int(x))
    else:
        if x=='+':
            n1=stack.pop()
            n2=stack.pop()
            stack.append(n2+n1)
        elif x=='-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 - n1)
        elif x=='*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 * n1)
        elif x=='/':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 / n1)
print(stack[0])

📍 파이썬 입력 속도 줄이기

input()을 사용할 경우 속도 제한에서 걸릴 수 있다.

import sys
input = sys.stdin.readline

위의 readline을 설정후 input()은 평소대로 사용하도록 하자


5-5. 공주구하기(큐)

  • 내코드
"""
8 3
"""
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
# prince = [n for n in range(1, n+1)]
prince = list(range(1, n+1))
prince=deque(prince)

while prince:
    for i in range(2):
        prince.append(prince.popleft())
    prince.popleft()
    if len(prince)==1:
        break
        
print(' '.join( map(str, list(prince))))
 

📍 파이썬 숫자 리스트 만들기

리스트 [1,2,3,4,5,6,7,8,9] 까지의 초기화된 리스트를 구현

version1 = [n for n in range(1, n+1)]
version2 = list(range(1, n+1))

5-6. 응급실(큐)

  • 정답코드
"""
5 2
60 50 70 80 90
"""
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
patient = [(idx, value) for idx, value in enumerate(list(map(int, input().split())))]
patient = deque(patient)
cnt=0
while True:
    cur = patient.popleft()
    if any(cur[1]<x[1] for x in patient):
        patient.append(cur)
    else:
        cnt+=1
        if cur[0]==m:
            print(cnt)
            break

📍 파이썬 튜플생성하며 입력받기

입력받은 값에 idx를 매겨 튜플 형태로 저장하는 방법

  • 방법1
patient = list(map(int, input().split()))
dict = []
for i, value in enumerate(patient, start=1):
    dict.append((i, value))
print(dict) # [(1, 60), (2, 50), (3, 70), (4, 80), (5, 90)]
  • 방법2
patient = [(idx, value) for idx, value in enumerate(list(map(int, input().split())))]
print(patient) # [(0, 60), (1, 50), (2, 70), (3, 80), (4, 90)]


23.08.13


5-7. 교육과정 설계(큐)

  • 인덱스 out of range 에러
"""
CBA
3
CBDAGE
FGCDAB
CTSBDEA
"""

from collections import deque
s = input()
n = int(input())

q = deque(s)
for i in range(n):
    subject = input()
    for c in subject:
        if c==q[0]:
            q.popleft()
    if len(q)==0:
        print("#%d YES", i+1)
    else:
        print("#%d NO", i+1)
  • 정답
from collections import deque
s = input()
n = int(input())
for i in range(n):
    plan = input()
    dq = deque(s)
    for x in plan:
        if x in dq: #x가 dq에 있는지 확인 여부 
            if x!=dq.popleft(): #가장 왼쪽 꺼내서 확인
                print("#%d NO" %(i+1))
                break
    else:
        if len(dq)==0:
            print("#%d YES" %(i+1))
        else:
            print("#d NO" %(i+1))

5-8. 단어찾기

  • 내코드

"""
5
big
good
sky
blue
mouse
sky
good
mouse
big
"""
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
word = [input() for _ in range(n)]
# word = deque(word)
poem = [input() for _ in range(n-1)]

for c in poem:
    if c in word:
        word.pop(word.index(c))

print(''.join(word))

📍 파이썬 딕셔너리 - items()

리스트의 경우 인덱스를 숫자밖에 사용하지 못한다.
하지만 파이썬 딕셔너리의 경우 키값을 문자로도 사용 가능하다. 즉, key,value 값을 마음대로 설정하여 사용가능.

딕셔너리의 키, 값 쌍 얻기 - items()

딕셔너리(dictionary)는 items()함수를 사용하면 딕셔너리에 있는 키와 값들의 쌍을 얻을 수 있다.

  • 정답
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
p = dict()

# 입력받은 단어들을 key값으로 사용하고 value값은 1로 지정 {'big\n': 1, 'good\n': 1, 'sky\n': 1, 'blue\n': 1, 'mouse\n': 1}
for i in range(n):
    word=input()
    p[word]=1

for i in range(n-1):
    word=input()
    p[word]=0
for key, value in p.items(): #key, values값들을 접근
    if value == 1:
        print(key)
        break

5-9. 아나그램

  • 구현에러
word1 = input()
word2 = input()
save = dict()

for c in word1:
    if c in save:
        save[c]+=1 #???
    save[c]=1

print(save)
  • 정답코드
"""
AbaAeCe
baeeACA
"""
a = input()
b = input()
word1 = dict()
word2 = dict()

for c in a:
    word1[c]=word1.get(c,0)+1
for c in b:
    word2[c]=word2.get(c,0)+1

for i in word1.keys():
    if i in word2.keys():
        if word1[i]!=word2[i]: #value값 비교로 확인
            print("NO")
            break
    else:
        print("NO")
        break
else:
    print("YES")
  • 개선코드
a = input()
b = input()
find=dict()
for c in a:
    find[c]=find.get(c,0)+1
for c in b:
    find[c]=find.get(c,0)-1

for c in a:
    if find.get(c)>0:
        print("NO")
        break
else:
    print("YES")

📍 파이썬 딕셔너리 - str.get(x,0)+1

a = input()
b = input()
word1 = dict()
word2 = dict()
for c in a:
    word1[c]=word1.get(c,0)+1 
    # word1[c] 키값 c가 있는지 
    # c 라는 값이 없으면 0, 있으면 +=1 저장 
print(word1) #{'A': 2, 'b': 1, 'a': 1, 'e': 2, 'C': 1}
profile
개발기록

0개의 댓글