Do it! 알고리즘 코딩테스트 3장. 자료구조 ( 3-4, 3-5 )

Cold Ui·2023년 6월 22일
Do it 알고리즘 코딩테스트
0

코딩테스트

목록 보기
2/3
post-thumbnail

03-4. 슬라이딩 윈도우

문제 9

DNA 비밀번호 ( 백준 실버 5 / 12891번 )

P와 S의 길이가 1,000,000으로 매우 크기 떄문에 O(n)의 시간 복잡도로 문제를 해결해야한다. 부분 문자열의 길이가 P이므로 슬라이딩 윈도우 개념을 사용한다.

  • 슬라이딩 윈도우란 리스트 S의 시작점부터 시작하며 길이가 P인 윈도우를 지정하여 오른쪽으로 밀면서 윈도우에 값들이 조건에 맞는지 탐색하는 작업이다.
  • 리스트 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있다.
  1. 먼저 리스트 S와 비밀번호 체크 리스트를 지정한다.
  2. 윈도우에 포함된 문자로 현재 상태 리스트를 만든다. 그런 다음 현재 상태 리스트와 비밀번호 체크 리스트를 비교하여 유효 비밀번호인지 판단한다.
  3. 윈도우를 한 칸씩 이동하며 현재 상태 리스트를 업데이트 한다. 현재 상태 리스트를 업데이트한 이후에는 비밀번호 체크 리스트와 비교하여 비밀번호 유효성을 판단한다. 현재 상태 리스트를 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행한다.
checkList = [0] * 4     # 비밀번호 체크 리스트
myList = [0] * 4        # 현재 상태 리스트
checkSecret = 0         # 몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수

def myadd(c):           # 문자가 들어올 때 호출하는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        myList[0] += 1
        if myList[0] == checkList[0]:
            checkSecret += 1
    elif c == 'C':
        myList[1] += 1
        if myList[1] == checkList[1]:
            checkSecret += 1
    elif c == 'G':
        myList[2] += 1
        if myList[2] == checkList[2]:
            checkSecret += 1
    elif c == 'T':
        myList[3] += 1
        if myList[3] == checkList[3]:
            checkSecret += 1

def myremove(c):        # 문자가 삭제될 때 호출되는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        if myList[0] == checkList[0]:
            checkSecret -= 1 
        myList[0] -= 1
    elif c == 'C':
        if myList[1] == checkList[1]:
            checkSecret -= 1
        myList[1] -= 1
    elif c == 'G':
        if myList[2] == checkList[2]:
            checkSecret -= 1
        myList[2] -= 1
    elif c == 'T':
        if myList[3] == checkList[3]:
            checkSecret -= 1
        myList[3] -= 1

S, P = map(int, input().split())
Result = 0          # 최종 유효한 비밀번호 개수
A = list(input())
checkList = list(map(int, input().split()))

for i in range(4):          # {'A','C','G','T'} 중 최소 개수가 0개 이면 무조건 조건을 만족하므로 checkSecret에 1 더해줌
    if checkList[i] == 0:
        checkSecret += 1

for i in range(P):          # 윈도우 크기만큼 앞에서부터 먼저 탐색
    myadd(A[i])
if checkSecret == 4:    # 만약 체크리스트 결과를 만족하면 최종 개수 +1
    Result += 1

for i in range(P, S):       # 윈도우를 오른쪽으로 이동 시키며 i는 추가 하는 문자열 j는 삭제하는 문자열  
    j = i - P
    myadd(A[i])
    myremove(A[j])
    if checkSecret == 4:
        Result += 1

print(Result)


문제 10

최솟값 찾기 1 ( 백준 플레티넘 5 / 11003번 )

이 문제의 가장 어려운 점은 슬라이딩 윈도우 크기만큼 계속 정렬을 하게 된다면 O(nlogn)의 시간 복잡도를 가진다. N과 L의 최대 범위가 5,000,000이므로 이 문제에서는 정렬을 사용할 수 없다.
다시 말하면 O(n)의 시간 복잡도로 해결해야 한다. 따라서 슬라이딩 윈도우를 '덱'으로 구현하면 정렬 효과를 볼 수 있다.

