Post

[코딩테스트 합격자 되기 스터디] 2주차 - 스택과 큐 (7.14 ~ 7.20)

Posted Updated
By Je Hun Lim 11 min read

코딩테스트 합격자 되기 스터디 2주차

강의 보기 -> 해당되는 부분 책 다시 읽기 -> 블로그 정리
강의는 C++로 되어 있지만 개념적인 내용이라 언어 상관 없이 보고 코드는 각 언어에 맞게 바꾸면 된다.

참고 강의 및 책

인프런 : 코딩테스트 합격자 되기 파이썬, C+_+ 저자님 인프런 강의 링크
Youtube : 코딩테스트 합격자 되기 파이썬, C+_+ 저자님 Youtube 링크
종이책 : 코딩테스트 합격자 되기 파이썬 편
종이책 : 코딩테스트 합격자 되기 C++ 편
종이책 : 코딩테스트 합격자 되기 자바스크립트 편
종이책 : 코딩테스트 합격자 되기 자바 편

ADT란?

  • ADT(Abstract Data Type) : 추상 데이터 타입의 약어
  • 세부 사항을 숨기고 사용자에게 필요한 기능만 명시
  • 필요한 연산만 정의함으로써 자료구조 동작 자체에 집중할 수 있다.
  • 전화번호부
    • put(name, phone)
    • get(name)
    • remove(name)
    • contains(name)
    • size()
    • 위 기능들같이 필요한 기능만 사용할 수 있다.

스택의 개념

  • LIFO(Last In First Out) : 가장 최근에 들어간 원소가 가장 먼저 출력된다.
  • FILO(First In Last Out) : 가장 먼저 들어간 원소가 마지막에 출력된다.
  • 가장 최근에 들어온 원소를 알 수 있다.
  • 가장 최근에 들어온 원소순으로 출력된다.

스택의 ADT

  • algorithm-study

스택의 예시코드

  • C++ -> JAVA
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    import java.util.Stack;
public class Main {
  public static void main(String[] args) {
      Stack<Integer> s = new Stack<>();
      s.push(1); // 스택 s에 데이터 1 추가, 시간 복잡도: O(1)
      s.push(2);
      s.push(3);
      System.out.println(s.peek()); // peek(), 스택의 맨 위 원소 확인, 시간 복잡도: O(1)
      s.pop(); // 스택의 맨 위 원소 제거, 스택이 비어 있으면 예외 발생, 시간 복잡도: O(1)
      System.out.println("Top element after pop: " + s.peek());
      if (!s.isEmpty()) { // 스택이 비어있는지 확인, 시간 복잡도: O(1)
          System.out.println("Stack is not empty");
      } // !연산이 있기 때문에 스택에 데이터가 있을 때 출력문 실행
      System.out.println("Stack size: " + s.size()); // 스택의 크기 확인, 시간 복잡도: O(1)
      while (!s.isEmpty()) {
          System.out.println("Popping element: " + s.peek());
          s.pop(); // 스택데이터를 모두 제거할 때 까지 실행, 시간복잡도: O(1)
      }
      if (s.isEmpty()) {
          System.out.println("Stack is empty after popping all elements");
      }
  }
}

스택의 사용예시1

  • 함수 호출
    1
2
3
4
5
6
7
8
9
10
11
12
13

    void A() {
  System.out.println("Start A");
  B(); 3번
  System.out.println("End A"); 4번
}
void B() {
  System.out.println("Start B");
  System.out.println("End B");
}
int main() { 1번
  A(); 2번
  return 0; 5번
}
  • algorithm-study
  • 함수 호출 시, 현재 함수의 실행상태를 저장, 새로운 함수로 제어 이동

스택의 사용예시2

  • 이전 페이지로 가기
  • algorithm-study
  • 페이지 전환할 때 스택에 푸쉬, 이전 페이지로 돌아갈 때 팝

스택의 사용예시3

  • 괄호 짝 맞추기
  • algorithm-study
  • 열린 괄호 스택에 푸쉬, 닫힌 괄호 나오면 스택에 있는 열린 괄호 팝, 두 개 비교
  • 서로 상쇄되면 계속 진행, 안되면 반복 종료
  • 문자열 끝까지 반복한 후 스택이 비어있으면 성공, 데이터가 있으면 실패

큐의 개념

  • FIFO(First In First Out) : 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조

큐의 ADT

  • algorithm-study
  • front: 가장 먼저 푸시된 원소의 위치

큐의 예시코드

  • C++ -> JAVA
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
  public static void main(String[] args) {
      Queue<Integer> q = new ArrayDeque<>();
      q.offer(1); // offer: 큐의 끝에 요소 추가, 시간복잡도: O(1)
      q.offer(2); // offer 대신 add도 가능하다.
      q.offer(3);
      System.out.println("Front element: " + q.peek()); // peek: 큐의 첫 번째 요소에 접근, O(1)
      q.poll(); // poll: 큐의 첫 번째 요소 제거, O(1)
      System.out.println("Front element after poll: " + q.peek());
      if (!q.isEmpty()) {
          System.out.println("Queue is not empty");
      }
      System.out.println("Queue size: " + q.size()); // size: 큐의 크기 확인, O(1)
  }
}

큐의 사용예시1

  • 줄 서기
  • algorithm-study
  • algorithm-study
  • algorithm-study
  • 제일 앞에 줄 서있는 사람부터 계산을 하고 나간다.

