글 읽기 - 논리는 같은 두 가지 코드에서 Pass/Fail이 갈려요

(追記) (追記ここまで)

논리는 같은 두 가지 코드에서 Pass/Fail이 갈려요

1208번 - 부분수열의 합 2

yeramii 1년 전 0

증가하는 inc 배열과 감소하는 dec 배열을 만들어서, two pointer로 문제를 풀었는데요.

inc 배열의 값과 dec 배열의 값의 합이 S일 때의 갯수를 구하는 부분을 2가지로 구현해봤습니다.

1) while문으로 구현한 경우 Pass였고,

2) for & if 문으로 구현한 경우 Fail (시간 초과) 였는데요.

두 가지가 시간복잡도 측면에서 차이가 없을 것으로 보이는데, 아닌걸까요?

from itertools import combinations
N, S = map(int, input().split())
nums = list(map(int, input().split()))
inc = []
dec = []
tmp = nums[:len(nums)//2]
for i in range(len(tmp)+1):
 for comb in combinations(tmp, i):
 inc.append(sum(comb))
tmp = nums[len(nums)//2:]
for i in range(len(tmp)+1):
 for comb in combinations(tmp, i):
 dec.append(sum(comb))
inc.sort()
dec.sort(reverse=True)
i, d = 0, 0
ans = 0
while i < len(inc) and d < len(dec):
 if inc[i] + dec[d] > S:
 d += 1
 elif inc[i] + dec[d] < S:
 i += 1
 else:
 # 1) Pass
 ii, dd = i, d
 while ii < len(inc) and inc[ii] == inc[i]:
 ii += 1
 while dd < len(dec) and dec[dd] == dec[d]:
 dd += 1
 ans += (ii-i) * (dd-d)
 i, d = ii, dd
 
 # 2) Fail (time over)
 # cnt_i, cnt_d = 0, 0
 # for ii in range(i, len(inc)):
 # if inc[ii] == inc[i]:
 # cnt_i += 1
 # else:
 # i = ii
 # break
 # for dd in range(d, len(dec)):
 # if dec[dd] == dec[d]:
 # cnt_d += 1
 # else:
 # d = dd
 # break
 # ans += cnt_i * cnt_d
print(ans-1 if not S else ans)

lidersy961 10달 전 0

for 문의 경우, range() 객체를 계속해서 생성해주기 때문에 성능 차이가 발생하는 것 같습니다.

while문의 경우, 인덱스를 지정해주는 변수만 이용하면 되지만 for문은 range() 객체 생성 후 반복문을 순회하기 때문에 여기서 시간 차이가 나는 것 같네요.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC