PS/구현

[백준] No.15954_인형들 02

_빌런 2022. 3. 4. 16:17

 길었다... 모듈 문제에, 인덱스 문제에, 알고리즘 틀리고, 시간 초과까지. 정답도 나로서는 정석으로 푼 느낌이 아니다.

시간 초과를 해결하려면 시간 복잡도를 줄여야 하는데, 반복문을 줄일 방법이 도저히 떠오르지 않아 pypy로 제출했다.

뭐랄까... 출항해서 난항이란 난항을 다 겪고 도착한 곳이 선착장이 아니라 후미진 부둣가 같은 느낌?

어찌어찌 도착은 했으니까 지나온 길을 되새겨보자. 그래야 다음 운항에서는 길을 잃지 않을 테니까.

 

import math


def var(argv):
    var = 0
    averge = sum(argv) / len(argv)
    
    for arg in argv:
        var += (arg - averge) ** 2
    var = var / len(argv)
    
    return var
    

N, K = map(int, input().split())
goods = list(map(int, input().split()))
std = []

for i in range(N - K + 1):
    tmp = []
    
    tmp.append(goods[i])
    tmp.append(goods[i + 1])
    tmp.append(goods[i + 2])
    
    std.append(abs(math.sqrt(var(tmp))))
    # sqrt가 음의 제곱근을 출력해서 오류가 났을까봐 abs로 확인
    
print((min(std)))

 우선 저번에 작성했었던 IndexError. 혹시 sqrt 함수가 음의 제곱근을 출력해서 리스트 값을 연산하던 도중 오류가 생긴 건 아닌가 하고 abs(절댓값)를 넣었었다.

아주 가관이다... 우선 sqrt 함수는 음의 제곱근을 출력하지 않을뿐더러 abs는 '정수'의 절댓값을 연산해주는 함수다.

실수는 fabs()를 써야 한다... 저 생각이 들었을 당시는 정말 잘 찾았다고 생각이 들었는데 다시 보니 부끄럽다.

 

 이 함수에서 IndexError가 나타나는 이유는 아주 단순했다. 술 마시니까 보였음

K가 3일 때만 돌아가는 코드다. tmp.append(goods [i]) ~ tmp.append(goods [i+2])니까 당연하다.

K가 4가 되거나 5가 되거나 하는 식의 입력이 변형된다면 값이 나오지 않는다. 그래서 고쳤다.

 

import math


def var(argv):
    var = 0
    averge = sum(argv) / len(argv)
    
    for arg in argv:
        var += (arg - averge) ** 2
    var = var / len(argv)
    
    return var
    

N, K = map(int, input().split())
goods = list(map(int, input().split()))
std = []

for i in range(N - K + 1):
    tmp = []
    
    for index in range(K):
        tmp.append(goods[i+index])
    
    std.append(math.sqrt(var(tmp)))

print((min(std)))

 그리고 틀렸다.

대체 왜??? 라는 의문을 갖고 몇 시간씩 고민을 하고 입력을 여러 가지 바꿔가면서 깨달았다. 내가 문제를 잘못 이해했다는 것을.

백준 사이트에서 인형을 선택하는 방법에는 아래와 같은 2가지 조건이 있었다.

  • 먼저 비슷한 인형이 가깝게 위치하도록 서로 다른 N개의 인형을 종류당 한 개씩 일렬로 배치한다.
  • 그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여 그들을 같은 곳에 배치한다.

'K개 이상의 연속된'. 그러니까 입력이 1 2 3 4 5일 때 연산해야 하는 값이 1 2 3 / 2 3 4 / 3 4 5가 아니라

1 2 3 /  1 2 3 4 /  1 2 3 4 5 /  2 3 4 /  2 3 4 5 /  3 4 5를 연산해야 하는 거다. 이러니까 틀렸지.

 

import math


def var(argv):
    var = 0
    averge = sum(argv) / len(argv)
    
    for arg in argv:
        var += (arg - averge) ** 2
    var = var / len(argv)
    
    return var
    

N, K = map(int, input().split())
goods = list(map(int, input().split()))
std = []

for i in range(N - K + 1):
    tmp = []
    
    for j in range(N - K + 1 - i):
        tmp = goods[i : i+j+K]
        std.append(var(tmp))

print(math.sqrt((min(std))))

  고쳤는데 시간 초과로 틀렸다고 나왔다. 여기서부터는 이제 알고리즘이 틀렸다기보다는 시간의 효율성 문제다.

시간 복잡도를 줄여서 얼마나 빠르고 효율적인 코드를 완성시키느냐의 문제이기 때문이다.

이때부터 몇 번 제출해봤는데 이게 불필요한 코드를 줄이는 데에 오히려 도움이 되었다. 결국 완성은 pypy가 다 했지만...

 

import math
import sys
input = sys.stdin.readline


def var(argv):
    var = 0
    averge = sum(argv) / len(argv)
    
    for arg in argv:
        var += (arg - averge) ** 2
        
    return var / len(argv)


N, K = map(int, input().split())
goods = list(map(int, input().split()))
answer = []

tmp = []
for i in range(N - K + 1):
    for j in range(N - K + 1 - i):
        tmp = goods[i : i+j+K]
        answer.append(var(tmp))

print(math.sqrt((min(answer))))

 그렇게 완성한 코드다. sys를 호출해서 input() 대신에 sys.stdin.readline()을 쓰면 입력 처리가 빨라진다는 것은 알고 있었는데, 길어서 안 쓰고 있었다.

그걸 input = sys.stdin.readline으로 해결할 수 있다는 것을 이번에 돌아다니면서 알았다. 애용해야지.

아직도 한~~~참 공부해야 한다는 걸 절실히 깨닫게 해준 문제. 다음에는 python으로 재도전할 거다.

강해져서 돌아오마 문제.