코딩테스트 기록 4일차

코딩테스트 기록 4일차

1. 9012번: 괄호

Problem Link
Solved Link

문제 정리

이 문제의 목적은 주어진 괄호 문자열이 VPS인지 아닌지를 판별하여 그 결과를 “YES” 또는 “NO”로 출력하는 것입니다.

개념 및 접근법

후입선출 특성을 가진 Stack 자료구조를 활용하여, 괄호 문자열의 유효성검사를 한다.

1. 여는 괄호 발견 시 스택에 추가
2. 닫는 괄호 발견 시 스택에서 제거
3. 문자열 검사 종료 후 스택의 빈값 확인.

2. 1966번: 프린터 큐

Problem Link
Solved Link

1. 문제 정리

• 목표: 주어진 문서들의 중요도와 순서를 기반으로, 특정 문서가 몇 번째로 인쇄되는지 찾아내는 것.
• 조건: 문서는 중요도에 따라 비선형적 순서로 인쇄되며, 현재 Queue에서 가장 중요도가 높은 문서부터 인쇄한다.
• 입력:
• • 첫 줄에 테스트 케이스의 수 T
• • 각 테스트 케이스의 첫 줄에 문서의 개수 N과 몇 번째로 인쇄되었는지 궁금한 문서의 위치 M
• • 두 번째 줄에 N개 문서의 중요도
• 출력: 각 테스트 케이스별로 주어진 문서가 몇 번째로 인쇄되는지 출력

1. 개념
   • Queue (FIFO) 자료구조:
     First In First Out, 먼저 들어온 요소가 먼저 나가는 구조. 이 문제에서는 중요도에 따라 요소의 순서가 조정될 수 있다.
   • 우선순위 확인:
     현재 문서보다 중요도가 높은 문서가 있을 경우, 해당 문서를 Queue의 뒤로 보낸다.
2. 접근법
   • Queue 사용:
     문서의 초기 순서와 중요도를 관리하기 위해 Queue 자료구조를 활용한다.
   • 중요도 순 인쇄:
     Queue의 앞에서부터 문서의 중요도를 확인하고, 현재 문서보다 중요도가 높은 문서가 있다면, 현재 문서를 Queue의 뒤로 재배치한다. 그렇지 않으면 인쇄한다.
   • 인쇄 순서 파악:
     궁금한 문서가 인쇄될 때까지 위의 과정을 반복하며, 궁금한 문서가 인쇄될 때의 순서를 반환한다.
     

3. 풍선 터뜨리기

Problem Link
Solved Link

1. 문제 정리

• 목표:
  원형으로 배열된 N개의 풍선을 주어진 규칙에 따라 터뜨리고, 터진 풍선의 번호 순서를 찾는다.
• 조건:
• • 풍선 안에는 -N 이상 N 이하의 정수가 적힌 종이가 들어 있다.
• • 처음에는 1번 풍선을 터뜨린다.
• • 종이에 적힌 숫자만큼 오른쪽(양수) 또는 왼쪽(음수)으로 이동하여 다음 풍선을 터뜨린다.
• • 이동 시 이미 터진 풍선은 제외하고 계산한다.
• • 모든 풍선이 터질 때까지 이 과정을 반복한다.
• 입력:
• • 두번째 줄에는 차례로 각 풍선 안의 종이에 적힌 수가 주어진다. 종이에는 0이 적혀 있지 않다.
• 출력:
• • 터진 풍선의 번호를 차례로 나열한다.

1. 개념
   • 원형 리스트:
     1번 풍선의 왼쪽에는 N번 풍선이 있고, N번 풍선의 오른쪽에는 1번 풍선이 있는 구조.
   • Deque (덱):
     양방향 큐로, 앞뒤 양쪽에서 데이터를 추가하거나 제거할 수 있는 자료구조. 이 문제에서는 풍선의 순서를 조절하는 데 사용된다.
2. 접근법
   • 덱을 사용하여 풍선의 순서를 관리한다. 덱에서 풍선을 하나씩 제거하면서 해당 풍선의 종이에 적힌 숫자에 따라 다음 풍선을 결정한다.
   • 풍선에 적힌 숫자가 양수인 경우 덱의 앞에서부터, 음수인 경우 덱의 뒤에서부터 순서를 조절하여 이동할 풍선을 결정한다.

• 이동 후에 해당 풍선을 터뜨리고, 이 과정을 모든 풍선이 터질 때까지 반복한다
• 각 단계에서 터진 풍선의 번호를 배열에 기록하고, 최종적으로 이 배열을 출력하여 터진 풍선의 순서를 나타낸다.

4. 2493번: 탑

Problem Link
Solved Link

1. 문제 정리

• 목표: 각 탑에서 발사한 레이저 신호가 어느 탑에서 수신되는지 알아내기.

• 조건:
• • 탑의 레이저 신호는 왼쪽 방향으로만 발사됩니다.
• • 하나의 탑에서 발사된 신호는 가장 먼저 만나는 탑에 의해서만 수신됩니다.
• 입력:
• • 첫째 줄에 탑의 수 N (1 ≤ N ≤ 500,000).
• • 둘째 줄에 N개의 탑들의 높이, 각각 1 이상 100,000,000 이하의 정수.
• 출력:
• • 각 탑에서 발사한 레이저 신호를 수신한 탑들의 번호를 공백을 사이에 두고 출력.
• • 레이저 신호를 수신하는 탑이 없으면 0을 출력.

1. 개념
   • 스택(Stack):
   • • 탑의 인덱스를 저장하고, 레이저 신호 수신 여부를 판단하는 데 사용
   • 인덱스(Index):
   • • 각 탑의 위치를 나타내며, 문제에서는 1부터 시작
   • 레이저 신호
   • • 왼쪽 방향으로만 발사됨.
2. 접근법
   • 스택 활용:
     
   • • 현재 탑의 높이보다 낮은 탑의 인덱스는 스택에서 제거합니다.
   • • 스택이 비어있지 않다면, 스택의 맨 위에 있는 탑의 인덱스가 현재 탑의 신호를 수신합니다.

• 순차적 탐색:
• • 각 탑을 왼쪽부터 오른쪽까지 순차적으로 탐색하며, 각 탑에서 발사한 레이저 신호의 수신 여부를 결정합니다.
• 결과 저장:
• • 각 탑별로 신호를 수신한 탑의 인덱스(번호)를 결과 배열에 저장합니다. 인덱스는 1부터 시작하므로, 스택에서 꺼낸 값에 1을 더하여 저장합니다.