스택

백준 10026 파이썬 풀이 (적록색약, DFS)

이번 문제는 간단하다. 그냥 같은 영역이 얼마나 되는지 찾아내는 것이다. 1. 일반인을 위한 Map, 적록색약인 사람을 위한 Map('G'와 'R'를 동일하게 보는 사람) 2. DFS를 유연하게 만들어서 시간을 줄인다. n = int(input()) NMap = [] WMap = [] for i in range(n): tmp = list(input()) NMap.append(list(tmp)) for j in range(n): if tmp[j] == "G": tmp[j] = "R" WMap.append(tmp) def DFS(x,y, Map): s = [(x,y,Map[x][y])] Map[x][y] = 0 dx = [0,0,1,-1] #동서남북 dy = [1,-1,0,0] while s: x,y,z =..

백준 17298 풀이 (오큰수, 스택)

처음에는 sort로 정렬을 하고 다음수를 바로 찾아내는 방법으로 풀이를 진행했다. list : 3 5 2 7 sorted : 2 3 5 7 여기서 list에 해당하는 수를 sorted에서 찾으면 제거를 해서 출력값을 맞춰줬다. 그러나 문제는 시간이 준나게 오래걸렸다. 왜냐면 index로 어떤 수가 어디에 존재하는지 찾아야해서 연산을 너무 많이했다. n = int(input()) tmp = list(map(int, input().split())) stmp = sorted(tmp) final = [] for i in tmp: index = stmp.index(i) if index != n-1 and len(stmp) != 1: print(stmp[index+1],end=' ') else: print(-1,e..

백준 1874 풀이 (스택 수열, 스택)

문제는 그냥 스택으로 풀어주면된다. 스택을 구성하여 값을 넣었다가 뺐다가 이리저리 하는 문제이다. 문제는 4가 나오면 [1,2,3,4] 까지 받고 4를 반환 => [1,2,3] 3이 나오면 [1,2,3] 에서 3을 반환 => [1,2] 요런 식으로 동작한다. 좋은 점은 오름차순으로 push되기 때문에 값을 계속 해서 증가시키며 push를 하면 된다. 조심해야할점은 각 값을 받으면서 "+"나 "-"를 op리스트에 쌓아준다. 그러다가 문제가 있으면 "NO"를 반환하게 하고, 끝까지 잘 동작하면 "+","-"를 차례로 반환해주면된다. import sys n = int(input()) stack = [] op = [] count =1 for _ in range(n): num = int(sys.stdin.read..

백준 4949 풀이 (균형잡힌 세상, 스택)

이런 소괄호 중괄호 맞게 찾기는 스택으로 풀어야한다. 옛날에 자료구조 공부할때 교수님이 스택으로 문제를 푸셨었다. 만약에 괄호 하나만 확인하는 거면 굳이 스택으로 풀 필요가 없지만 이번 문제는 소괄호와 대괄호로 2개이기 때문에 스택으로 풀어봤다. 1. 만약 (, [ 이라면 스택에 쌓는다. 2. ), ] 가 나오면 스택에 top에 쌓인게 소괄호인지 중괄호인지 비교하여 같으면 스택에서 제거한다. 3. 만약 ), ] 가 먼저 나오면 잘못 입력된 것이기 때문에 바로 종료시킨다. 대강 이러한 느낌으로 코딩을 짜면 코드는 아래와 같다. 좀더 효율적으로 짤 수 있었을거 같은데 내가 좀 무식하게 코딩하다 보니 저렇게 돼버렸다.ㅎㅎ while True: tmp = input() if tmp == ".": break st..

백준 10828 풀이 (스택, sys.stdin.readline, 입력속도 높이기)

문제는 쏘쏘하다 스택을 구현하면 된다. 나는 리스트를 스택처럼 사용하기로 했다. 리스트에는 append(), pop(), len()등 쉽게 활용할수 있는 메소드가 존재하기 때문에 쉽게쉽게 가기로 했다. 처음에 제출을 했을때는 시간초과가 나왔다. 왜 그런건가? 하고 고민을 3초 하다가 sys.stdin.readline으로 바꿔서 풀어보기로 했다. sys.stdin.readline은 한줄을 그대로 입력을 받는다. 따라서 \n(개행문자)가 같이 들어오는 단점이 있으나 굉장히 빠르게 입력을 받기 때문에 많은 입력을 받아야하는경우 쉽게 사용할수있다. 무식하게 코딩을 한 결과 정답을 맞출 수 있었다. import sys n = int(input()) stack = [] for _ in range(n): tmp = ..