99클럽 코테 스터디 10일차 TIL | 백준 1253. 좋다 반례 (Python)

문제 링크 : 백준 1253. 좋다  /  정답 코드 바로가기 

 

주어진 N개의 수 중에서 '좋은수'를 찾아야한다.

좋은수란 다른 두 수의 합으로 나타낼 수 있는 수를 의미한다.

값이 같아도 숫자의 위치가 다르면 다른 수로 취급한다.

 

[1, 1, 2, 2, 2]

예를 들어 위 케이스에서, 각 2는 모두 다른 수이므로 결과는 3이 되어야한다.

 

숫자 배열의 길이는 1 ~ 2,000 이며, 각 수의 범위는 -1,000,000,000 ~ 1,000,000,000 이다.

 

예시 케이스

Case 1 ) input : [-1, 0, 1] / output : 1

 

-1 은 좋은 수가 아니다. -1을 제외한 [0, 1] 로는 -1을 만들 수 없다.

0 은 좋은수이다. (-1) + (1) 을 더해서 만들 수 있다.

1 은 좋은 수가 아니다. [-1, 0] 으로는 1을 만들 수 없다.

 

Case 2 ) [-3, 0, 0, 2] / output : 0

 

여기에 좋은수는 한개도 없다.

 

Case 3) [0, 0, 0, 2, 2] / output : 5

 

0은 좋은 수이다. 자기 자신을 제외한 2개의 0으로 표현할 수 있기 때문이다.

2는 좋은수이다. 2가 2개라서 (2 + 0) 으로 표현할 수 있기 때문이다. 

 

구현 아이디어

인덱스가 겹치지 않게 관리하기 위해 포인터를 사용할 수도 있었지만,

숫자의 합을 찾는 문제이기에 O(1) 시간으로 나머지 숫자를 찾아낼 수 있는 HashMap이 더 시간복잡도에서 유리하겠다고 판단했다.

 

key를 주어진 숫자, value를 숫자 갯수로 하는 HashMap을 만들고 이를 연산에 포함시키기로했다.

 

처음 고안한 로직은 아래와 같다.

def is_good(num, num_cnt_map) -> bool:
    for n in num_cnt_map.keys(): # key는 정렬된 상태임
    	x = num - n
        if x in num_cnt_map:
            return True # ex) num = 6, n = 2 일때, x = 4가 배열 안에 있으면 6은 좋은수이다.
    return False

 

5가 좋은수인지 판단하기 위해, 배열 속 모든 수에 대해 합해서 5를 만들 수 있는 수가 있는지 확인하는 것이다.

 

하지만 이 로직은 두가지 문제가 있었다.

 

1. num = 6, n = 3 같은 경우에 3이 무조건 2개 있어야하는데 이를 처리하지 못한다.

2. num = 0, n = 0 의 경우는 0이 무조건 3개 있어야하는데 이를 처리하려면 분기가 복잡해진다.

 

num이랑 n에 0이 있는 케이스를 아래처럼 2중, 3중 if문으로 나눠서 처리해보다가 계속 처참한 실패를 겪고, 문제를 다시 한번 생각해봤다.

def is_good(num, num_cnt_map) -> bool:
    # key는 정렬된 상태
    for n in num_cnt_map.keys():
        x = num - n
        if n == 0 or x == 0:
            if num == 0:
                if num_cnt_map[0] >= 3:
                    return True
            else:
                if num_cnt_map[num] >= 2:
                    return True
        elif n == x:
            if num_cnt_map[n] >= 2:
                return True
        else:
            if x in num_cnt_map:
                return True
    return False

 

위 로직의 문제점은 x만 확인하면 된다고 착각한 것이다.

num, n의 값에 따라 검증 기준을 바꿀 것이 아니라, num이랑 n도 그냥 확인을 해주면 된다.

 

(num = 2, n = 0, x = 0) 를 만들 수 있는지 확인하는 과정을 아래와 같이 바꾼다는 이야기이다.

