JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 스택/큐(같은 숫자는 싫어, 기능개발, 올바른 괄호, 프로세스, 다리를 지나는 트럭, 주식가격) 본문
프로그래머스 코딩테스트 고득점 Kit - 스택/큐(같은 숫자는 싫어, 기능개발, 올바른 괄호, 프로세스, 다리를 지나는 트럭, 주식가격)
DEOKJAE KWON 2024. 12. 16. 19:401번 문제: 같은 숫자는 싫어
https://school.programmers.co.kr/learn/courses/30/lessons/12906
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
각 원소는 숫자 0부터 9까지로 이루어진 정수 배열 arr에서 원소들의 순서를 유지한 상태로 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거한 후 남은 수들을 return 하는 solution 함수를 완성해야 한다. 예를 들면,
- arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 한다.
- arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 한다.
접근
스택을 선언하고 for문으로 arr를 순회하며 맨 위에 있는 원소가 현재 원소와 같지 않다면 해당 스택에 현재 원소를 집어넣고, 마지막에 return할 배열 answer[]에 채워넣는다. 이때, 스택이 비어있으면 스택의 맨 위에 있는 원소와 비교할 수 없으므로 해당 조건문을 추가한다.
코드
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
Stack<Integer> stack = new Stack<>();
for (int e : arr) {
if (stack.isEmpty() || stack.peek() != e) {
stack.push(e);
}
}
int[] answer = new int[stack.size()];
while (!stack.isEmpty()) {
answer[stack.size() - 1] = stack.pop();
}
return answer;
}
}2번 문제: 기능개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
각 기능은 진도가 100%일 때 서비스에 반영할 수 있으며, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성해야 한다.
접근
문제의 입출력 예시 중 다음과 같은 예시가 있다.
| progresses | speeds | return |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
return 값에 0이 없으므로 몇 번째 날에 몇 개의 기능을 배포했는지는 알 필요가 없다. 그냥 한 번 배포될 때 몇 개의 배포가 동시에 이뤄지는지 순서대로 적으면 된다.
작업이 끝나는 날짜를 담을 큐를 선언하고, for문에서 progresses[i]가 100 이상이 될 때까지 speeds[i]를 더하면서 해당 횟수를 큐에 담는다. 이후 큐에서 맨 앞의 원소(맨 앞에 있는 기능이 배포될 수 있는 날짜)를 poll하고 이후 맨 앞에 있는 원소(peek, 그 다음 기능이 배포될 수 있는 날짜)와 비교해서 poll된 원소가 배포될 때 배포될 수 있는지 확인해가며 개수를 세가며 리스트에 넣는다. 마지막에 이를 배열로 바꿔주면 된다.
코드
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < progresses.length; i++) {
int day = 0, progress = progresses[i];
while (progress < 100) {
progress += speeds[i];
day++;
}
queue.offer(day);
}
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
int finishedDay = queue.poll(), cnt = 1;
while (!queue.isEmpty() && queue.peek() <= finishedDay) {
queue.poll();
cnt++;
}
list.add(cnt);
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}3번 문제: 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호이다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호이다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해야 한다.
접근
스택 공부할 때 너무나도 많이 나오는 유형의 문제이다. for문을 돌며 i번째 문자 s[i]가 '(' 라면 스택에 넣고, ')' 라면 스택에서 pop이 가능한지 여부를 체크한다. 스택에서 pop이 가능하다면 매치되는 '(' 가 앞에 존재한다는 뜻이고, 가능하지 않다면 존재하지 않으므로 false를 반환한다. 모든 for문을 돌고난 후에 스택이 비어있지 않다면 아직 매치되지 않은 '(' 가 존재한다는 뜻이므로 false를 반환한다.
사실 '(' 와 ')' 만 입력이 가능하기 때문에 굳이 스택을 사용하지 않아도 된다.
코드
import java.util.*;
class Solution {
boolean solution(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}4번 문제: 프로세스
https://school.programmers.co.kr/learn/courses/30/lessons/42587
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내야 한다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 된다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해야 한다.
접근
문제의 입출력 예시 중 다음과 같은 예시가 있다.
| priorities | location | return |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
같은 우선순위의 프로세스들이 있고, 각각의 프로세스는 순서가 있기 때문에 우선순위 큐를 이용할 수는 있지만, 비교 조건문이 복잡해질 수 있다. 그러므로 큐를 사용했다.
프로세스의 인덱스와 우선순위를 저장할 Process 클래스를 만들고 Queue<Process> 타입의 큐를 선언한 뒤 모든 프로세스를 넣는다. 이후 큐가 빌 때까지 현재 큐에 들어있는 가장 우선순위가 높은 프로세스를 찾아 poll한 뒤 poll된 프로세스의 idx가 location과 일치한다면 answer를 리턴하도록 해야 한다.
코드
import java.util.*;
class Process {
private int idx, priority;
public Process(int idx, int priority) {
this.idx = idx;
this.priority = priority;
}
public int getIdx() {
return idx;
}
public int getPriority() {
return priority;
}
}
class Solution {
public int solution(int[] priorities, int location) {
Queue<Process> queue = new LinkedList<>();
for (int i = 0; i < priorities.length; i++) {
queue.offer(new Process(i, priorities[i]));
}
int answer = 1;
while (!queue.isEmpty()) {
int size = queue.size(), max = 0;
while (size-- > 0) {
Process p = queue.poll();
max = Math.max(max, p.getPriority());
queue.offer(p);
}
while (queue.peek().getPriority() < max) {
Process p = queue.poll();
queue.offer(p);
}
if (queue.poll().getIdx() == location) {
return answer;
}
answer++;
}
return -1;
}
}5번 문제: 다리를 지나는 트럭
https://school.programmers.co.kr/learn/courses/30/lessons/42583
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 할 때 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시한다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있을 때 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 한다.
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
| 0 | [] | [] | [7,4,5,6] |
| 1~2 | [] | [7] | [4, 5, 6] |
| 3 | [7] | [4] | [5, 6] |
| 4 | [7] | [4, 5] | [6] |
| 5 | [7, 4] | [5] | [6] |
| 6~7 | [7, 4, 5] | [6] | [] |
| 8 | [7, 4, 5, 6] | [] | [] |
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸린다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성해야 한다.
접근
다리에 bridge_length대의 트럭이 올라갈 수 있을 때 비어있는 칸을 0으로 채워넣는다. 이는 비어있다는 뜻으로, 0kg의 트럭이 올라가있는 것과 의미가 같다고 볼 수 있다. 트럭은 앞에서부터 한 칸씩 앞으로 가며, 먼저 올라간 트럭이 먼저 내려오므로 선입선출 방식을 사용하는 큐를 사용했다.
여기서 선언한 큐는 다리를 의미하며, truck_weights 배열에서 하나씩 다리에 올라갈 수 있는지 여부를 확인하며 앞으로 이동한다.
코드
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < bridge_length; i++) {
queue.offer(0);
}
int answer = bridge_length, sum = 0;
for (int truck_weight : truck_weights) {
while (true) {
sum -= queue.poll();
answer++;
if (sum + truck_weight <= weight) {
queue.offer(truck_weight);
sum += truck_weight;
break;
} else {
queue.offer(0);
}
}
}
return answer;
}
}첫 번째 for문은 다리의 길이만큼 0을 채워넣는다. 아래의 sum은 현재 다리에 올라가있는 트럭들의 무게의 합을 의미한다.
두 번째 for문에서 앞에서부터 하나씩 트럭이 다리 위로 올라온다. 맨 앞의 트럭 하나가 다리를 빠져나왔으므로 sum에서 큐에서 poll된 원소(맨 앞의 트럭의 무게)를 뺀다.
이후 현재 트럭이 올라갈 수 있는지 여부를 if문에서 확인한 뒤, 가능하다면 큐(다리)에 현재 트럭을 올린다는 의미로 큐에 삽입하고, sum에 현재 트럭 무게를 더한다. 가능하지 않다면 아무것도 올라가지 않았다는 의미로 0을 큐에 삽입하는 것을 반복한다.
answer가 0이 아닌 bridge_length부터 시작하하는 이유는 마지막에 올라간 트럭이 다리를 건너는 시간인 bridge_length를 더해야하기 때문이다.
6번 문제: 주식가격
https://school.programmers.co.kr/learn/courses/30/lessons/42584
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성해야 한다.
접근
문제의 입출력 예시 중 다음과 같은 예시가 있다.
| prices | return |
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어진다. 따라서 1초간 가격이 떨어지지 않은 것으로 본다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았다.
주식의 가격은 바로 앞의 가격과 비교한 뒤 그 인덱스들을 비교한 뒤에 answer 배열을 채운다. 이를 위해 주식의 인덱스와 가격을 저장할 Stock 클래스를 만든 뒤 이를 저장할 Stack<Stock> 타입의 스택을 선언한다.
각각의 가격들을 for문으로 순회하며 스택의 peek 값과 비교한다. peek 값의 가격보다 현재 가격이 낮다면 스택에서 이전 가격을 pop한 뒤 인덱스를 비교하며 answer 배열을 채우는 과정을 반복하고, 마지막에 현재 가격을 스택에 push한다.
코드
import java.util.*;
class Stcok {
private int idx, price;
public Stcok(int idx, int price) {
this.idx = idx;
this.price = price;
}
public int getIdx() {
return idx;
}
public int getPrice() {
return price;
}
}
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
Stack<Stcok> stack = new Stack<>();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && stack.peek().getPrice() > prices[i]) {
Stcok stock = stack.pop();
answer[stock.getIdx()] = i - stock.getIdx();
}
stack.push(new Stcok(i, prices[i]));
}
while (!stack.isEmpty()) {
Stcok stock = stack.pop();
answer[stock.getIdx()] = (prices.length - 1) - stock.getIdx();
}
return answer;
}
}마지막 while문에서 for문이 끝난 뒤에 남아있는 스택의 값들을 처리한 뒤 answer 배열을 반환한다.
결론
한 문제당 하나의 글을 작성하려고 했는데 이번 파트도 딱히 설명이 길 것 같지 않아 하나의 글에 모두 작성했는데 지난번과 마찬가지로 똑같이 후회된다. 생각보다 시간이 많이 걸린 것 같다. 그래도 이왕 이렇게 컨셉를 잡은 거 가능한 적은 수의 글로 이를 작성해야겠다.
'프로그래머스 > 코딩테스트 고득점 Kit' 카테고리의 다른 글
| 프로그래머스 코딩테스트 고득점 Kit - 탐욕법(체육복, 조이스틱, 큰 수 만들기, 구명보트, 섬 연결하기, 단속카메라) (0) | 2024.12.24 |
|---|---|
| 프로그래머스 코딩테스트 고득점 Kit - 완전탐색(최소직사각형, 모의고사, 소수 찾기, 카펫, 피로도, 전력망을 둘로 나누기, 모음사전) (1) | 2024.12.21 |
| 프로그래머스 코딩테스트 고득점 Kit - 정렬(K번째수, 가장 큰 수, H-Index) (0) | 2024.12.18 |
| 프로그래머스 코딩테스트 고득점 Kit - 힙(더 맵게, 디스크 컨트롤러, 이중우선순위큐) (2) | 2024.12.17 |
| 프로그래머스 코딩테스트 고득점 Kit - 해시(폰켓몬, 완주하지 못한 선수, 전화번호 목록, 의상, 베스트 앨범) (3) | 2024.12.15 |