728x90 반응형 자료구조8 [백준/Python] 9012 괄호 문제: https://www.acmicpc.net/problem/9012 사용 알고리즘: 스택 입력테스트케이스 개수 T밑으로는 T 개의 테스트케이스가 주어지며, 테스트케이스의 괄호 문자열의 길이는 2 이상 50 이하 괄호의 짝을 맞추는 문제 -> 스택 대표 문제라고 생각하면 됨 주어진 괄호 문자열을 돌면서 1. '(' 인 경우 스택에 추가2. ')' 인 경우빈 스택일 경우 짝이 안 맞으므로 answer 에 'NO' 를 기록빈 스택이 아닐 경우 스택의 맨 위의 요소 pop주어진 괄호 문자열을 다 돌고 나왔는데, 빈 스택이 아닌 경우는 짝이 안 맞는 경우이므로 answer 에 'NO' 를 기록for _ in range(n): s = deque() PS = input().rstrip() .. 2024. 7. 30. [백준/Python] 12789 도키도키 간식드리미 문제: https://www.acmicpc.net/problem/12789 사용 알고리즘: 스택 입력첫째 줄에는 승환이 앞에 서 있는 학생들의 수 N (1 승환이 앞에 서있는 모든 학생들의 번호표 (1, 2, 3, ..., N) 입력으로 주어진 학생들의 번호표를 올바른 순서로 만들 수 있는지 확인하는 문제 -> 스택을 사용해서 넣고 빼야겠다 대기번호 순서대로 간식 받게 하기stack = deque()waitingNum = 1 # 간식을 받을 차례의 대기번호for x in arr: stack.append(x) while stack and stack[-1] == waitingNum: # 빈 스택이 아니고 & 스택 맨 위랑 대기번호가 같을 때 stack.pop() wa.. 2024. 7. 28. [백준/Python] 17413 단어 뒤집기 2 문제: https://www.acmicpc.net/problem/17413 사용 알고리즘: 큐 입력문자열 S 가 주어짐 (S 의 길이는 100,000 이하) 규칙알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다.문자열의 시작과 끝은 공백이 아니다.''가 문자열에 있는 경우 번갈아가면서 등장하며, '태그는 '' 로 끝나는 3 이상인 부분 문자열이고, '' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다. 예제 입력 1baekjoon online judge 예제 출력 1noojkeab enilno .. 2024. 7. 25. [프로그래머스/python] 뒤에 있는 큰 수 찾기 문제: https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 사용 자료구조: 스택 사실 문제의 답을 내는 논리 자체는 너무 쉬워서 이게 왜 Lv. 2 ? 라고 생각했지만.. 23 개의 테스트케이스 중에 11번까지 통과되고 나머지는 시간초과가 떴다. 이중 for 문을 사용하기 때문에 시간 복잡도가 O(n^2) 이 되기 때문에 n 값이 커질수록 실행시간이 길어져 시간 초과가 발생한 것이다. 시간초과코드def findLargerThenMe(cur,.. 2024. 5. 31. 이전 1 2 다음 728x90 반응형
