[프로그래머스] 문제별 생각 포인트 (계속 추가됨.)

 

 

 

 

 

📍 스택/큐

1. 올바른 괄호
   • 방법1 : StringBuilder 사용

     • 	String	StringBuilder
       타입	불변(immutable) 객체	가변(mutable) 배열
       문자열 저장	String 객체 생성	내부적으로 가변 배열을 사용해서 문자 저장
       문자열 수정	수정할 때마다 새로운 String 객체를 생성	기존의 배열을 수정
       대량의 문자열 조작	계속해서 문자 String객체를 생성해야하기 때문에, 메모리 소비가 증가하고 성능이 저하	기존의 배열을 수정해서 조작

     • • String s = "aa"; // "aa"라는 새로운 String 객체가 생성되고, s가 이 객체를 참조
         String c = "bb"; // "bb"라는 새로운 String 객체가 생성되고, c가 이 객체를 참조
         
         s = s + c; // s에 "aa" + "bb"를 합친 새로운 String 객체가 생성

          
       • s는 이제 "aabb"를 참조하게 되지만, 원래의 "aa"라는 String 객체는 여전히 메모리에 존재함.
       • s가 "aabb"를 참조하게 되면서, "aa"라는 객체는 여전히 존재합니다. 다른 어떤 변수도 이 객체를 참조하지 않으면, 이 객체는 가비지 컬렉터에 의해 수거될 때까지 메모리에 남아 있습니다.
       • 즉, String을 수정할 때마다 새로운 객체가 생성되므로, 이전 문자열은 메모리에서 여전히 유지되지만 더 이상 접근할 방법이 없게 될 수 있습니다.
   • 방법2 : Stack 또는  deque(덱) --> stack 보다 향상된.. 스택과 큐를 합쳐놓은 것이라 생각하면 됨

     • import java.util.Stack;
       
       public class ValidParentheses {
       	// 스택 사용.
           public static boolean useStack(String s) {
               Stack<Character> stack = new Stack<>(); 
       
               for (char c : s.toCharArray()) {
                   if (c == '(') {
                       stack.push(c); // 열린 괄호는 스택에 추가
                   } else if (c == ')') {
                       if (stack.isEmpty()) {
                           return false; // 스택이 비어 있으면 닫힌 괄호가 유효하지 않음
                       }
                       stack.pop(); // 쌍이 맞는 경우 열린 괄호 제거
                   }
               }
       
               return stack.isEmpty(); // 최종적으로 스택이 비어 있어야 유효한 문자열
           }
           
           
           // 덱 사용.
           public static boolean useDeque(String s) {
               Deque<Character> deque = new ArrayDeque<>();
       
               for (char c : s.toCharArray()) {
                   if (c == '(') {
                       deque.addLast(c); // 열린 괄호는 뒤에 추가
                   } else if (c == ')') {
                       if (deque.isEmpty()) {
                           return false; // 스택이 비어 있으면 닫힌 괄호가 유효하지 않음
                       }
                       deque.removeLast(); // 쌍이 맞는 경우 열린 괄호 제거
                   }
               }
       
               return deque.isEmpty(); // 최종적으로 deque가 비어 있어야 유효한 문자열
           }
       
           public static void main(String[] args) {
               String s = "(()())()";
               System.out.println(useStack(s)); // true
               System.out.println(useDeque(s)); // true
           }
       }

   • 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 스택의 push와 pop 연산은 평균적으로 O(1)이므로, 전체 알고리즘의 성능은 효율적입니다.  
2. 다리를 지나는 트럭

 

 

 

 

---

출처 : 

https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Stack-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%A0%95%EB%A6%AC

 

 

---

개발 공부를 위한 블로그 입니다. 

오류가 있다면 댓글로 알려주세요! 

감사합니다.