[백준] No.15954_인형들 02
길었다... 모듈 문제에, 인덱스 문제에, 알고리즘 틀리고, 시간 초과까지. 정답도 나로서는 정석으로 푼 느낌이 아니다.
시간 초과를 해결하려면 시간 복잡도를 줄여야 하는데, 반복문을 줄일 방법이 도저히 떠오르지 않아 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으로 재도전할 거다.
강해져서 돌아오마 문제.