[백준 1744] 수 묶기 (Python)

www.acmicpc.net/problem/1744

1744번: 수 묶기

 

문제풀이

N, arr : 입력값

minus_cnt, plus_cnt, zero_cnt : 음수, 양수, 0 개수

 

그리디 알고리즘 문제인데, 극강의 하드코딩으로 해결하였다... 분명히 더 효율적인 방법이 많이 존재할 것이다. 예외 테스트케이스를 생각하면서 짜다보니 코드가 길어졌고, 결국 하드코딩이 되어버렸다...ㅠㅠ

 

1. 음수, 양수, 0 개수 세주기

 

2. 음수 계산하기

- 음수 개수가 짝수일 경우 짝지어서 곱해주기

- 음수 개수가 홀수일 경우, 가장 큰 음수 제외하고 쌍 만들어서 곱해주기

- 위에서 남은 하나의 음수에 대해, arr 에서 0이 존재한다면 해당 음수와 0을 짝지어 주는것이 더 큰 경우이므로 아무것도 더하지 않음

- 0이 존재하지 않는다면 가장 큰 음수 더하기

 

3. 양수 계산하기

- 가장 큰 양의 정수부터 짝지어서 곱해보기

- 원소가 1이면 그냥 더하는 것이 더 큰 경우

- 음수에서 계산했던 것과 마찬가지로 짝지어서 곱하기, 짝이 없는 원소가 있을 경우 그냥 더해주기

 

코드 주석을 보면 조금 더 이해가 잘 될것 같다...

 

코드

if __name__ == '__main__':
    N = int(input())
    arr = []
    minus_cnt, plus_cnt = 0, 0
    zero_cnt = 0
    for _ in range(N):
        n = int(input())
        if n < 0: minus_cnt += 1
        elif n > 0: plus_cnt += 1
        else: zero_cnt += 1
        arr.append(n)
    arr.sort()
    ans = 0
    # minus 개수가 짝수인 경우
    if minus_cnt % 2 == 0:
        for i in range(0, minus_cnt, 2):
            ans += (arr[i] * arr[i + 1])
    # minus 개수가 홀수인 경우
    else:
        for i in range(0, minus_cnt - 1, 2):
            ans += (arr[i] * arr[i + 1])
        # 0이 존재하면 0을 곱한것이 더 크므로 그냥 넘어간다. ex) -3*0 = 0
        if not zero_cnt: # 0이 존재하지 않는다면 가장 큰 음수 더해주기
            ans += arr[minus_cnt - 1]
    # 0 개수 줄이기 => 0이 존재하든 안하든 양수가 시작하는 인덱스를 알기 위해 zero_cnt 에서 1 빼줌
    zero_cnt -= 1
    idx = len(arr) - 1
    # minus_cnt : 양수 시작 인덱스
    minus_cnt += (zero_cnt + 1)
    # 가장 큰 값부터 곱해보기
    while idx >= minus_cnt:
        # 원소가 0이면 패스
        if not arr[idx]:
            idx -= 1
            continue
        # 원소가 1이면 그냥 더해주기
        if arr[idx] == 1:
            ans += 1
            idx -= 1
            continue
        # 원소가 양수 하나 남았을 경우 그냥 더해주고 종료
        if idx == minus_cnt:
            ans += arr[idx]
            break
        # 현재 원소에서 곱할 수가 1이 아니면 곱해주기
        if arr[idx - 1] != 1:
            ans += (arr[idx] * arr[idx - 1])
        # 곱할 수가 1이라면 그냥 더해주기, 더하는 것이 더 큰 경우이다. => 더하였기 때문에 idx 는 1만 감소
        else:
            ans += arr[idx]
            idx -= 1
            continue
        # 곱하였으면 idx 2 감소
        idx -= 2
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!