본문 바로가기

스택

 (6)
[백준] 16120번 : PPAP 16120번: PPAP 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 🤔 문제분석 스택자료구조와 P의 개수와 C의 개수를 카운팅하여 조건부 연산을 통하여 PPAP를 만들 수 있는지 확인합니다. P를 만나면 p_count를 증가시키고 C를 만나면 c_count를 증가시킵니다. 이전에 값이 C이고 그다음이 P가 나올경우 p_count의 PPAP를 만들 수 있는지 카운팅을 하고 p_count값을 -2 감소 c_count값을 -1을 감소시킵니다. 이렇게 해서 최종 p_count값이 1이 나온경우만 정답이 됩니다. 마지막에 PPAP → P로 변하기 때문이다. 💻 코드 ..
[백준] 6198번 : 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하여 문제를 해결한다. 스택은 해당위치에서 자기자신보다 낮은 건물이 나올때까지 꺼낸다. 스택에 담긴 자료는 해당 건물포함해서 그 뒤에 볼 수 있는 건물을 담는다. 자기자신보다 큰 건물이기때문에 해당 건물을 포함한 그 뒤에있는 건물 또한 볼 수 있기때문이다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) buildings = list(..
[백준] 17299번 : 오등큰수 17299번: 오등큰수 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하면 문제를 해결 할 수 있다. counter 해당 숫자의 개수를 누적하고, 인덱스로 접근하여 개수의 크기를 판별한다. 만약 리터리에션에서 자기자신보다 작은 counter들은 모두 꺼내고, 작업을 다완료한뒤 stack의 크기를 확인하여 stack이 0보다 크면 스택의 마지막 원소에서 인덱스를 가져오고 그렇지 않다면 -1을 넣는다. 💻 코드 import sys input = sys.stdin.readline N = int(..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 [백준] 6549번 : 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 🤔 문제분석 이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂 해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다. 분할정복, 세그먼트 트리 최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 ..
[프로그래머스] 2023 Kakao Blind Recuiment 택배 배달 수거하기 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제개요 배달해야할 택배와, 수거해야할 재활용 박스가 각 집에 주어졌을때, 트럭이 Cap크기만큼 박스를 트럭에 실을 수 있고, 트럭이 택배를 전달하고, 재활용 박스를 수거하는 최단경로를 구하시오. 🤔 문제분석 택배는 항상 Cap 크기만큼 전달한다. 재활용박스는 항상 Cap크기만큼 수거한다. 택배는 항상 맨 끝에있는 재활용박스를 거두어야할 집 혹은 배달해야할 집으로 이동해야한다. 스택 자료구조..
[백준] 9935번 : 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 해당 문제를 처음에는 파이썬 내장함수로 문제를 풀었지만, 시간복잡도가 o(n^2)으로 시간초과가 발생한다. 해당 문제를 해결하기 위해서 스택 자료구조 를 활용하여 O(n)으로 문제를 풀 수 있다. 개선 이전 ( 내장함수 in , replace 함수 사용 ) char = input() bumpchar = input() while bumpchar in char: char = char.r..

티스토리툴바