(인프런) 파이썬 알고리즘 문제1-10 "점수 계산"

Score Calculate

[시간복잡도]

O(n)

 

: 해당 코드의 시간복잡도는 O(n)으로 추측된다. 그 이유는 for문의 사용횟수가 1번이라는점이 가장 큰 이유이다.

해당 코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이기 때문이다.

[공간복잡도]

O(1)

 

: 해당 코드에서 고정공간(score, count) / 가변공간(n_list[i]) 정도이기 때문에 O(1)에 해당한다. 

 

Problem

OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다.

여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기 로 하였다.

1번 문제가 맞는 경우에는 1점으로 계산한다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다.

또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, ..., K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계산한다.

예를 들어, 아래와 같이 10 개의 OX 문제에서 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경우에는 0으로 표시하였을 때, 점수 계산은 아래 표와 같이 계산되어, 총 점수는 1+1+2+3+1+2=10 점이다.

 

1 0 1 1 1 0 0 1 1 0

 

채점 1 0 1 1 1 0 0 1 1 0

점수 1 0 1 2 3 0 0 1 2 0

 

시험문제의 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하시오.

 

▣ 입력설명

 

첫째 줄에 문제의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 N개 문제의 채점 결과를 나 타내는 0 혹은 1이 빈 칸을 사이에 두고 주어진다. 0은 문제의 답이 틀린 경우이고, 1은 문제의 답이 맞는 경우이다.

 

▣ 출력설명

 

첫째 줄에 입력에서 주어진 채점 결과에 대하여 가산점을 고려한 총 점수를 출력한다.

 

▣ 입력예제

 

10

1 0 1 1 1 0 0 1 1 0

 

▣ 출력예제

 

10

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
# 문제 갯수
n=int(input())
n_list=list(map(int,input().split()))
 
# 총 점수를 담을 변수 설정
score=0
count=0
 
for i in range(n):
    # 정답을 맞춘 경우 : 1
    if n_list[i]==1:
        # count가 1이상이라면, 이전 값이 정답이었다.
        if count>=1:
            count+=1
            score+=count
        # 이번 값은 정답이었지만, 이전 값은 정답이 아니었다.
        else:
            count+=1
            score+=1
 
    # 정답을 못 맞춘 경우 : 0
    else:
        count=0
        score+=0
 
 
print(score)

 

• score , count 변수를 0으로 선언한다. (score 변수는, 총 점수를 계산하기 위한 변수이고 count 변수는 연속해서 정답일 때 횟수를 count 하기 위해서 선언한 변수이다.)
• for 문을 돌려서 n_list[i] 값이 1이라면, 정답이기 때문에 if 문을 타고  n_list[i] 값이 0이라면, 오답이기 때문에 count=0, score+=0 을 해준다.
• 만약 정답 if 문을 들어간다면, if count >=1 을 통해서 해당 정답이 첫번째 정답인지 두번째 이상의 정답인지 나눈다.

ex)  [1, 0, 0, 1, 1, 1, 0, 0, 1, 1]

 

(계속된 정답이었을 경우) count에 1을 더하고 score에 count값을 더한다.

# count가 1이상이라면, 이전 값이 정답이었다.
        if count>=1:
            count+=1
            score+=count

-> 해당 배열의 4번째 인덱스에 해당하는 경우이다.

 

(첫번째 정답이었을 경우) count에 1을 더하고 score에 1을 더한다.

# 이번 값은 정답이었지만, 이전 값은 정답이 아니었다.
        else:
            count+=1
            score+=1

-> 해당 배열의 3번째 인덱스에 해당하는 경우이다.

 

💯 Solution ②

: Tutor advice

 

import sys
sys.stdin=open("input.txt","rt")
n=int(input())
a=list(map(int,input().split()))
 
sum=0
cnt=0
 
for x in a:
    if x==1:
        cnt+=1
        sum+=cnt
    else:
        cnt=0
        
print(sum)

 

: 내가 작성한 코드와 똑같지만, 조금 더 간단하게 작성한 코드이다.

 

📚 참고