[041] 프로그래머스: 유효한 괄호, 두 큐 합 같게 만들기, 괄호 회전하기, 주식 가격

 
2024.07.05(금)
 
알고리즘 2일차

특강이기에
세부 내용은 노션에 기록
티스토리에는 출퇴근 복습용 코드만 기록
 

---

 

Queue, Stack, 문자열

 

유효한 괄호

▼ 내가 작성한 코드

import java.util.
import java.util.ArrayDeque;

public class Solution{
    boolean solution(String s){
        boolean answer = true;
//         Stack 사용법
        Deque<Integer> s = new ArrayDeque<>();
        
        //for 반복문을 돌려서 문자 하나하나에 접근한다.
        for(int i=0; i<s.length; i++){
            char c = s.charAt(i);
            
//             열린 괄호
       if( c == ')'){
           stack.push(c);
       }else{
//            닫힌 괄호
           stack.pop();
       }
        }

            //스택에 넣어준다
        //닫힌 괄호면~
            //스택 팝()
        //비어있으면 합이 맞아서 true
        //괄호가 남으면 유효하지 않아서 false
        return answer;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        String s1 = "(())()"

    }
//     비어있지않으면 false, 비어있다면 true
     if (!stack.isEmpty()) {
            System.out.println(false);System.out.println(true);
}

 

▼ 완성 코드

import java.util.*;

public class Solution{
    boolean solution(String s){
        boolean answer = true;
//         Stack 사용법
        Deque<Character> stack = new ArrayDeque<>();
        
        //for 반복문을 돌려서 문자 하나하나에 접근한다.
        for(int i=0; i < s.length(); i++){
            char c = s.charAt(i);
            
//             열린 괄호
       if( c == '('){
           stack.push(c);
       }else{
           if(stack.isEmpty()) return false;
//            닫힌 괄호
           stack.pop();
       }
        }
        answer = stack.isEmpty();
        return answer;
    }
}

 

> if (s.charAt(0) == ')' || s.charAt(s.length()-1 == '(') return false;

> 루프를 돌지 않고 false 값이 나올 수 있는 것 체크해도 무방 (점수에는 크리티컬한 영향을 주지 않음)

 

Temperature
 
▼ 완성 코드

import java.util.*;

class Solution {
    public int[] solution(int[] temps) {
        int[] ans = new int[temps.length]; // 결과 배열 초기화
        Stack<Integer> stack = new Stack<>(); // 인덱스를 저장할 스택
        
        for (int day = 0; day < temps.length; day++) { // 각 날에 대해 순회
            // 스택이 비어있지 않고 현재 날의 온도가 스택 최상단 날의 온도보다 높으면
            while (!stack.isEmpty() && temps[stack.peek()] < temps[day]) {
                int prevDay = stack.pop(); // 스택에서 제거된 날
                ans[prevDay] = day - prevDay; // 결과 배열에 일 수를 저장
            }
            stack.push(day); // 현재 날을 스택에 추가
        }
        
        return ans; // 결과 배열 반환
    }
    
    // 테스트 코드
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] result = sol.solution(temps);
        System.out.println(Arrays.toString(result)); // 예상 출력: [1, 1, 4, 2, 1, 1, 0, 0]
    }
}

 

두 큐 합 같게 만들기

 

코드 작성 순서 익히기

 

1.

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
//         Queue 인터페이스 활용 (1, 2 나눠서 생성)
        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();

 

 

▶ Queue 인터페이스를 2개 만들기

 

2.

        int q1sum = 0;
        int q2sum = 0;
        
        for(int value: queue1){
            q1.add(value);
            q1sum += value;
        }
        
        for(int value: queue2){
            q2.add(value);
            q2sum += value;
        }

 

▶q1sum, q2sum 만들기 → for문 사용

 

3.

        if(q1sum > q2sum){
            
            
        }
       
        if(q2sum > q2sum){
            
        }
        
        
        
        
    }
}

 

▶ q1sum과 q2sum의 값 비교

 

4. 

        for(int value: queue1){
            q1.add(value);
            q1sum += value;
        }
        
        for(int value: queue2){
            q2.add(value);
            q2sum += value;
        }
        
        for(int i = 0; i < 4*n; i++){
        if(q1sum > q2sum){
            int value = q1.remove();
            q2.add(value);
            q1sum -= value;
            q2sum += value; 
        }else if(q2sum > q1sum){
            int value = q2.remove();
            q1.add(value);
            q2sum -= value;
            q1sum += value; 
        }  else {
//             count 대신 i로 횟수 구현
            return i;
        }
    }
        return -1;
}
}

 

해당 문제 투 포인터로 풀어보기

 

괄호 회전하기

 
▼ 내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        boolean answer = true;
        Deque<Integer> stack = new ArrayDeque<>();
        
        for(int i = 0; i < s.length; i ++){
            char c = s.charAt(i);
            
            if(isValid(c) = true) {
                stack.push(c);
                count++;
            }else{
                stack.pop(c);
                count++;
            }
        }
        return answer;
    }
}

 

▼ 완성 코드

import java.util.*; // 필요한 라이브러리들을 임포트합니다.

class Solution {
    public int solution(String s) {
        // 주어진 문자열을 두 번 연결하여 확장된 문자열을 만듭니다.
        String extendedS = s + s;
        int answer = 0; // 유효한 회전 문자열의 개수를 저장할 변수입니다.

        // 주어진 문자열의 길이만큼 회전을 시도합니다.
        for (int i = 0; i < s.length(); i++) {
            // 회전된 문자열의 유효성을 검사하고 유효하면 answer를 증가시킵니다.
            if (isValid(extendedS.substring(i, i + s.length()))) answer++;
        }

        // 유효한 회전 문자열의 개수를 반환합니다.
        return answer;
    }

    // 주어진 문자열이 유효한 괄호 문자열인지 검사하는 메서드입니다.
    private boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>(); // 괄호를 저장할 스택입니다.

        // 문자열의 각 문자를 순회합니다.
        for (char current : s.toCharArray()) {
            // 열린 괄호는 스택에 푸시합니다.
            if (current == '(' || current == '{' || current == '[') {
                stack.push(current);
            } else {
                // 닫힌 괄호가 나왔을 때 스택이 비어 있으면 유효하지 않은 문자열입니다.
                if (stack.isEmpty()) return false;

                // 스택의 상단 괄호와 현재 닫힌 괄호가 맞는지 확인합니다.
                char target = stack.pop();
                if ((target == '(' && current != ')') ||
                    (target == '{' && current != '}') ||
                    (target == '[' && current != ']')) {
                    return false; // 괄호가 맞지 않으면 유효하지 않은 문자열입니다.
                }
            }
        }
        // 스택이 비어 있으면 모든 괄호가 유효하게 닫혔음을 의미합니다.
        return stack.isEmpty();
    }
}

 

주식가격

 
▼ 내가 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
//         p 배열 초기화해둠
        int[] p = new int[prices.length];
//         Stack 원리 활용
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < prices.length; i++){
            for(int j = 0; j < i ; j++){
//                 count를 담는 함수를 만들어둬야하나?
                if(stack[i] <= stack[j]) count++; return false;
            }
        }
        return p;
    }
}

 

▼ 완성 코드

 

ㅇ