본문 바로가기
728x90

스택

[백준] 6198 옥상 정원 꾸미기 / 자바(Java) 문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 해설 각 빌딩별 오른쪽에 있는 자신보다 크거나 같은 빌딩과의 사이에 있는 빌딩의 수들의 합을 구하는 문제입니다. 각 빌딩별로 오른쪽을 탐색하면 확인하는 과정을 거친다면 O(n^2)의 시간복잡도를 가져 시간초과가 날 수 있습니다. 발상의 전환으로 각 빌딩별 자신을 볼 수 있는 빌딩의 수를 구한다면? 각 빌딩기준 왼쪽에 자신보다 큰 빌딩의 수를 구한다면 O(n)으로 해결이 가능하다 생각되.. 더보기
[백준] 17298 오큰수 / 자바(Java) 문제 https://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 해설 오큰수는 수열에서 특정 숫자보다 오른쪽에 있는 수 중 큰 가장 가까운 수이다. 들어오는 값의 순서를 유지하고 오큰수가 정해진 수에 관여하지 않기 위해 stack을 사용한다. 앞에 있는 값부터 순서대로 stack에 넣으면 stack에는 값이 역순으로 들어가게 됩니다. 그러다 오큰수에 해당하는 stack의 peek값보다 큰 수가 들어온다면 stack에서 그 값을 pop해주고 오큰수로 배열에 저장해 주.. 더보기
[프로그래머스] 택배상자 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/131704 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 유사한 문제 2023.10.25 - [[IT] 코딩테스트/[문제 및 풀이] 프로그래머스] - [프로그래머스] 과제 진행하기 / 자바(Java) 해설 스택 자료구조를 사용하면 간편하게 구현 가능하다. order에 있는 값들을 차례로 훑어나갈 인덱스 index를 따로 만들고 for문을 통해 택배 번호를 가진 i 로 택배를 하나씩 가져와 확인한다 우선 택배를 스택에 쌓아두고 내부에 while문을.. 더보기
[프로그래머스] 햄버거 만들기 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/133502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 아래에서부터 쌓이는 재료들이 특정 순서(빵, 야채, 고기, 빵 / 1,2,3,1) 일 때만 포장해 최종적으로 나오는 햄버거의 개수를 구하는 문제입니다. 입출력 예에 따라 [2, 1, 1, 2, 3, 1, 2, 3, 1] 이 차례로 들어올 때 1. 처음 6번째 까지 재료가 들어왔을 때 [2,1,1,2,3,1] 에서 1개가 만들어지고 남은 재료는 [2,1]이 됩니다. 2. 이후 들어오는 .. 더보기
728x90

티스토리툴바