
https://school.programmers.co.kr/learn/courses/30/lessons/138476
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
/*
1. 배열을 순회하며 하나씩 Map에 넣으면 시간복잡도는 n^2 이된다.
2. 먼저 정렬하면 n, 순회하며 비교하며 Map에 넣으면 n, Map 에서 찾는것 n
-> 시간복잡도 n
*/
/*
1. Arrays.sort(tangerine)
2. 배열 끝까지 순회하며 비교해서 카운트 증가 후 Map 에 저장
3. Map 에서 가장 value 높은것 부터 찾아서 k와 뺄셈하여 k가 0이 되는 순간을 찾음
4. 결과 배열을 만들어서 반환
*/
int answer = 0;
Arrays.sort(tangerine);
List<Integer> list = new ArrayList<>();
int tmp = tangerine[0];
int count = 1;
int loopCount = 0;
for (int i = 1; i < tangerine.length; i++) {
if (tmp != tangerine[i]) {
tmp = tangerine[i];
list.add(count);
count = 1;
} else if (i == tangerine.length - 1) {
list.add(++count);
} else {
count++;
}
}
int max = 0;
int idx = 0;
while (list.size() > 0) {
for (int i = 0; i < list.size(); i++) {
max = 0;
if (max < list.get(i)) {
max = list.get(i);
idx = i;
}
}
k -= list.get(idx);
list.remove(idx);
if (k <= 0 && loopCount == 0) {
answer = 1;
break;
} else if (k <= 0) {
break;
}
answer++;
loopCount++;
}
return answer;
}
}
한시간 가량 걸려서 나름대로 열심히 풀었으나 또 실패했다.
스트레스가 극심해서... 머리가 멈춰버렸다.ㅋㅋㅋ
주어진 대표 3가지 테스트케이스는 통과했는데 나머지가 안된다.
4, 14, 16, 19, 20, 31, 32 만 통과했다.
다른 분들의 풀이를 배워보자
[프로그래머스] 프로그래머스 귤 고르기 JAVA 자바 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/138476?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁
hjdiary.tistory.com
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer = 0;
Map<Integer, Integer> m=new HashMap<>();
for(int t:tangerine){
m.put(t,m.getOrDefault(t, 0)+1);
}
List<Integer> list=new ArrayList<>(m.values());
Collections.sort(list, Collections.reverseOrder());
for(Integer a:list){
k-=a;
answer++;
if(k<1){
return answer;
}
}
return answer;
}
}
나와 비슷한 로직을 생각하신 것 같다.
다시 풀어보기
23.03.10
다른 문제들을 풀며 논리력이 향상된 것인지 다시 풀어봤는데 빠르게 성공했다.
다른 분의 코드라던가 전혀 영향없이 온전히 스스로 해내서 기분이 좋다.
코드
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer=1;
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(tangerine);
int count=1;
int tmp=0;
for(int i=0; i<tangerine.length-1; i++){
if(tangerine[i]==tangerine[i+1]){
count++;
}
else{
list.add(count);
count=1;
}
}
list.add(count);
list.sort(Comparator.reverseOrder());
for(int item : list){
k=k-item;
if(k<=0){
return answer;
}
answer++;
}
return answer;
}
}
같은 종류인 귤의 개수가 중요하므로 이를 ArrayList에 담았고
이 ArrayList를 내림차순으로 정렬 후, 주어진 k와 비교하는 방식으로 최소 귤 종류의 개수를 알 수 있다.
25분 정도 소요되었다.
'알고리즘 > 문제' 카테고리의 다른 글
| <다시풀기성공>[프로그래머스] lv2 JadenCase문자열만들기 / Java (0) | 2023.02.19 |
|---|---|
| [프로그래머스] Lv2 최댓값과 최솟값 / JAVA (0) | 2023.02.18 |
| [Programmers] 연속 부분 수열 합의 개수 / JAVA -> 실패 (0) | 2023.02.09 |
| [프로그래머스] 과일 장수 / JAVA (0) | 2023.02.06 |
| [Programmers] 문자열 나누기 / JAVA (0) | 2023.01.13 |