큐의 사용예시2

  • 요세푸스 문제
    • N명의 사람들이 원형으로 둘러앉고, 1~N으로 번호를 매긴다.
    • 시작 위치부터 K번째 사람 제거
    • 제거한 위치부터 다시 K번째 사람 제거
    • 3번째 과정을 한 명이 남을 때 까지 반복
  • algorithm-study 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
  public static int josephus(int N, int K) {
      Queue<Integer> q = new ArrayDeque<>();
      for (int i = 1; i <= N; i++) { // 큐를 초기화하고 1부터 N까지의 요소를 삽입합니다.
          q.add(i); // 시간복잡도: O(N)
      }
      while (q.size() > 1) { // 큐의 크기가 1이 될 때까지 반복합니다.
          // 첫 번째 K-1개의 요소를 큐의 뒤로 이동시킵니다.
          for (int i = 0; i < K - 1; i++) {
              q.add(q.poll()); // 시간복잡도: O(N * K)
          }
          q.poll(); // K번째 요소를 제거합니다.
      }
      return q.peek();
  }
  public static void main(String[] args) {
      int N = 5; // 예시: 5명의 사람이 있을 때
      int K = 2; // 예시: 매 2번째 사람을 제거할 때
      System.out.println("The survivor is: " + josephus(N, K));
  }
}

정리

  • 스택(Stack)
    • LIFO
    • 함수 호출 관리
    • 페이지 탐색
    • 괄호 짝 맞추기
    • 가장 최근 원소를 봐야하는 경우에 사용
    • DFS, 백트래킹에서 사용
  • 큐(Queue)
    • FIFO
    • 줄 서기
    • 요세푸스
    • 들어온 순서대로 나갈 때 사용
    • BFS에서 사용

괄호 회전하기 문제 풀이

  • 괄호 회전하기 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    public static int solution(String s) {
      int count = 0;
      int n = s.length();
      for (int i = 0; i < n; i++) {
          if (isValid(s, i)) {
              count++;
          }
      }
      return count;
  }
  private static boolean isValid(String s, int start) {
      Stack<Character> stack = new Stack<>();
      int n = s.length();
      for (int i = 0; i < n; i++) {
          char c = s.charAt((start + i) % n);
          if (c == '(' || c == '{' || c == '[') {
              stack.push(c);
          } else {
              if (stack.isEmpty()) {
                  return false;
              }
              char top = stack.pop();
              if (!isMatchingPair(top, c)) {
                  return false;
              }
          }
      }
      return stack.isEmpty();
  }
  private static boolean isMatchingPair(char open, char close) {
      return (open == '(' && close == ')') ||
             (open == '{' && close == '}') ||
             (open == '[' && close == ']');
  }
  • 시간복잡도: O(N^2)

주식 가격 문제 풀이

  • 주식 가격 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

      public int[] solution(int[] prices) {
      ArrayDeque<Integer> stack = new ArrayDeque<>();
      int length = prices.length;
      int[] answer = new int[length];
      stack.push(0);
      for (int i = 1; i < length; i++) {
          while(!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
              int pop = stack.pop();
              answer[pop] = i - pop;
          }
          stack.push(i);
      }
      while(!stack.isEmpty()) {
          int pop = stack.pop();
          answer[pop] = length - 1 - pop;
      }
      return answer;
  }
  • 시간복잡도: O(N)

영어 끝말잇기 문제 풀이

  • 영어 끝말잇기 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    public int[] solution(int n, String[] words) {
      Set<String> wordSet = new HashSet<>();
      wordSet.add(words[0]);
      for (int i = 1; i < words.length; i++) {
          String prevWord = words[i - 1];
          String currentWord = words[i];
          if (prevWord.charAt(prevWord.length() - 1) != currentWord.charAt(0)
              || wordSet.contains(currentWord)) {
              int player = (i % n) + 1;
              int turn = (i / n) + 1;
              return new int[]{player, turn};
          }
          wordSet.add(currentWord);
      }
      return new int[]{0, 0};
  }
  • 시간복잡도: O(N)

베스트 앨범 문제 풀이

  • 베스트 앨범 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

      static class Song {
      int plays;
      int index;
      Song(int plays, int index) {
          this.plays = plays;
          this.index = index;
      }
  }
  public int[] solution(String[] genres, int[] plays) {
      Map<String, Integer> genrePlayCount = new HashMap<>();
      Map<String, List<Song>> songsByGenre = new HashMap<>();
      for (int i = 0; i < genres.length; i++) {
          String genre = genres[i];
          int play = plays[i];
          genrePlayCount.put(genre, genrePlayCount.getOrDefault(genre, 0) + play);
          songsByGenre.putIfAbsent(genre, new ArrayList<>());
          songsByGenre.get(genre).add(new Song(play, i));
      }
      List<String> sortedGenres = new ArrayList<>(genrePlayCount.keySet());
      sortedGenres.sort((a, b) -> genrePlayCount.get(b) - genrePlayCount.get(a));
      List<Integer> bestAlbum = new ArrayList<>();
      for (String genre : sortedGenres) {
          List<Song> songs = songsByGenre.get(genre);
          songs.sort((a, b) -> b.plays == a.plays ? a.index - b.index : b.plays - a.plays);
          for (int i = 0; i < Math.min(2, songs.size()); i++) {
              bestAlbum.add(songs.get(i).index);
          }
      }
      return bestAlbum.stream().mapToInt(i -> i).toArray();
  }
  • 못 풀었다… ↑ 다른 사람의 풀이 ↑
  • 시간복잡도: O(n log n)
Algorithm, Study
java algorithm study