스택
파이썬은 스택이라는 라이브러리는 판다스에 존재한다. 문제는 판다스를 쓰기에는 너무 귀이이이이 찬타
대신에 리스트가 존재하여 이걸로 사용하는게 편리하다.
- 선언
stack = []
-추가 및 삭제
stack.append(4)
stack.pop() #데이터 삭제 및 반환
- 조회
stack[-1]
- 기타
len(stack)==0 #데이터 없음
if(stack) #데이터 존재하는지 확인
len(stack) #데이터 갯수 확인
stack.clear(): 스택 비우기#include <stack>
- 선언
stack<T> st;
- 추가 및 삭제
push(element): top에 원소를 추가
pop(): top에 있는 원소를 삭제
- 조회
top(): top(스택의 처음이 아닌 가장 끝)에 있는 원소를 반환
- 기타
empty(): 스택이 비어있으면 true 아니면 false를 반환
size(): 스택 사이즈를 반환문제
9093 단어 뒤집기
python
한 줄 그대로 읽기
s=sys.stdin.readline()
리스트에서 문자열로 특정문자를 중간중간 삽입하기
print(':'.join(stack[::-1])import sys
sys.stdin = open("input.txt","r")
t = int(input())
for _ in range(t):
s = sys.stdin.readline()
stack=[]
for ch in s:
if(ch == ' ' or ch=='\n'):
print(''.join(stack[::-1]),end='')
stack.clear()
print(ch,end='')
else:
stack.append(ch)문자열 관련 문제를 다룰때는 한 문자씩 다루기 보다는 String으로 한번에 읽어 들여서 처리하는 것이 훨씬 편리하다.
읽어들일 때 getline 함수 사용하기
getline 함수는 string.h 와 string 라이브러리 두개에 각각들어가 있는데
cstring(string.h)에 들어가 있는 getline 함수는 char 형식의 문자열을 처리하는데 사용됨 그래서 사용시 getline(char s, streamsize n, char delim)의 제한을 가지고 delime은 이 문자에 도달시 추출이 중단된다는 의미임.
사용할 때는
#include <iostream>
char greeting[100];
cin.getline(greeting,10);위의 형식으로 사용됨
반면에 string 클래스에 있는 getline은 getline(ifstream& is, string& str, char delim)임
사용할 때는
#include <string>
string greeting;
getline(cin,greeting);위의 형식으로 사용됨
string 반복문 돌릴때 다음과 같이 문자를 하나씩 반복하면서 찾아낼 수도 있음
for(char ch:str){
}#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;
int main(void) {
freopen("input.txt", "r", stdin);
int t;
scanf("%d\n", &t);
stack<char> st;
while (t--) {
string d;
getline(cin, d);
d += '\n';
for (char ch : d) {
if (ch == ' ' || ch == '\n') {
while (!st.empty()) {
printf("%c", st.top());
st.pop();
}
printf("%c", ch);
}
else {
st.push(ch);
}
}
}
}9012 괄호
import sys
sys.stdin = open("input.txt","r")
t = int(input())
for i in range(t):
d=0
s = input()
flag = True
for j in range(len(s)):
if(s[j]=='('): d=d+1
elif(s[j]==')'): d=d-1
if(d<0):
print("NO")
flag = False
break
if(d==0 and flag): print("YES")
elif(flag): print("NO")1874 스택 수열
우리가 push와 pop을 번갈아서 숫자를 삽입하는 것으로 보이는데 어떻게 해야 우리가 원하는 수열대로 숫자를 push, pop 할 수 있을지를 찾아내는 문제이다.
파이썬에서 문자열을 특정 문자를 기준으로 나누고 싶을 때는 "\n".join(ans)를 사용하면 된다.
exit(0) : 문제없는 탈출
exit(1) : 문제 있는 종료
import sys
sys.stdin = open("input.txt","r")
t = int(input())
a = [int(input()) for _ in range(t)]
st=[]
ans=""
m=0
for x in a:
if(x>m):
while(x>m):
m=m+1
st.append(m)
ans+="+"
st.pop()
ans+="-"
else:
if st[-1]!=x:
print("NO")
sys.exit(0)
st.pop()
ans+="-"
print("\n".join(ans),end="\n")1406 에디터
문제가 별거는 없는데 그냥 리스트를 역으로 만들때는 reverse() 함수를 사용해서
rst.reverse() 해 놓거나 아니면 리스트 참조방식인 rst[::-1]을 사용해서 lst에 데이터를 모두 붙여놓기
또한 추가적으로 데이터 양끝에 "\n" 이 붙어 있는 경우가 존재하기 때문에 input().strip() 함수를 사용해주는 것이 좋다.
데이터 입력시
list(input().strip()) 하고 [input().strip()]은 다른 표현이다.
list(input().strip())은 문자별로 각각 나누어서 list로 들어가는 반면
[input().strip()]은 통 문자열이 리스트를 구성한다.
또한 입력시 속도를 빠르게 하기 위해서 sys.stdin을 사용하는 것이 좋다.
sys.stdin.readline
sys.stdin
보통 아래와 같이 사용한다.
input = sys.stdin.readline
lst = list(input().strip())
import sys
sys.stdin = open("input.txt","r")
input = sys.stdin.readline
lst = list(input().strip())
rst = []
t = int(input())
for _ in range(t):
d = input().strip().split()
if(d[0] == "L"):
if(lst):
rst.append(lst.pop())
elif(d[0] == "D"):
if(rst):
lst.append(rst.pop())
elif(d[0]=="B"):
if(lst):
lst.pop()
elif(d[0]=="P"):
lst.append(d[1])
lst+=rst[::-1]
print("".join(lst))큐
파이썬에서 큐라는 라이브러리가 존재하지 않는다... 대신에 리스트를 사용해서 유사한 기능을 제작할 수 있다.
하지만 가급적 큐보다는 덱을 사용하자. 리스트의 연산속도가 그렇게 빠르지 않기에 from Collections import deque로 가져온 라이브러리의 속도가 보다 빠른편이다.
- 선언
queue = []
-추가 및 삭제
queue.append(4)
queue.pop(0) #데이터 삭제 및 반환
- 조회
queue[0]
- 기타
len(queue)==0 #데이터 없음
if(queue) #데이터 존재하는지 확인 -> 이게 조금 더 좋음
len(queue) #데이터 갯수 확인
queue.clear(): 큐 비우기문제
10845 큐
stdin 은 standard input을 뜻하며 얼핏 보면 input() 과 같은 동작을 수행한다고 생각할 수 있다.
sys.stdin.readline()은 사용자의 입력을 받지만 개행 문자도 입력을 받을 수 있다. 또한 입력 크기에 제한을 줌으로써 한번에 읽어들일 문자의 수를 정할 수 있다.
이걸 input=sys.stdin.readline으로 작성하는 것으로 input 대신 sys.stdin.readline을 사용할 수 있지만 개행문자까지 받아오기 때문에 .strip(양끝 개행 문자 제거)이나 .rstrip(오른쪽 개행 문자 제거)를 함께 사용하는 것이 좋다.
삼항연산자를 사용했다.
True if x else Falseimport sys
sys.stdin = open("input.txt","r")
input = sys.stdin.readline
t = int(input())
queue = []
for _ in range(t):
s = input().strip().split(" ")
if(s[0] == "push"): queue.append(s[1])
elif(s[0]=="pop"):
if(queue): print(queue.pop(0))
else: print("-1")
elif(s[0]=="size"): print(len(queue))
elif(s[0]=="empty"): print("0") if queue else print("1")
elif(s[0]=="front"): print(queue[0]) if queue else print("-1")
elif(s[0]=="back"): print(queue[-1]) if queue else print("-1")1158 요세푸스 문제
요세푸스 문제를 그냥 리스트로 풀면 시간제한을 크게 받는다...
그래서 이번에는 파이썬 라이브러리인 디큐를 사용하는 것이 오히려 낫다.
사실 파이썬에서 큐를 사용한다면 가급적 덱을 쓰는 것이 효율적이다.
import sys
sys.stdin = open("input.txt","r")
from collections import deque
input = sys.stdin.readline
t,m = map(int,input().rstrip().split())
q = deque()
for i in range(1,t+1):
q.append(i)
ans=[]
for i in range(t-1):
for j in range(m-1):
q.append(q.popleft())
ans+=[q.popleft()]
ans+=[q[0]]
print('<'+', '.join(map(str,ans))+'>')덱
우선 덱은 양방향 연결리스트로 구성되어 있으며 파이썬 라이브러리를 사용하게 된다.
- 선언
from collections import deque
dq = deque()
-추가 및 삭제
dq.append(4) #오른쪽에 데이터 삽입
dq.appendleft(4) #왼쪽에 데이터 삽입
dq.pop() #오른쪽 데이터 삭제 및 반환
dq.leftpop() #왼쪽 데이터 삭제 및 반환
- 조회
queue[0]
- 기타
len(dq)==0 #데이터 없음
if(dq) #데이터 존재하는지 확인 -> 이게 조금 더 좋음
len(dq) #데이터 갯수 확인
dq.clear(): 큐 비우기문제
10866 덱
import sys
sys.stdin = open("input.txt","r")
from collections import deque
input = sys.stdin.readline
t = int(input().rstrip())
dq = deque()
for _ in range(t):
s = input().rstrip().split()
if(s[0]=="push_front"): dq.appendleft(s[1])
elif(s[0]=="push_back"): dq.append(s[1])
elif(s[0]=="pop_front"):
if(dq):
print(dq.popleft())
else:
print("-1")
elif(s[0]=="pop_back"):
if(dq):
print(dq.pop())
else:
print("-1")
elif(s[0]=="size"): print(len(dq))
elif(s[0]=="empty"): print(0 if dq else 1)
elif(s[0]=="front"):
if(dq):
print(dq[0])
else:
print("-1")
elif(s[0]=="back"):
if(dq):
print(dq[-1])
else:
print("-1")17413 단어뒤집기 2
