자료구조14 [ 파이썬(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. [ 파이썬(python) ] 백준 12789 - 도키도키 간식드리미 📍 백준 12789 - 도키도키 간식드리미 백준 12789 - 도키도키 간식드리미 ⚡️ 나의 풀이 언뜻 쉬워 보였으나 막상 풀어보니까 조금 어려웠다. 맨 앞의 사람만 이동이 가능하다는 지문을 보아 현재 줄 서있는 곳은 queue의 자료구조이고, 가운데 공간에 들어갈 순 있지만 제일 앞이 벽으로 막혔기 때문에 맨 뒤부터 사람이 나와야 한다. 따라서 한 명씩만 설 수 있는 공간은 stack으로 생각하면 쉽다. 대체적으로 queue와 stack 문제는 지문의 의미를 잘 해석해야 어떤 자료형을 사용해야 할지 감이 오는 것 같다. 그 감을 찾기 위해 많은 문제를 풀어봐야겠다. 처음에는 queue에 있는 사람이 다 빠지고 stack을 생각하면 될 줄 알았는데 queue 보다 stack에 더 작은 값이 있으면 sta.. 2021. 6. 30. [ 파이썬(python) ] 백준 1874 - 스택 수열 📍 백준 1874 - 스택 수열 문제: 백준 1874 - 스택 수열 💡 나의 풀이 나에겐 난이도가 있던 문제였다. 문제의 길이는 짧았지만 이해하기까지 시간이 오래 걸렸다. 중요한 포인트는 스택에 push하는 순서는 반드시 오름차순을 유지한다.라는 문장인데, 이를 다시 말하면 push 순서는 현재 만들어야 할 수열보다 작아질 수 없고 오직 current = target 혹은 current > target 할때만 성립한다는 의미다. 이를 이해하기까지는 꽤 오랜 시간이 걸렸다. 또, current는 어떻게 구현해야하지를 고민했는데 1~n까지 선언한 다음 여기서 뽑지 않은 값 중 가장 작은 값들을 가져와야 하는 건가? 생각했는데 결론적으로 current += 1씩 증가하면서 값을 넣으면 된다. current가 .. 2021. 6. 30. [ 파이썬(python) ] 백준 10546 - 배부른 마라토너 📍 백준 10546 - 배부른 마라토너 백준 10546 - 배부른 마라토너 ⚡️ 나의 풀이 저번에 풀었던 프로그래머스 - 완주하지 못한 선수 와 동일한 문제다. 참가자의 수가 100,000이기 때문에 기본적으로 list를 사용해서 풀면 시간 초과가 난다. 그래서 dict를 사용해서 풀었다. 참가자를 저장할 dict와 완주 선수를 저장할 dict를 defaultdict로 선언한다. defaultdict를 선언하면 동일 선수가 나와도 +1을 할 수 있기때문에 유용하게 사용할 수 있다. Counter 라이브러리로 참가자와 완주자의 Counter를 준다. 간단한 팁이지만 Counter끼리는 서로 빼거나 더할 수 있다. 남은 값의 key를 출력한다. 이런방식은 정답 판정을 받을 수 있으나, 메모리와 실행시간이 오.. 2021. 6. 29. 이전 1 2 3 다음
