[Python] 백준 1253 - 좋다

🧑‍💻 백준 1253 - 좋다

Gold 4 - 정렬

 

리스트 안에 있는 어떤 수를, 리스트 안에 있는 두 수의 합으로 나타낼 수 있는 수의 개수를 구하는 것이다

여기서 놓치지 말아야 할 것은, 숫자의 값이 같아도 위치가 다르면 다른 숫자로 간주한다

 

예시)

null

원래 그냥 리스트를 정렬을 한 후, 투 포인터를 이용해서 더해서, 더한 숫자가 리스트에 있는지 확인만 하면 되는 줄 알았다

• 그렇게 되면, 다른 위치에 있어도, 같은 값의 숫자가 카운팅이 잘 안 될 수 있다
• 그래서 숫자 하나하나 씩 빼고, 그 외의 숫자들을 투 포인터를 사용해서 그 뺐던 숫자와 일치하는지 더해주면 된다

---

 

문제 풀이

위 각 변수들의 설명

• i : for문을 통해서 정렬된 리스트에 있는 값들을 가지고 온다 (range를 가지고 오면 됨)
• temp : i의 값을 제외한, 정렬된 리스트에 있는 값들을 리스트로 만든다
• start / end : 투 포인터다 (인덱스로 표현, while문으로 구현)
• add_num : 투 포인터의 값들을 더한 값이다.
  • add_num > i : end 를 1씩 빼준다
  • add_num < i : start에 1씩 더해준다
  • add_num = i : result에 1을 누적 시키고, 해당 while문은 break 한다
• result : add_num과 i가 같을 경우 1을 누적 시켜 주는 것이다

이렇게 하면, 리스트에 있는 각 숫자들을 꺼내오는 것이기 때문에, 숫자의 값이 같아도, 다른 숫자로 취급을 할 수 있다

---

 

코드

N = int(input())
array = list(map(int, input().split()))

array.sort(key=lambda x: x)
result = 0

for i in range(N):
	# 숫자가 같아도, 다른 위치에 있으면, 다른 숫자이다
    # 0 0 2 2 2
    # 답이 3개
    temp = array[:i] + array[i+1:]
    start, end = 0, len(temp) - 1

    while start != end:
        add_num = temp[start] + temp[end]

        if add_num == array[i]:
            result += 1
            break
        elif add_num > array[i]:
            end -= 1
        else:
            start += 1

print(result)

• for문을 이용해서, 두 수를 더해서 나와야 할 숫자를 정한다
• while문을 이용해서 투 포인터를 설정한다