알고리즘 재활 6일차 - 프로그래머스 괄호 회전하기, 할인 행사

아 ㅋㅋ

 

공부허기 싫다~

 

괄호 회전하기

 

 

먼저 괄호가 왼쪽으로 회전하기 때문에

 

1 2 3 4

2 3 4 1

3 4 1 2 이런식으로 변경을 해줘야 했다.

큐를 써도 됐는데, 문제가 쉬워서 "아 그냥 후딱풀자~!"마인드라 오히려 돌아갔다..

substring 활용해서 s = s.substring(1) + s.charAt(0); 로 회전시켜줬다.

 

import java.io.*;
import java.util.*;
 
public class Solution {
 
    public int solution(String s) {
        int answer = 0;
        int s_length = s.length();
 
 
        for (int k = 0; k < s_length; k++) {
            boolean isValid = true;
            Stack<Character> stack = new Stack<>();
 
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
 
                if (ch == '(' || ch == '[' || ch == '{') {
                    stack.push(ch);
                } else {
                    if (stack.isEmpty()) {
                        isValid = false;
                        break;
                    }
                    char top = stack.pop();
                    if (!chkLogic(top, ch)) {
                        isValid = false;
                        break;
                    }
                }
            }
            if (stack.isEmpty() && isValid) {
                answer++;
//                System.out.println(s);
            }
            s = s.substring(1) + s.charAt(0); 
 
        }
        return answer;
    }
 
    private boolean chkLogic(char start, char end) {
        return (start == '(' && end == ')') || (start == '[' && end == ']') || (start == '{' && end == '}');
    }
}

 

---

 

할인행사

 

슬라이딩 윈도우 알고리즘

 

문제를 읽고 10일동안에 내가 원하는 품목, 개수가 있으면 되겠다 떠올렸다.

그러면 슬라이딩 윈도우 알고리즘으로 정해진 범위에 값을 조정해 주자로 작성했다.

10개의 값을 넣어서 HashMap으로 항목과 개수를 관리해주었고 오른쪽으로 이동해 주면서

오래된 값은 빼고 새로운 값을 넣어주면서 그 Map이 내 'Want' Map과 같으면 answer ++ 늘려줬다.

 

import java.util.*;
 
public class Solution {
 
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
 
        Map<String, Integer> wantMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }
 
        // 이미 있다면 +1
        Map<String, Integer> discountMap = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            discountMap.put(discount[i], discountMap.getOrDefault(discount[i], 0) + 1);
        }
 
        if (matches(wantMap, discountMap)) {
            answer++;
        }
 
        // 하나씩 오른쪽으로 옮기면서 검사하기.
        for (int i = 10; i < discount.length; i++) {
            String oldItem = discount[i - 10];
            String newItem = discount[i];
 
            discountMap.put(oldItem, discountMap.get(oldItem) - 1);
            if (discountMap.get(oldItem) == 0) {
                discountMap.remove(oldItem);
            }
 
            discountMap.put(newItem, discountMap.getOrDefault(newItem, 0) + 1);
 
            // want와 비교
            if (matches(wantMap, discountMap)) {
                answer++;
            }
        }
 
        return answer;
    }
 
    private boolean matches(Map<String, Integer> wantMap, Map<String, Integer> discountMap) {
        for (String key : wantMap.keySet()) {
            if (discountMap.getOrDefault(key, 0) < wantMap.get(key)) {
                return false;
            }
        }
        return true;
    }
 
}