- n = 0 이므로, 이번 케이스에서는 num = 0 인지 확인하고 num != 0 이므로 x를 어쩌고 저쩌고... (X)

- 2가 1개 이상, 0이 2개 이상 있는지 확인한다 (O)

 

단순화한 로직은 아래와 같다.

def is_good(num, num_cnt_map) -> bool:
	# key값을 정렬할 필요도 없다.
    for n in num_cnt_map.keys():
        x = num - n

        # 1. (n, x, num)이 몇개나 주어졌는지 정보를 불러온다.
        pair_cnt = dict()
        for k in [n, x, num]:
            pair_cnt[k] = num_cnt_map.get(k, 0)
        
        # 2. (n, x, num) 갯수가 충분한지 하나하나 세본다.
        pair_cnt[n] -= 1
        pair_cnt[x] -= 1
        pair_cnt[num] -= 1
        
        # 3. 모든 숫자가 충분히 존재하면 성공
        if pair_cnt[n] >= 0 and pair_cnt[x] >= 0 and pair_cnt[num] >= 0:
            return True
        
    return False

 

 

이제 터미널 입력 처리하는 부분만 추가해주면 잘 동작한다.

동일한 수에 대한 중복계산을 피하기 위해 set도 활용해주었다.

def is_good(num, num_cnt_map) -> bool:
    # num의 범위는 [-1_000_000_000, 1_000_000_000]
    # O(n) 시간, O(1) 메모리 소모
    for n in num_cnt_map.keys():
        x = num - n

        # 1. (n, x, num)이 몇개나 주어졌는지 정보를 불러온다.
        pair_cnt = dict()
        for k in [n, x, num]:
            pair_cnt[k] = num_cnt_map.get(k, 0)
        
        # 2. (n, x, num) 갯수가 충분한지 하나하나 세본다.
        pair_cnt[n] -= 1
        pair_cnt[x] -= 1
        pair_cnt[num] -= 1
        
        # 3. 모든 숫자가 충분히 존재하면 성공
        if pair_cnt[n] >= 0 and pair_cnt[x] >= 0 and pair_cnt[num] >= 0:
            return True
        
    return False # None을 반환해도 연산에 오류는 없다

def handle_input(arr):
    # 1. arr에 어떤 수가 몇개 있는지 HashMap 자료구조로 저장한다.
    num_cnt_map = {}
    for i, num in enumerate(arr):
        num_cnt_map[num] = 1 + num_cnt_map.get(num, 0)

    # 2. arr 속 각 수가 '좋은수'가 맞는지 확인한다.
    # 이때 중복계산을 피하기 위해 set을 사용한다.
    cnt = 0
    good_nums = set() 
    bad_nums = set()
    
    for num in arr:
        # 기존 계산 결과 확인 - O(1) 시간 소요
        if num in good_nums:
            cnt += 1
            continue
        elif num in bad_nums:
            continue
        
        # 기존 계산 결과가 없다면 새로 계산 - O(n) 시간 소요
        else:
            if is_good(num, num_cnt_map):
                cnt += 1
                good_nums.add(num)
            else:
                bad_nums.add(num)
    return cnt

# 백준 입출력
_ = input()
arr = [int(i) for i in input().split(' ')]
print(handle_input(arr))

---

오늘의 회고

입력 범위를 자연수로 오해해서 많은 시간을 소모했다.

입력값을 정수로 확장하는 과정에서 당황해서 분기 로직을 미친듯이 만들뻔 했는데, 잠깐 타자를 멈추고 효율적인 방법을 침착하게 고민해본 것이 더 도움이 되었다.

또 오늘은 문제 조건의 상한선까지 포함하는 테스트 케이스를 만들어본 점이 잘한 것 같다.

시간복잡도 최적화를 위해 투포인터 대신 HashMap을 썼는데, 투포인터로 메모리 소모 없이 다시한번 풀어보면 좋을 것 같다.