체육복
https://school.programmers.co.kr/learn/courses/30/lessons/42862
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
import java.util.*;
import java.io.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int resP = reserve.length; //여벌 체육복 가진 학생 수
int lostP = lost.length;
PriorityQueue <Integer> pqStudent = new PriorityQueue<>();
PriorityQueue <Integer> pqRes = new PriorityQueue<>(); //여분인 애들 저장해주기.
PriorityQueue <Integer> pqLost = new PriorityQueue<>();
for(int i = n; i >= 1; i--){
pqStudent.add(i);
}
for(int i = resP-1; i >= 0; i--){
pqRes.add(reserve[i]);
pqRes.add(reserve[i]);
}
for(int i = lostP-1; i >= 0; i--){
pqLost.add(lost[i]);
}
//이제 처리해주면 됨.
while(pqStudent.size() > 0){
int curr = pqStudent.poll();
if(pqRes.size() > 0 && pqLost.contains(curr)){
if(curr == pqRes.poll()-1 || curr == pqRes.poll()+1){
pqRes.remove();
}
answer++;
}
else if(pqRes.size() > 0 && !pqLost.contains(curr)){
if(pqRes.contains(curr)){
pqRes.remove();
answer++;
}
else answer++;
}
else if(pqRes.size() == 0) {
if(!pqLost.contains(curr)) answer++;
}
}
return answer;
}
}
틀린 내 코드.
여벌을 가져온 학생이 옷을 잃어버릴 수 있다는 중요한 조건을 빼먹고 풀어나가기 시작한 것부터 잘못됨ㅋㅋㅋㅋ
이렇게하면 안됨. 정확도 40퍼대 뜬다.
다른 코드 참고
import java.util.*;
import java.io.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n-lost.length;
Arrays.sort(lost);
Arrays.sort(reserve);
for(int i=0; i<lost.length; i++){
for(int j=0; j<reserve.length; j++){
if(reserve[j]==lost[i]){
answer++;
lost[i] =-1;
reserve[j] =-1;
break;
}
}
}
for(int i=0; i<lost.length; i++){
for(int j=0; j<reserve.length; j++){
if(reserve[j]==lost[i]-1 || reserve[j]==lost[i]+1){
answer++;
lost[i]=-1;
reserve[j]=-1;
break;
}
}
}
return answer;
}
}
이중for문으로 배열을 돌면서 -1로 무의미한 값 처리를 해주기...
이렇게하면 굳이 추가적으로 queue를 만들 필요없이 간단하게 무의미한 값 처리를 할 수 있다.
큰 수 만들기★
https://school.programmers.co.kr/learn/courses/30/lessons/42883
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
핵심 로직: len-k자리 수를 만드려면> 구간을 만들어 len-k만큼 반복하고> 그 구간 내에서의 최댓값을 sb에 더해주면 되겠네
class Solution {
public String solution(String number, int k) {
String answer = "";
int len = number.length();
int idx = 0;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < len - k; i++) { //구간을 밀어주는 반복문. len-k번만큼 반복
int max = 0;
for(int j = idx; j <= i + k; j++) { //최댓값의 위치(인덱스)를 다루는 반복문
if(max < number.charAt(j) -'0') {
max = number.charAt(j)-'0';
idx = j + 1; //찾은 최댓값 다음 위치부터 탐색
}
}
sb.append(max);
}
return sb.toString();
}
}
단속카메라
https://school.programmers.co.kr/learn/courses/30/lessons/42884
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
핵심 로직: 끝나는 지점을 기준으로 오름차순 정렬을 해준다.
import java.io.*;
import java.util.*;
class Solution {
public int solution(int[][] routes) {
Arrays.sort(routes, (o1,o2)->{
// routes[1]이 동일하면
if(o1[1] == o2[1]) {
//routes[0]로 비교
return o1[0] - o2[0];
}
//오름차순 정렬
return o1[1] - o2[1];
});
int answer = 1;
int end = routes[0][1];
for(int i = 1; i < routes.length; i++) {
if(routes[i][0] > end) {
answer += 1;
end = routes[i][1];
}
}
return answer;
}
}
구명보트
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 문제는 특정한 길이의 구간을 잡는 것에 집중하면 안된다.
처음에 정렬한 후, 구간의 길이를 2로 설정하고 구간 내에 있는 사람들의 몸무게를 limit와 비교하는 식으로 구현하다가 이렇게되면 첫번째, 세번째 혹은 첫번째, 네번째 사람을 하나에 태우는 경우를 처리하지 못한다는 것을 깨달음
그래서 다른 방식으로 접근을 했는데, 우선 몸무게가 무거운 사람부터 처리를 해줘야할 것 같았다.
왜냐? 무거운 사람들이 limit보다 무거울 확률이 높으므로 빠르게 처리해주자는 판단.
따라서 for문을 뒤에서부터, 즉 people.length-1부터 순차적으로 탐색한다.
그리고 사람을 한명만 태울지, 두명을 태울지 판단이 필요.
limit보다 적으면 사람을 한명 더 태우고(idx++) answer++ 해준다.
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int idx = 0;
for(int i = people.length-1; i >= idx ; i--){
if((people[idx]+people[i]) <= limit){
idx++;
}
answer++;
}
return answer;
}
}
'Algorithms > programmers' 카테고리의 다른 글
[이분탐색] 징검다리 건너기 (0) | 2024.01.23 |
---|---|
[이분탐색] 프로그래머스 입국심사 (0) | 2024.01.11 |
[Dynamic Programming] 프로그래머스 정수삼각형 (0) | 2023.12.26 |
[DFS/BFS] 프로그래머스 타겟넘버, 네트워크 (1) | 2023.12.22 |
[완전탐색] 프로그래머스 최소직사각형 (0) | 2023.12.01 |