[2학기 4주차] 평균은 넘겠지, 최솟값 찾기

문제

대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다.

입력

첫째 줄에는 테스트 케이스의 개수 C가 주어진다.

둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 정답과 출력값의 절대/상대 오차는 10-3이하이면 정답이다.

---

C = int(input())

for _ in range(C):
    data = list(map(int, input().split()))
    N = data[0]
    scores = data[1:]
    avg = sum(scores) / N

    count = 0
    for s in scores:
        if s > avg:
            count += 1

    rate = (count / N) * 100
    print(f"{rate:.3f}%")

 

1. 테스트 케이스의 개수 C를 입력받아 정수형태로 저장한다.

2. list를 저장할 변수 data를 만들고 입력받은 것을 공백을 기준으로 나누고 정수형으로 변환하여 list에 저장한다.

3. data의 0번째 인덱스를 학생의 수 N으로 지정하고 1번째인덱스부터 끝까지는 scores라고 지정한다.

4. 평균은 scores의 총합을 학생 수 N으로 나눈 것이다.

5. 평균을 넘은 학생 수를 저장할 변수 count을 0으로 초기화한다.

6. 만일 점수 s가 평균보다 크면 count가 1 증가한다.

7. 평균을 넘는 학생들의 비율을 저장할 변수 rate는 count를 학생 수 N으로 나누고 100을 곱한 수이다.

8. 반올림하여 소수점 이하 3자리까지 표시한 rate를 출력한다. 

 

+) f"..." : f-string(포매팅 문자열) ; 문자열 안에 { }를 써서 변수나 표현식의 값을 바로 넣는 방법

 

+) {rate: .3f} 에서

rate → 출력할 변수 이름

: → 포맷 지정 시작

.3f → 실수 형식으로 소수점 이하 3자리까지 표시하며 자동으로 반올림 됨

 

 

---

 

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

---

import sys
from collections import deque
input = sys.stdin.readline
write = sys.stdout.write

N, L = map(int, input().split())
A = list(map(int, input().split()))

dq = deque()

for i in range(N):
    # 덱의 뒤에서 A[i]보다 큰 값 제거
    while dq and A[dq[-1]] > A[i]:
        dq.pop()

    dq.append(i)

    # 윈도우 범위 벗어난 인덱스 제거
    if dq[0] <= i - L:
        dq.popleft()

    # 현재 최소값 출력 (공백으로 구분)
    write(str(A[dq[0]]) + ' ')

 

1. 표준입출력 긴 스트림 처리용 ( sys.stdin.readline , sys.stdout.write를 쓰려면 필요 )

2. from collections import deque는 양쪽에서 O(1){시간복잡도, 입력크기에 상관없이 일정 시간}로 push/pop 가능한

덱(deque)을 쓰기 위한것. 슬라이딩 윈도우의

최소를 유지할 때 최적

3. input()보다 훨씬 빠른 입력 함수로 대체 ( 끝에 \n이 붙어 필요할 때 .strip()을 사용해야하지만 여기서는 split()으로 바로

처리해서 괜찮음)

4. print()보다 빠른 출력 함수로 대체. 매번 호출해도 오버헤드가 작아 대량 출력 시 필수적

5. 입력받은 것을 공백을 기준으로 나눠 int형으로 변환해 각각 N(원소 수)과 L(윈도우 크기)에 저장

6. N개의 정수들을 한번에 리스트로 읽음

7. 인덱스를 저장할 빈 덱을 초기화. (덱에는 값이 아니라 인덱스를 저장하는게 핵심-윈도우 범위 체크를 쉽게 하기 위해)

8. 덱의 맨 뒤부터 현재 값 A[i]보다 큰 값들을 전부 제거 (뒤의 큰 값들은 앞으로 나올 A[i]보다 항상 크므로 A[i]가 앞에 있으면

그 큰 값은 최소 후보가 될 수 없음)

9. 현재 인덱스 i를 덱 뒤에 추가 (인덱스는 항상 증가하므로 덱 내에서 인덱스는 오름차순 유지)

10. 현재 윈도우는 [i-L+1, ... , i]이므로 인덱스가 i-L 이하면 윈도우에서 벗어난 것 (덱의 맨 앞이 가장 작은 인덱스 원소이므로 윈도우를

벗어나면 앞에서 하나 제거)

11. 덱의 맨 앞 dq[0]는 현재 윈도우의 최소값의 인덱스이므로 A[dq[0]]를 출력 + 공백으로 구분해서 바로 출력

 

 

+) deque는 double-ended queue(양쪽 끝에서 뽑고 넣을 수 있는 큐)의 줄임말

슬라이딩 윈도우: 연속된 일정 길이의 구간(Window)를 만들어서 배열이나 문자열 같은 자료구조를 한칸씩 이동시키며 처리하는 기법

 

+) print()보다 이 문제에서는 sys.stdout.write()쓰는게 효율적 (속도, 메모리 측면에서)