https://school.programmers.co.kr/learn/courses/30/lessons/42862
💡 체육복
- 단순 구현 문제
- lost_num이라는 int형 변수에 lost배열의 크기를 저장해두고, 최대로 빌려준 후 남은 학생 수를 저장하도록 하여, n에서 lost_num을 빼 답을 구할 것이다.
- n+1 크기의 배열 arr을 생성해서, reserve를 참고해 여벌을 가진 번호에 1을, 아니면 0으로 초기화한다.
- 근데, 여벌을 가져온 학생 중 도난을 당할 경우 자신의 옷을 입어야 한다. 따라서 lost배열과 arr배열을 비교해서, lost에 있는 번호가 arr배열에서 값이 1이면 0으로 만들고, lost_num을 1 빼준다.
만약 해당하지 않으면 stack에 lost값을 넣는다. - stack이 비워질 때까지, 하나씩 빼가면서 arr배열에서, 현재 peek값+1 또는 peek값-1 번호가 1의 값을 가질 때 둘 중 하나 먼저 해당되는 것을 빌리도록 하고, 그 arr값을 0으로, lost_num을 1 빼준다. 그리고 pop한다.
- 최종 answer는 n에서 lost_num을 뺀 값이다.
- 여기서 주의할 점은, lost 배열을 사용하기 전에, 오름차순 정렬해야 한다는 점이다.
로직은 동일했는데, 두 테케에서 자꾸 실패가 떠서 왜 그런가 하고, 정렬을 해봤더니 해결됐다.
항상 입력 배열이 정렬되어 주어질 것이라 장담하지 말고, 정렬하고 시작하는 습관을 기르자. - 그리고 나의 풀이 방식의 경우, lost를 오름차순 정렬한 후에, lost 크기만큼 순회하면서 stack에 넣었다.
stack에 넣으면 작은 값부터 들어가고, 나올때는 큰 값부터 나오기 때문에, lost+1번호가 여벌이 있는지를 먼저 확인하도록 하였다.
만약 작은 값부터 나오게 짰다면, lost-1번호가 여벌이 있는지를 먼저 확인하도록 해야, 최대의 값을 가질 수 있을 것이다. - 전체 코드는 아래와 같다.
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int[] arr = new int[n+1];
Arrays.fill(arr,0);
for(int i=0; i<reserve.length; i++){
arr[reserve[i]]++;
}
int lost_num=lost.length;
Stack<Integer> st = new Stack<>();
Arrays.sort(lost);
for(int i=0; i<lost.length; i++){
if(arr[lost[i]]==1){
arr[lost[i]]--;
lost_num--;
}else{
st.push(lost[i]);
}
}
while(!st.isEmpty()){
if(st.peek()<n&&arr[st.peek()+1]==1){
arr[st.peek()+1]--;
lost_num--;
}
else if(st.peek()>1&&arr[st.peek()-1]==1){
arr[st.peek()-1]--;
lost_num--;
}
st.pop();
}
answer=n-lost_num;
return answer;
}
}
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] MYSQL "5월 식품들의 총매출 조회하기" 풀이 / JOIN, GROUP BY (0) | 2024.01.11 |
---|---|
[프로그래머스] MYSQL "특정 기간동안 대여 가능한 자동차들의 대여비용 구하기" 풀이 / JOIN, CAST (1) | 2024.01.11 |
[프로그래머스] JAVA LV3 "여행경로" 풀이 / DFS+BFS 사용 (0) | 2023.10.24 |
[프로그래머스] JAVA LV3 "단어 변환" 풀이 / DFS 사용 (0) | 2023.10.24 |
[프로그래머스] JAVA LV2 "더 맵게" 풀이방법 / 우선순위 큐 - min heap 사용 (0) | 2023.10.20 |