Algorithm272 [ 파이썬(python) ] 백준 2493 - 탑 📍 백준 2493 - 탑 문제: 백준 2493 - 탑 💡 나의 풀이 스택을 활용하면 되는 문제인데 머릿속으로는 단계별로 생각이 잘 됐는데 코드로 구현하려니까 쉽지 않았다. 우선 범위가 500,000이기 때문에 이중 반복문을 사용하면 최대 250,000,000,000까지임을 명심해야 한다. 여기서 의문점은 성공코드와 실패 코드의 시간 복잡도의 차이는 (index, slicing)의 차이인것 같은데 왜 시간초과가 나는지 잘 모르겠다.(고수님들 댓글부탁드립니다 :)) --- [ 21. 7. 13. ] 백준에 시간초과 관련하여 질문을 남겼는데 @djm03178님께서 좋은 답변을 해주셨다. 결론적으로 시간복잡도는 다음과 같다. 1. 성공코드(O(N)): 각 원소가 스택에 들어가고 나오는 연산이 한 번씩만 수행된다.. 2021. 7. 9. [ 파이썬(python) ] 백준 2504 - 괄호의 값 📍 백준 2504 - 괄호의 값 문제: 백준 2504 - 괄호의 값 💡 나의 풀이 stack에 값을 넣고 순서를 잘 알았더라면 금방 풀 수 있을 텐데, 나한테는 어려웠던 문제였다. 전체적인 흐름은 다음과 같다. 괄호열이 올바른지 올바르지 않은지 검사한다.(def is_checked) 괄호열이 올바르면 def calc_value 함수로 이동하고 괄호열이 올바르지 않다면 print(0)을 출력한다. 이어서 세부적인 흐름을 살펴보자. is_check()는 단순히 올바른지 아닌지만 확인하면 되기때문에 큰 어려움은 없었으나, calc_value() 함수에서 상당히 애를 먹었다. 어떻게 해결했는지 차근차근 살펴보자. 여는 괄호((, [)면 stack에 집어넣는다. 닫는 괄호가 나올때 )의 경우와 ]의 경우를 나눈다.. 2021. 7. 7. [ 파이썬(python) ] 백준 3986 - 좋은 단어 📍 백준 3986 - 좋은 단어 문제: 백준 3986 - 좋은 단어 💡 나의 풀이 어떤 방식으로 풀어야 할지 고민하다 stack으로 풀었는데 정답판정을 받았다. 문제에서 아치형 곡선으로 만나야 한다고 나와있는데 괄호 쌍맞추는 문제처럼 stack에 들어오는 현재 값과 이전에 있던 stack[-1]과 비교해서 같으면 pop() 다르면 s[i]를 추가하는 방법으로 풀면 된다. 맨 처음 stack이 없을 때 값을 어떻게 넣지??라고 생각하다 stack에 값이 있을 때, 없을 때로 나눠서 조건을 작성했다. 여기서 나의코드와 다른 사람 코드의 차이점은 13 ~ 19번 인데, stack 조건을 and로 합치고 아닌 경우에는 append를 줘도 같은 결과가 나왔길래 가져왔다. 다음 사진은 예제 입력 1을 손으로 그리면.. 2021. 7. 6. [ 파이썬(python) ] 백준 4949 - 균형잡힌 세상 📍 백준 4949 - 균형잡힌 세상 문제: 백준 4949 - 균형잡힌 세상 💡 나의 풀이 문제의 조건을 잘 따져야 하는데 마지막 조건(짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.)은 문자열 공백을 똑같이 줘야 하는 건가?라는 생각이 들면서 조금 헷갈렸다. 그러나 문제에 주어져있지 않기때문에 고려하지 않아도 된다. 올바른괄호를 찾는 문제는 여러 가지 T.C를 넣어가면서 에러가 걸리지 않게 로직을 짜는 것이 중요한 것 같다. 논외로 while True와 while 1의 차이를 물어보는 질문들이 꽤 있었는데, 결론부터 말하자면 python 3에서 두 개의 코드의 시간 차이는 없다. 조금 덧붙여서 말하자면 python 2에서는 while 1이 더 약 3 ~ 4초 가량 더 빠른.. 2021. 7. 5. [ 파이썬(python) ] 백준 10799 - 쇠 막대기 📍 백준 10799 - 쇠 막대기 문제: 백준 10799 - 쇠 막대기 💡 나의 풀이 stack으로 해결할 수 있는 문제이나, 레이저와 쇠 막대기의 관계를 코드로 구현하는데 오래 걸렸다. 이 문제를 풀 때 예제는 올바른(짝이 맞는) 괄호만 주어진다는 점을 알고 풀면 접근하기 쉬울 것이다. 또 하나의 깨알 팁은 입력범위가 100,000이라서 import sys를 써야 시간초과가 나지 않는다. 여는 괄호(()는 stack에 집어넣는다 닫는 괄호())가 나올 때 쇠 막대기인지 레이저인지 구분해야 하는데, 우선 레이저는 인접한 쌍(즉, 현재 index가 ) 이면 무조건 이전 index는 ()이다. 그럼 나머지의 경우는 모두 쇠 막대기로 판단할 수 있다. 레이저의 경우는 현재까지 들어있는 len(stack)을 구.. 2021. 7. 5. 이전 1 ··· 23 24 25 26 27 28 29 ··· 55 다음