덱(deque)은 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 왼쪽에서는 appendleft()와 popleft() 함수를 사용해 삽입, 삭제가 가능하고 오른쪽에서는 append(), pop() 함수로 삽입, 삭제가 가능하다.

메인 아이디어 2개는 다음과 같다.

    1. 나보다 큰 데이터는 삭제하기
    1. 슬라이딩 윈도우 크기를 벗어난 데이터는 삭제하기
from collections import deque
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
mydeque = deque();
now = list(map(int, input().split()))

for i in range(N):
    # 아이디어 1.나보다 큰 데이터 삭제하기
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    mydeque.append((now[i], i))
    # 아이디어 2.슬라이딩 윈도우 벗어난 데이터 삭제
    if mydeque[0][1] <= i - L:      # 윈도우 범위를 벗어나면
        mydeque.popleft()
    print(mydeque[0][0], end=' ')


03-5. 스택과 큐

문제 11

스택으로 수열 만들기 ( 백준 실버 3 / 1874번 )

이 문제는 먼저 문제 이해를 해야한다. 입력한 수열 모양처럼 스택을 이용하여 답을 구해야 한다.

  1. 현재 수열 값 >= 자연수
  • 현재 수열 값이 1부터 입력되는 자연수 보다 작으면 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push(append)한다.
  • 수열 값과 입력된 자연수 값이 같아 지면 수열을 출력하기 위해 1회 pop 한다.
  • 예를 들어 현재 수열 값이 4면 스택에는 1,2,3,4를 push(append)하고 마지막에 4를 얻기 위해 1회만 pop 하여 4를 출력한 뒤 조건문을 빠져나온다. 다음 입력될 자연수는 1이 커진 5가 될 것이다.
  1. 현재 수열 값 < 자연수
  • 현재 수열 값보다 자연수가 크면 pop으로 스택에 있는 값을 꺼낸다.
  • 꺼낸 값이 현재 수열 값이 아니라면 수열을 제대로 표현할 수 없으므로 "NO"를 출력한 후 문제를 끝낸다.
  • 꺼낸 값이 현재 수열 값과 같다면 그대로 조건문을 빠져나온다.
import sys
input = sys.stdin.readline  # 백준에서 없이 제출하니 시간초과가 나서 붙임

N = int(input())
A = [int(input()) for _ in range(N)]    # 수열 리스트 채우기

stack = []  # 스택
num = 1     # 자연수 1부터 시작
result = True
answer = ""

for i in range(N):
    now_num = A[i]
    if now_num >= num:
        while now_num >= num:    # 현재 수열값 >= 오름차순 자연수: 값이 같아질 때까지 append() 수행
            stack.append(num)
            num += 1
            answer += "+\n"
        stack.pop()
        answer += "-\n"
    else:       # 현재 수열값 < 자연수 : pop()을 수행해 수열 원소를 꺼냄
        n = stack.pop()
        if n > now_num:     # 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열을 출력할 수 없다.
            print("NO")
            result = False
            break
        else:
            answer += "-\n"

if result:
    print(answer)


문제 12

오큰수 구하기 ( 백준 골드 4 / 17298번 )

이 문제에서 오큰수는 오른쪽에 있으면서 현재 숫자보다 큰 수 중 가장 왼쪽에 있는 수를 의미한다. 이 문제를 반복문으로 오큰수를 찾으면 N의 최대 크기가 1,000,000이기 때문에 제한 시간을 초과하게 된다.
따라서 스택에 다음 아이디어를 추가해서 풀어야 한다.

핵심 아이디어

  • 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
  • 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다.

문제 푸는 순서는 다음과 같다.

  1. 스택이 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장합니다. pop은 조건을 만족하는 동안 계속 반복합니다. 과정 1을 마치면 과정 2로 넘어갑니다.
  2. 현재 인덱스를 스택에 push(append)하고 다음 인덱스로 넘어갑니다.
  3. 과정 1~2를 수열 길이만큼 반복한 다음 현재 스택에 남아 있는 인덱스에 -1을 저장합니다.
import sys
input = sys.stdin.readline

