[BOJ] 1253. 좋다

📌 1253. 좋다

이제 알고리즘을 풀 때 마다 어떤 문제를 어떻게 풀었는지 기록해보고자 한다.
기록하면서 풀이 방법도 다시 정리하고, 개념도 다져봐야지 ~

아무튼 알고리즘 첫 게시물은 다음주 스터디 문제인 백준 1253번 좋다이다.

---

💡 Gold 4 / 1028ms

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력

10
1 2 3 4 5 6 7 8 9 10

예제 출력

8

---

💡 PS

• 우선 주어진 수들 중 두 개의 수의 합이 되는 수들로 구성된 집합리스트를 만든다.
• 입력값으로 주어진 배열과, 위에서 만든 집합 리스트를 모두 오름차순으로 정렬한다.
• 그 뒤 집합 리스트를 순환하며 해당 값이 나오는지 입력값으로 주어진 숫자 배열을 투포인터로 탐색한다.

N = int(input())
numbers = sorted(list(map(int, input().split())))
answer = 0

nums = []

for i in range(N):
    for j in range(N):
        if i != j and numbers[i] + numbers[j] in numbers:
            nums.append(numbers[i] + numbers[j])

nums = sorted(nums)

for num in nums:
    left = 0
    right = len(numbers) - 1

    while left != right:
        tmp = numbers[left] + numbers[right]
        if tmp == num:
            answer += 1
            break
        elif tmp < num:
            left += 1
        elif tmp > num:
            right -= 1

print(answer)

• 위 생각대로 처음 짠 코드이다.
• 하지만 제출했더니 python으로는 시간초과, pypy로는 틀렸습니다. 가 떴다.

---

• 문제는, 수가 중복이 되면 안된다는 것.

• 예를 들어 입력 배열이 0 0 1 이라면, 0 0 이 더해지면 순환할 때 0 0 을 빼야한다는 것이다. 그렇지 않으면 0 0 을 더하면 0이 나오고 위에서 만든 집합리스트에 존재하므로 좋은 수로 카운팅이 된다.

• 위 문제를 고려하여 다시 코드를 짜보았다.

• 미리 좋은 수가 될 수 있는 집합리스트를 만들어 놓지 않고, 하나의 리스트에서 인덱스가 겹치지 않는 조건을 추가하여 풀었다.

• 코드는 아래와 같다.

N = int(input())
numbers = sorted(list(map(int, input().split())))
answer = 0

for i in range(N):
    number = numbers[i]
    left = 0
    right = N - 1

    while left != right:
        tmp = numbers[left] + numbers[right]
        if i != left and i != right and tmp == number:
            answer += 1
            break

        elif tmp <= number:
            left += 1
        elif tmp >= number:
            right -= 1

print(answer)

• 하지만 모든 배열의 수가 같은 수 일 경우 대소 비교에서 포인터가 이동하는 부분이 잘못 작동하게 된다.
• 그래서 tmp == number 인 경우의 조건을 더 추가하여 인덱스가 이동하게 만들어주었다.

N = int(input())
numbers = sorted(list(map(int, input().split())))
answer = 0

for i in range(N):
    number = numbers[i]
    left = 0
    right = N - 1

    while left != right:
        tmp = numbers[left] + numbers[right]
        if tmp == number:
            if i != left and i != right:
                answer += 1
                break
            elif i == left:
                left += 1
            else:
                right -= 1

        elif tmp <= number:
            left += 1
        elif tmp >= number:
            right -= 1

print(answer)

• 위와 같이 조건을 추가하니
  드디어 맞았다 ...!

---

📌 회고

• 이제 그래도 문제를 보면 어떤 풀이방법인지 금방 떠오른다 ! 많이 발전했다.

• 하지만 설계 단계에서 허점이 있는 것 같다. 예제는 금방 통과하는데 정답까지 가는데 시간이 꽤 걸린다. 좀 더 침착하고 치밀하게 해답을 설계하고 코드를 짜도록 해봐야겠당.

• 싸피 2학기 하면서 알고리즘에 작년보다 소홀했는데, 그래도 알잘딱깔센 스터디 하면서 카카오 기출을 꾸준히 푼 덕분인지 작년에는 잘 못했던 투포인터가 이제는 좀 쉽게 느껴진다 !!!