본문 바로가기

스택17

[프로그래머스 2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임 programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 스택을 사용하는 문제이다. moves를 순회하고 각 요소는 col에 해당한다. col은 고정된 상태로 row=0부터 마지막 row까지 돌면서 0이 아닌 값이 있다면 break 0이 아닌 값이 있다면 스택에 현재 값을 푸쉬하고 두개를 터트릴 수 있는지 확인한다. 그런 다음에 0으로 바꾸고 answer+=2;한다. #include #include #include using namespace std; int.. 2021. 1. 19.
[백준 17298] 오큰수 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택을 사용하는 문제이다. 입력받은 배열을 거꾸로 돌면서 스택의 탑에 위치한 값이 현재 배열 값보다 작다면 팝한다. 만약 스택이 비어있다면 -> 현재값보다 큰 값이 오른쪽에 위치하지 않았다는 의미이므로 -1을 푸쉬한다. 먄약 스택이 비어있지 않다면 -> 스택의 탑값을 결과값에 푸쉬한다. 탑에 있는게 가장 왼쪽에 있는 값이기 때문이다. 그리고 항상 마지막엔 현재 값을 푸쉬해준다. //오큰수 오른쪽에 있으면서 a보다 큰 수 중 .. 2021. 1. 14.
[백준 2493] 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 사용하는 문제이다. 골5였지만 구현은 단순했다. 이전 문제와 마찬가지로 거꾸로 배열을 돌면서 현재값 스택의 탑이라면 pop을 한다. #include #include using namespace std; int n; int arr[500000]; int res[500000]; stack s; int main(void) { scanf("%d", &n); for (i.. 2020. 11. 30.
[백준 6198] 옥상 정원 꾸미기 www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 스택을 사용하는 문제이다. 리트코드에서 유사한 문제를 풀어본 경험이 있어서 접근하기가 어렵지 않았지만... 처음 보면 당황할 꺼 같다. 배열 사이즈가 꽤 크기 때문에 모든 배열에 대해 자기자신보다 큰 수가 나올때까지 카운트한다면 시간 초과가 날 것이다. 스택을 이용하여 거꾸로 배열을 순회하며 o(n)에 끝내도록 한다. 1. 맨 마지막 배열 인덱스를 넣는다. 2. 배열 인덱스를 n-2부터 0까지 돌면서 a.. 2020. 11. 30.

티스토리툴바