사용 알고리즘: 슬라이딩 윈도우...?
사용 언어: java
처음엔 문제를 잘못 이해해서 틀렸다. 처음 회원 등록이 가능한 날을 리턴하는 것인줄..ㅎㅎ
아래는 틀린 코드!
import java.util.*;
class Solution {
Map<String, Integer> map = new HashMap<>();
Map<String, Integer> jun = new HashMap<>();
public int solution(String[] want, int[] number, String[] discount) {
init(want, number);
int answer = 1;
boolean beMember = false;
for (int i = 0; i < 10; i++) {
map.put(discount[i], map.getOrDefault(discount[i], 0) + 1);
}
int beforeLast = 0;
int newLast = 10;
while(newLast < discount.length) {
if(canBeMem()) {
beMember = true;
return answer;
}
answer++;
slidingWindow(discount, beforeLast, newLast);
beforeLast++;
newLast++;
}
// System.out.println(map);
if(!beMember) return 0;
return answer;
}
public void slidingWindow(String[] discount, int bl, int nl) {
//bl빼고
//nl넣고
// System.out.println("A");
map.put(discount[bl], map.get(discount[bl]) - 1);
map.put(discount[nl], map.getOrDefault(discount[nl], 0) + 1);
if(map.get(discount[bl]) == 0) map.remove(discount[bl]);
}
public boolean canBeMem() {
for(String key : map.keySet()) {
if(!jun.containsKey(key))
return false;
if(jun.get(key) != map.get(key))
return false;
}
return true;
}
public void init(String[] want, int[] number) {
for(int i=0; i<want.length; i++) {
jun.put(want[i], number[i]);
}
}
}
회원 등록이 가능한 전체 날짜의 개수를 구하는 것이다.
import java.util.*;
class Solution {
Map<String, Integer> jeongHyun = new HashMap<>();
Map<String, Integer> discounts = new HashMap<>();
public int solution(String[] want, int[] number, String[] discount) {
for(int i=0; i<want.length; i++) {
jeongHyun.put(want[i], number[i]);
}
int answer = 0;
for(int i=0; i<discount.length; i++) {
if(i < 10) {
discounts.put(discount[i], discounts.getOrDefault(discount[i], 0) + 1);
if(i == 9) {
if(registerMember()) {
answer++;
}
}
continue;
}
int removeIdx = i - 10;
discounts.put(discount[removeIdx], discounts.get(discount[removeIdx]) - 1);
discounts.put(discount[i], discounts.getOrDefault(discount[i], 0) + 1);
if(registerMember())
answer++;
}
return answer;
}
public boolean registerMember() {
for(String key : jeongHyun.keySet()) {
if(!discounts.containsKey(key))
return false;
if(jeongHyun.get(key) != discounts.get(key))
return false;
}
return true;
}
}
나는 슬라이딩 윈도우처럼 구현하고 싶어서,
discount가 11번 째일 때부터는 앞의 품목을 빼고, 새로운 품목을 더하면서 계산했다.
그런데 굳이 슬라이딩 윈도우를 하지 않아도 시간 초과가 나지 않는다...ㅎ...ㅎ
'알고리즘 > 프로그래머스' 카테고리의 다른 글
주차 요금 계산 (0) | 2025.02.22 |
---|---|
양궁대회 (1) | 2025.02.21 |
표현 가능한 이진트리 (0) | 2025.01.30 |
뒤에 있는 큰 수 찾기 (0) | 2025.01.28 |
이중우선순위큐 (0) | 2024.12.18 |