99클럽 코테 스터디 15일차 TIL - 그리디 (백준13417 - 카드 문자열)

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

• 오늘의 학습 키워드 : 그리디

1. 덱 초기화:첫 번째 카드는 그대로 덱(초기값 설정)
2. 카드를 덱의 왼쪽 또는 오른쪽에 추가:
    2-1. c <= queue [0] : 새 카드가 덱의 가장 왼쪽 카드보다 작거나 같으면 덱의 왼쪽에 추가(사전순 유지 가능)
    2-2. c > queue[0]: 새 카드가 더 크면 덱의 오른쪽에 추가
3. 덱을 문자열로 변환 후 출력 : ''.join(queue)를 사용해 문자열로 합치고 출력

• 공부한 내용
  - 덱으로 생각했던 이유 : 양쪽 끝에서 빠르게 원소를 추가
  

  import sys
  from collections import deque
  
  # 테스트 케이스 수를 입력받음
  T = int(sys.stdin.readline().strip())
  
  # 각 테스트 케이스에 대해 처리
  for i in range(T):
      # 카드의 개수를 입력받음
      N = int(sys.stdin.readline().strip())
      # 카드에 적힌 알파벳 순서를 리스트로 입력받음
      cards = sys.stdin.readline().strip().split()
      
      # 첫 번째 카드를 덱에 초기값으로 추가
      queue = deque([cards[0]])
      
      # 두 번째 카드부터 차례로 처리
      for c in cards[1:]:
          # 현재 덱의 가장 왼쪽 카드(queue[0])와 비교
          # c가 더 작거나 같으면 덱의 왼쪽에 추가하여 사전순을 빠르게 유지
          if c <= queue[0]:  
              queue.appendleft(c)
          else:
              # c가 더 크면 덱의 오른쪽에 추가
              queue.append(c)
      
      # 덱을 문자열로 변환하여 결과 출력
      print(''.join(queue))

• 오늘의 회고
  • 처음에 틀린 이유는 사전순 배열이고, 문제를 잘못 이해했다.
    무조건 처음 뽑은 카드값이 무조건 가운데에서 생각하고 해야한다고 생각했는데 기준이 queue [0]이었다는것 그 풀이가 잘못되었다.
  • 오늘은 어제보다는 좀 더 나한테는 어려운 듯..? 쉬운 문제? 그게 바로 그리디인가 싶기도
  • 오늘은 짤 안 넣어야지 푸하하 🦹