스택(Stack) 구현하기
파이썬에서 제공하는 기본 함수를 최소한으로 쓰면서 구현해봤다.
class Stack:
items = []
top = -1
def __init__(self, size): # createStack
self.size = size
self.items = [False for s in range(size)]
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.size - 1
def push(self, item):
if self.is_full():
print("Stack is full.")
else:
self.top += 1
self.items[self.top] = item
def pop(self):
if self.is_empty():
print("Stack is empty.")
else:
self.items[self.top] = False
self.top -= 1
def peek(self):
if self.is_empty():
print("Stack is empty.")
else:
return self.items[self.top]
def display(self):
print(self.items)
my_stack = Stack(3)
my_stack.display()
my_stack.pop() # stack is empty 출력
my_stack.push(8)
my_stack.push(2)
my_stack.display()
my_stack.push(7)
my_stack.display()
my_stack.push(6) # stack is full 출력
print(my_stack.peek())백준 문제풀이
[9012] 괄호
T = int(input())
def isVps(text):
vpsStack = []
for t in text:
if t == "(":
vpsStack.append(t)
else: # t가 ) 일 때
if not vpsStack: # 스택에 아무것도 안 들어있고, 시작은 ) 로 하면 바로 NO
return "NO"
else:
vpsStack.pop()
return "NO" if vpsStack else "YES"
for tc in range(T):
print(isVps(input()))[3986] 좋은 단어
n = int(input())
def good_word(text):
stack = []
for t in text:
if (len(stack) == 0) or (stack[-1] != t):
stack.append(t)
else: # t와 stack의 마지막 값이 같다면 짝이 맞는 걸로 판단하면 스택에서 제거
stack.pop()
return (0 if stack else 1)
count = 0
for i in range(n):
word = input()
count += good_word(word)
print(count)[14888] 연산자 끼워넣기
이 문제는 위의 두 문제에 비해 어렵게 풀었다.
단순히 스택을 쓰면 되지 않을까 생각하고, 스택 리스트를 만들면서 접근했다가 뭔가 아닌 것 같았다.
구글링으로 다른 분들 코드를 보고, 복기하면서 혼자서 짜봤는데, 그러면서도 중간중간 에러가 났다 ㅠ
겨우 통과한 코드는 아래와 같다.
n = int(input()) # 수의 개수 n
numbers = list(map(int, input().split())) # 계산할 숫자 리스트
operators = list(map(int, input().split())) # +, -, *, // 의 개수
result = [-1000000000, 1000000000] # 계산 결과 저장
def cal(answer=numbers[0], idx=1):
if idx == n: # idx 가 숫자 개수만큼 되면 최종 계산 결과 저장하고, 함수 종료
result[0] = max(answer, result[0])
result[1] = min(answer, result[1])
return
for i in range(4):
if operators[i] > 0:
operators[i] -= 1
if i == 0: # 덧셈
cal(answer + numbers[idx], idx + 1)
elif i == 1: # 뺄셈
cal(answer - numbers[idx], idx + 1)
elif i == 2: # 곱셈
cal(answer * numbers[idx], idx + 1)
elif i == 3: # 나눗셈 (answer가 음수일 때 변환해서 정수로 계산이 안되어 변환 필요)
cal(int(answer / numbers[idx]), idx + 1)
operators[i] += 1
cal()
print(result[0])
print(result[1])마지막에 "음수를 나눌 때" 정수로 나눗셈이 안되고, 부동 소수점 값을 반환한다고 해서, 이 케이스는 따로 정수형으로 변환하는 작업을 했다.
(아니면 잘못된 결과가 나온다)
예시로 아래와 같이 연산을 해보면 알 수 있다.
a = -3
b = 6
print(a/b) # 음수 / 양수 = -0.5 (실수)
print(int(a/b)) # 음수 / 양수 를 정수로 변환 = 0
print(a//b) # 음수 // 양수 = -1
print(b/a) # 양수 / 음수 = -2.0
print(b//a) # 양수 // 음수 = -2
print(a/(-b)) # 음수 / 음수 = 0.5
print(a//(-b)) # 음수 // 음수 = 0[10799] 쇠막대기
이 문제는 손으로 막대기를 직접 그려가면서 풀었는데, 생각보다 재밌었다.
문제도 어렵지 않았음!
parentheses = input()
parentheses = parentheses.replace("()", "0") # 레이저는 0으로 변경
stack = []
total_sticks = 0
for p in parentheses:
if p == "0": # 레이저라면 현재까지 스택에 쌓인 스틱 개수만큼 더함
total_sticks += len(stack)
elif p == "(": # 쇠막대가 시작하면 스택에 막대를 담는다.
stack.append(1)
elif p == ")": # 쇠막대가 끝나면 끝난 막대 하나를 스택 개수에 더하고, 스택에서 제거
total_sticks += 1
stack.pop()
print(total_sticks)[15649] N과 M (1)
n, m = map(int, input().split())
def sequence(used = []):
if len(used) == m:
print(" ".join(map(str, used)))
return
for num in range(1, n + 1):
if not num in used:
used.append(num)
sequence(used)
used.pop()
sequence()[15650] N과 M (2)
위의 15649번 문제의 연장선 같은 느낌이라 쉽게 풀었다.
오름차순으로 정렬하기 위한 코드만 추가하면 쉽게 해결!
n, m = map(int, input().split()) # n까지의 자연수 중에 중복 없이 m개를 고른 수열
def sequence(used=[]):
if len(used) == m: # 수열 길이가 m이 되면 리턴
print(" ".join(map(str, used)))
return
for num in range(1, n+1):
if (used == []) or (used[-1] < num): # 수열에 값이 하나도 없거나 수열 마지막 값보다 크면 추가
used.append(num)
sequence(used)
used.pop()
sequence()[9663] N-Queen
일단 문제를 읽었을 때 체스 룰부터 몰라서 당황..
처음엔 이차원 배열로 풀려고 했으나, 수업에서 굳이 이차원 배열을 하지 않고도 하는 법을 배웠다.
손으로 그리면 쉽지만, 하나하나 직접 구현하는 게 더 힘든 문제..
수업을 듣고도 다시 혼자 구현하는 데 시간이 많이 걸렸다.
그랬더니 또 시간 초과...
Python 3 를 이용해서 최대한 시간초과가 안 나게 하고 싶었지만..
결국 블로그 서칭을 하다하다 포기하고, PyPy3로 해서 통과했다.
Python 3 로는 도대체 어떻게 하는 거야 ㅠㅠ
# n x n 체스판 위에 n개의 퀸을 서로 공격할 수 없게 놓는다.
# 퀸은 가로, 세로, 대각선 방향으로의 이동이 가능하다. (같은 열, 행, 대각선 방향에 다른 퀸을 둘 수 없음)
n = int(input())
# 크기가 n인 리스트를 만들어서, 각 줄당 퀸이 위치하는 인덱스를 값으로 두면 2차원 배열을 안 만들고 해결 가능!
queens = [-1] * n # n = 4이면, [-1, -1, -1, -1] (인덱스가 아닌 -1을 초기값 지정)
result = 0
def is_valid(row, col):
for i in range(row): # 현재 체크하는 행의 이전 행까지만 확인!
# 같은 열에 위치한 퀸이 있을 때 or 양쪽 대각선 방향에 퀸이 존재할 때
if (queens[i] == col) or (abs(queens[i] - col) == abs(i - row)):
return False
return True
def n_queens(row):
global result
if row == n: # 모든 행 탐색 완료
result += 1
return
for col in range(n):
queens[row] = col # 지금 행, 열 위치에 퀸을 두기
if is_valid(row, col): # 퀸의 위치가 괜찮은지 체크
n_queens(row + 1) # 괜찮으면 row 하나 높여서 다시 진행
n_queens(0)
print(result)[1759] 암호 만들기
이 문제는 혼자 풀었다! 재밌었음!
# l = 암호를 구성하는 문자 개수, c = 후보 문자의 개수
l, c = map(int, input().split())
letters = list(input().split()) # 중복된 문자 없음
letters.sort() # 문자열 오름차순 정렬
vowels = "aeiou"
def decrypt(code=""):
if len(code) == l: # 탈출 조건
vowel_cnt = sum(1 for v in "aeiou" if v in code)
consonant_cnt = len(code) - vowel_cnt
if vowel_cnt >= 1 and consonant_cnt >= 2:
print(code)
return
for i in range(len(letters)):
if code == "" and i > (c-l): # c-l 번째 인덱스 까지만 첫 문자가 될 수 있음
break
if not letters[i] in code: # 중복된 문자 없어야 함
if code == "" or (code[-1] < letters[i]):
code += letters[i]
decrypt(code)
code = code[:-1]
decrypt()