스택을 쌈싸먹어 보자!

스택

특징

• 한 쪽으로만 자료를 넣고 뺄 수 있다
• 위 특징 때문에 제일 먼저 들어간 자료가 제일 나중에 나오는 구조 = 선입후출 (LIFO)

스택의 구현

• 배열을 이용, 자료를 넣을 땐 size가 늘어나고 뺄 땐 size가 줄어드는 원리

문제 예제 1 (백준 9012 괄호)

https://www.acmicpc.net/problem/9012

내 풀이

• '('와 ')'의 쌍이 안 맞는 경우가 있다면 NO를 출력하면 된다.
  • '('가 ')'보다 먼저 나와야 함
    • 즉 현재 위치에서 ')'의 수는 항상 '('의 수보다 작거나 같아야 함
    • 동시에 문자열 끝까지 갔을 때, '('의 수와 ')'의 수는 같아야 함
• 문자열을 입력받은 후, 첫 글자부터 마지막 글자까지 넘어가면서 괄호 수를 센다.
  • 만약 반복문 도는 도중에 '('의 수가 ')'의 수보다 적어진다면 바로 리턴
    • (불필요한 반복을 줄이기 위함)
  • 끝까지 돌았을 때 '('의 수와 ')'의 수 비교

  public static void count(String str) {
    int left = 0;
    int right = 0;

    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '(') left++;
      else right++;

      if (right > left) {
        System.out.println("NO");
        return;
      }
    }

    if (right != left) System.out.println("NO");
    else System.out.println("YES");
  }

• 맞았당
  

해설

• 닫는 괄호가 나왔을 때, 아직 짝이 없는 여는 괄호와 매칭한다면?
  • 모든 문자에 대해 검사를 수행해야 하므로 시간 복잡도는 O(N)
• (풀이) 스택에 아직 짝이 없는 여는 괄호를 집어 넣고, 닫는 괄호가 나올 때마다 하나씩 스택에서 빼주는 방식으로 구현한다.
  • 이 경우 최종적으로 스택이 비었는지 아닌지 체크만 하면 되니까 시간 복잡도는 O(1)
  • 근데 이제 이걸 스택에 직접 넣고 빼지 말고, cnt 값을 이용하면 좀 더 쉬워진다!
    • cnt가 음수인지 아닌지로 판별하는 방식

훔 풀이를 어떻게 하느냐보다, 이 문제를 보고 스택이 생각났냐 안났냐로 접근하면 좋을 것 같다..! 사실 풀이를 듣고도 왜 굳이 스택을 응용해야 하는지 모르겠다
(어차피 문자열의 처음부터 끝까지 반복을 돌아야 하는건 똑같으니까)

문제 예제 2 (백준 9012 쇠막대기)

https://www.acmicpc.net/problem/10799

내 풀이

• 이 친구도 결국 방금 풀었던 괄호 쌍 만드는 문제!
• 스택을 응용해서 풀어보자.
  • 여는 괄호가 나오면 스택에 넣는다.
  • 닫는 괄호가 나오면 스택에서 뺀다. 이때 result += 1
• 이렇게 입력 문자열 끝까지 돈 다음, result 수를 출력하면 될 것 같다.
  • 근데 이제 쇠막대기가 겹쳐있을 수 있다는 점을 고려해야 하는..!
  • 여는 괄호가 연속해서 나온다면 -> 즉, 닫는 괄호가 나와서 스택을 pop했을 때 스택이 비지 않았다면 스택 사이즈만큼 더해주면 된다.
• 라고 생각했는데 테케에서 틀렸다ㅋㅎ
  • )(의 경우와 ())(()의 경우, 즉 가운데가 빈 경우와 아닌 경우를 고려해야 하기 때문!
    

• 즉 인접한 쇠 막대기가 있냐 없냐로 result를 증가시켜야 한다.
  • 그럼 인접한 쇠 막대기가 있다는걸 코드로 어떻게 알 수 있을까?
    • 위 사진에서 제일 작은 쇠막대기가 +1이 될 때, 그 밑에 있는 친구들은 카운트되면 안된다. 아직 안 잘렸으니까! 이 차이에서 어떻게 알 수 있는지 잡아보자.
      • 밑까지 전부 잘리는 경우, 즉 인접한 쇠막대가 없는 경우는 여는 괄호와 닫는 괄호가 바로 이어서 나오는 경우다.
      • 밑은 안 잘리는 경우, 즉 인접한 쇠막대가 있는 경우는 여는 괄호와 닫는 괄호의 사이가 떨어져 있는 경우다.
  • 하지만 여는 괄호와 닫는 괄호가 연달아 나오는지 알기 위해선 인덱스가 필요하다.
    • 어차피 스택에 괄호를 넣어봤자 쓸모가 없으니 (닫는 괄호 나올 때 pop하는 용도로 썼으니 안에 뭐가 들어가도 상관없음) 인덱스를 넣어서 풀어보자.

    for (int i=0; i<str.length(); i++) {
      if (str.charAt(i) == '(') stack.push(i);
      else {
        if (i-1 == stack.pop()) result += stack.size();
        else result += 1;
      }
    }

• 맞았당22
  

해설

• 옹 같은 방식으로 인덱스로 접근했다! ^____^ 햅비~

문제 예제 3 (백준 1406 에디터)

https://www.acmicpc.net/problem/9012

내 풀이

• 요건 예전에 풀었던 문제라 생략!
• 스택을 이용해 풀었고, 커서 왼쪽과 오른쪽을 구분해서 명령어마다 push, pop 작업을 수행하도록 구현했었다.

해설

• 문제 N 제한이 제일 중요하다!
  • 조건에 따라, 문자열의 길이는 최대 60만이 될 수 있다.
  • 단순 문자열로 풀면 L은 O(1), D는 O(1), B는 O(N), P는 O(N)으로 O(N^2)가 나와 시간 초과가 뜰 것
• 따라서 좀 더 효율적인 방식으로 -> 커서를 기준으로 왼쪽과 오른쪽으로 나눠서 풀자!
  • 왼쪽 오른쪽 번갈아 push, pop을 먹이면 모든 명령이 O(1)이 된다.
  • 즉 O(n)이 되므로 문제 제한 시간에 딱 맞출 수 있게 된다.
  
  

옹 접근 자체는 맞았는데, 이렇게 시간 복잡도를 하나하나 따지진 않았던 것 같다. 솔직히 문제 분류에서 스택인거 보고 힌트 얻었던 것 같군 😇 조건과 시간 복잡도 따지는 연습을 해야겠다.