Baekjoon 2217번

Baekjoon 2217번

URL : https://www.acmicpc.net/problem/2217

==============================================

Contents

1. Problem

2. Error & Fail

3. Solution

4. My Code

5. Other's Code

6. Shortest Code

==============================================

배울 것

1. sys가 input보다 무조건 압도적으로 빠르다
2. 개수가 정해졌다면 전체 list를 만드는 것이 생각보다 빠를 수 있다.
3. 함수화를 통해 속도가 개선될 수 있다.

1. Problem

1. N개의 로프가 있으며 각각은 중량이 서로 다를 수도 있다.(주의 -> 2번 확인)
2. k개의 로프를 병렬로 연결했을 때 w 물체를 들어올릴 때의 각 줄의 중량은 w/k만큼 걸리게 된다. 만약 이 중량에 부합하지 않은 로프가 있다면 고려하지 않는다.
3. 물체의 최대 중량을 구해내는 프로그램을 작성하라
4. 모든 로프를 사용할 필요가 없다

2. Error & Fail

주의할 점은 문제 마지막에는 단, 각각의 로프는 한 개씩만 존재한다라고 적혀있어 혼돈이 있을 수 있지만 사실 이 문장은 없어야 올바르다고 개인적으로는 생각한다.
이 문장이 존재하는 것만으로도 큰 문제를 야기할 수 있는데 서로 다른 로프가 우연히 하중이 같을 수 있다는 어불성설로 혼돈을 야기한다.
사실 이 문장은 크게 신경쓰지 않아도 잘 풀리긴해서 상관없을 수도 있으나 너무 짜증나는 문장이다.
결론 : 중복이 가능한 로프가 존재할 수 있다.

또 하나의 주의점은 로프가 0인 경우도 있을 수 있다. 크게 문제되지 않을 수도 있으나 주의는 하자.

3. Solution

첫 입력을 제외한 나머지 입력에서 각 로프들의 하중들을 입력받는다.
우리는 이것을 sort하는 것이 좋은 판단이다
단순한 방법으로 생각하면 sort한 것들 중 하중이 가벼운 앞의 숫자들은 상대적으로 무거운 로프들의 도움을 받아 그 개수만큼 더해 결과 하중을 구할 수 있다.
예로 [3,4,5,7,7,7,8]이라는 7개의 입력을 받았다고 가정하면
상대적으로 가벼운 3은 나머지 6개의 줄의 도움을 받아 3*(1+6) = 21이라는 결과를 얻을 수 있다.
그러나 4의 경우 3은 4의 하중을 견디지 못하므로 제외. 나머지 줄의 도움을 받으면
4*(1+5) = 24의 하중을 견딜 수 있다.
그렇다면 우리는 이런 방식으로 결과값들을 얻고 max를 통해 결과를 얻어낼 수 있을 것이다.

만약 위와 같은 방식을 취하지 않는다면 dict에 key 값에 uniq한 하중의 수를 넣고 value에 그 갯수를 넣는 방식으로 sorting 할 수도 있을 것이다.

4. My Code

1차 - 147B 4164ms

N = int(input())
r = sorted([int(input()) for _ in range(N)])
result = []
for i in range(N):
    result.append(r[i]*(N-i))
print(max(result))

가장 무식하게 하는 방법으로 sort한 list에서 i번째의 값은 i+1의 값보다는 무조건 낮은 값을 가지므로 도움을 받는다
때문에 list[i]*(N-i)의 방식으로 넣은 값들 중 최대값을 찾는다.
이 방법은 짧으며 중복도 감당해내지만 오래 걸린다.

2차 - 288B 4028ms

N = int(input())
r = sorted([int(input()) for _ in range(N)])
uniq=sorted(list(set(r)))
d = {i:0 for i in uniq}
for i in range(N):
    d[r[i]] += 1
    
result = []
num = 0 
for i in range(len(d)):
    result.append(uniq[i] * (N-num))
    num += d[uniq[i]]
print(max(result))

3. Solution에서 마지막으로 이야기한 dict를 통한 uniq 값을 넣는 방식이다.
실용적으로 보이나 속도차이에서는 조금 빠를 뿐 코드길이가 1차에 비해 2배나 늘었다.

왜 이렇게 갑자기 속도가 늘었던 것인지에 대해서 다른 사람의 코드를 보며 학습하자

5. Other's Code

rapaeljin 256B 92ms - 내가 돌렸을 때는 96ms

import sys
In = sys.stdin.readline

def main():
    n = int(In())
    rope = [0] * 10001
    for _ in range(n):
        rope[int(In())] += 1
    m, s = 0, 0
    for x in range(10000,-1,-1):
        s += rope[x]
        m = max(m, x * s)
    print(m)
main()

가장 빠른 코드이다. 우리가 여기서 배울 것이 많다.
1.우선 이 방법은 우리가 받을 수 있는 rope 최대 개수 100,000개로 알기에 쓸 수 있는 방법이다.
rope의 모든 하중에 따른 리스트를 따로만들고 입력받을 때마다 바로 그 값을 하나씩 증가시키는 방법이다.
key값을 찾아 value를 뽑아 그것으로 연산하는 자체보다 한번에 list를 빨리 돌리는 것이 효율적이다라는 것을 보여준다.

2. 그럼에도 다른 어떤 방식보다도 빠르다. 그것의 비결은 sys.stdin.readline에 있다.
위 코드를 input으로 바꿔서 돌려보면 4196ms가 나온다. 아니! 이럴수가.
내 코드 또한 바꿔서 넣어보면 속도가 바뀐다
1차 - 148ms

import sys
N = int(sys.stdin.readline())
r = sorted([int(sys.stdin.readline()) for _ in range(N)])
result = []
for i in range(N):
    result.append(r[i]*(N-i))
print(max(result))

2차 - 152ms

import sys
N = int(sys.stdin.readline())
r = sorted([int(sys.stdin.readline()) for _ in range(N)])
uniq=sorted(list(set(r)))

import collections
counter = collections.Counter(r)
d = dict(counter)

result = []
num = 0 
for i in range(len(d)):
    result.append(uniq[i] * (N-num))
    num += d[uniq[i]]
print(max(result))

실제로 속도가 많은 것이 차이가 나는데 여기서는 유독 심했다.
사실 Baekjoon에서만 이런 것인지는 모르겠지만 Baekjoon은 sys.stdin.readline의 속도가 무조건 빠르다.

3. 위 두가지를 해도 충분히 빠른데 더 빠르게 하는 방법이 이 분의 코드에는 숨겨져 있다.
그것은 함수로 빼내서 넣는 방식이 속도가 빠르다는 것이다.
나의 1차 코드를 이 분의 방식처럼 돌려보았다.

import sys
In = sys.stdin.readline
def main():
    N = int(In())
    r = sorted([int(In()) for _ in range(N)])
    result = []
    for i in range(N):
        result.append(r[i]*(N-i))
    print(max(result))
main()

무려 속도가 128ms였다.
4164ms의 속도를 가지던 기존 코드가 sys를 통해 148ms로 함수화를 통해 128ms이 나온 것이다.

여기서 주의할 점은 In을 밖에서 ()를 제외한체로 선언한 후 함수 안에서는 따로 변수를 불러오는 방식을 채택해야한다는 것이다
만약 함수화를 할 때 In을 신경쓰지 않고 main 함수에 다 넣는다면 속도가 조금 느리게 나온다.

왜 그런지는 모르겠다.... 짧은 실력의 최후랄까... ㅋ
그래도 배워가자

6. Shortest Code

시간에서 너무 많은 소모가 크므로 넘기겠다.