N = int(input())
answer = [0] * N
A = list(map(int, input().split()))
Stack =[]
result = ""

for i in range(N):
    # 스택이 비어 있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우
    while Stack and A[Stack[-1]] < A[i]:
        answer[Stack.pop()] = A[i]
    Stack.append(i)     # 스택이 비어 있거나 top인덱스가 더 작은 경우에 추가

while Stack:    # 반복문 다 돌고 왔는데 스택에 남아 있는 경우
    answer[Stack.pop()] = -1

for i in range(N):
    sys.stdout.write(str(answer[i]) + " ")


문제 13

카드 게임 ( 백준 실버 4 / 2164번 )

이 문제는 큐를 이용하여 가장 위에 있는 카드를 가장 아래에 있는 카드 밑으로 옮기며 마지막 한장이 남을 때까지 진행한다.

  1. popleft를 사용하여 맨 위의 카드를 버린다.
  2. 과정 1에 이어서 popleft하여 맨 위 카드를 뽑은 후 append하여 맨 아래로 보낸다.
  3. 큐에 하나만 남을 시 까지 반복한다.
import sys
input = sys.stdin.readline
from collections import deque   # 덱을 사용하는 라이브러리 가져오기

N = int(input())
myQueue = deque()

for i in range(1, N+1):     # 덱에 1부터 추가
    myQueue.append(i)

while len(myQueue) > 1:     # 내 덱에 하나가 남을 때까지 반복
    myQueue.popleft()       # 맨 아래 카드를 뽑기 위해 popleft
    myQueue.append(myQueue.popleft())       # 그 다음 아래 카드를 뽑고 맨 위로 추가

print(myQueue.pop())    # 한장이 남았을 때 추출


문제 14

절댓값 힙 구현하기 ( 백준 실버 1 / 11286번 )

N의 최대 범위가 100,000으로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다. 새로 입력을 할 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 풀어야 한다. 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다. 유의할 점은 절댓값이 같을 때는 음수를 우선으로 출력해야 한다.

문제 푸는 순서

  1. x=0일 때
    큐가 비어 있을 떄는 0을 출력하고 비어 있지 않을 때는 절댓값이 최소인 값을 출력한다. 단, 절댓값이 같다면 음수를 우선하여 출력한다.
  2. x=1일 때
    put으로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬한다.

새로 알게 된 사실

print()와 sys.stdout.write()의 차이

from queue import PriorityQueue
import sys
input = sys.stdin.readline
print = sys.stdout.write        

N = int(input())
myQueue = PriorityQueue()

for i in range(N):
    request = int(input())
    if request == 0:
        if myQueue.empty():
            print('0\n')
        else:
            temp = myQueue.get()        # 우선순위 큐의 값 삭제해서 temp변수에 넣음
            print(str(temp[1])+'\n')    # temp변수에 (x,y) 형태니까 y값인 1번 출력
    else:
        myQueue.put((abs(request), request)) # 절댓값을 기준으로 정렬하고 같으면 음수 우선 정렬하도록 구성

파이썬에서는 데이터의 순서가 정렬의 우선순위가 된다.

위 코드 마지막의 myQueue.put((abs(request), request)) 코드의 정렬 순서가 1.절댓값, 2.음수인 것은 파이썬에서는 우선순위 큐에 데이터를 추가할 때 순서가 정렬 우선순위의 기준이 되기 때문이다. abs(request)가 절댓값을 나타내므로 먼저 절댓값을 기준으로 정렬한다. 그다음으로 request를 기준으로 정렬하므로 절댓값이 같다면 양수인지 음수인지를 비교하여 음수 우선으로 정렬한다.

이상으로 Do it! 알고리즘 코딩테스트 3장. 자료구조 3-4, 3-5 풀이를 마친다.

profile
Cold Ui
안녕하세요. 차니의 개발 블로그 입니다!
이전 포스트

Do it! 알고리즘 코딩테스트 3장. 자료구조 ( 3-2, 3-3 )

다음 포스트

Do it! 알고리즘 코딩테스트 4장. 정렬 ( 4-1, 4-2 , 4-3)

0개의 댓글

관련 채용 정보