그동안 시간이 없어서 블로그를 잠시 쉬었는데 다시 시작해보려 한다.
(사람들이랑 하는 챌린지는 코드업 기초 100제 중 어려운 문제 풀면서 계속했는데 너무 많이 쉽더라... 백준 실버문제도 안 되는 느낌)
오늘 푼 문제는 함께 스터디하는 사람 중 한명이 먼저 푸신 수들의 합 2다.
https://www.acmicpc.net/problem/2003
문제에 대한 간단한 이해
수열이 주어지고 그 수열 안에서 연속적으로 이어지는 부분 수열이 어떤 숫자를 만족하는 경우의 수 구하기입니다.
입출력에 대한 이해
수열의 길이, 만족해야할 숫자, 그리고 수열이 주어집니다.
문제에 대한 세부 이해
1. 주어진 것(입력값)
수열
2. 구하고자 하는 것(출력값)
경우의 수
3. 규칙
중요한 것은 항상 내부에서 이어져 있어야 한다는 것입니다.
- 제약하는 규칙이 있으니 부분 수열안의 모든 숫자를 더해보기 보다는 시간을 줄일 수 있는 방법을 생각해봅니다.
- 부분 수열이 변할 때를 생각해본다면 가장 단순한 방법은 항상 앞이나 뒤가 하나씩 변하는 것입니다.
- 맨 앞에서부터 시작해 M보다 현재의 부분 수열의 합이 작으면 한 개의 숫자 추가, 크면 한 개의 숫자를 감소시킵니다.
구현
- 규칙에 따라서 구현하기 위해 list의 앞 뒤를 정의해줄 front, back의 인덱스와 변했는지 여부를 변수로 만들어줍니다.
- 수열을 다 돌 때까지 반복문을 실행시킵니다.
- 반복문 안은 변했는지 여부를 통해 갱신해주는 단락과, 현재 합계(cur_sum)와 M을 비교해주는 단락으로 나뉩니다.
import sys
from collections import deque
N, M = map(int, (input().split()))
num_list = list(map(int, (input().split())))
front_idx = -1
back_idx = 0
cur_sum = 0
is_front_change = False
is_back_change = True
answer_num = 0
while (back_idx < N) & (front_idx < N):
# 앞을 땡겼는지 뒤를 밀었는지 확인 후 작업
if is_front_change:
# M보다 크면 맨 앞에거 하나 삭제
cur_sum -= num_list[front_idx]
is_front_change = False
if is_back_change:
# M보다 작으면 맨 뒤 하나 추가
cur_sum += num_list[back_idx]
is_back_change = False
# M과 현재 합 값이 어떤 상태인지 판단
if M == cur_sum:
answer_num += 1
front_idx += 1
back_idx += 1
is_front_change = True
is_back_change = True
# M보다 크면 맨 앞에거 하나 삭제
elif M < cur_sum:
front_idx += 1
is_front_change = True
# M보다 작으면 맨 뒤 하나 추가
else:
back_idx += 1
is_back_change = True
print(answer_num)
참고:
https://wayhome25.github.io/python/2017/06/14/time-complexity/
파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그
파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) 14 Jun 2017 | 들어가기 알고리즘 문제를 풀다 보면 시간복잡도를 생각해야 하는 경우가 종종 생긴다. 특히 codility는 문제마다 시간복잡도 기준
wayhome25.github.io
친구가 카드 등록을 도와줬다고 스타벅스 아메리카노를 사줬다...
고마워~
(당근 채팅은 꼭 다른 사람에게 부탁하자.)
'컴퓨터 공학 분야 별 지식 > 백준' 카테고리의 다른 글
BOJ 백준 2559번 문제 <수열> python, 문제 해석 및 풀이 (0) | 2023.02.02 |
---|---|
BOJ 백준 1935번 문제 <후위 표기식> python, 문제 해석 및 풀이 (0) | 2023.01.19 |
BOJ 백준 4949번 문제 <균형잡힌 세상> python, 문제 해석 및 풀이 (0) | 2023.01.18 |
BOJ 백준 18258번 문제 <큐2> python, 문제 해석 및 풀이 (0) | 2023.01.17 |
BOJ 백준 9012번 문제 <괄호> python, 알고리즘 문제 푸는 방법 (0) | 2023.01.16 |