[Do-it! 코딩 테스트-기초편] 008. '좋은 수' 구하기

문제

https://www.acmicpc.net/problem/1253

1253번: 좋다

---

접근

데이터 크기: 2,000

시간 제한: 2초

N^2의 연산은 충분히 가능하다. 하지만 N^3가 되면 2초안에 해결이 불가능하다. 2초 = 대략 80,000,000 데이터

반복문은 최대 2개까지 중첩이 가능할 듯 하다.

 

N개의 수에서 자신(K)이 아닌 다른 두 수의 합으로 자신(K)과 같은 수를 만들 수 있다면 K는 '좋은 수'이다.

나(K)를 만들 수 있는 두 수를 찾으려면 투 포인터를 사용하는 것이 좋아보인다.

투 포인터를 사용하기 위해 정렬도 필요하다.

---

코드

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split(' ')))  # 중복 o, N개, 정렬 x
num.sort()
temp = 0
cnt = 0

while temp < N:
    start = 0
    end = N - 1

    while start != end:
    	# 1
        if end == temp:
            end -= 1
        # 2
        if start == temp:
            start += 1
        # 3
        if start == end:
            break
        # 4
        if num[start] + num[end] == num[temp]:
            cnt += 1
            break
        # 5
        elif num[start] + num[end] < num[temp]:
            start += 1

        elif num[start] + num[end] > num[temp]:
            end -= 1
    temp += 1

print(cnt)

---

설명

두 번의 while문을 사용했다. while문 내부에 조건이 많은데 하나씩 설명하면

 

# 1, # 2

만약 포인터가 자기 자신 즉, 좋은 수인지 판별하는 대상을 가리킨다면 '다른 두 수의 합에서' 조건을 만족하지 못하기 때문에 해당 인덱스를 벗어나기 위한 부분이다. 벗어난 직후 포인터가 가리키는 값은 좋은 수를 판별하는 데에 사용할 수 있다.

 

# 3

위 조건에서 한가지 예외가 있다. 만약

1. 반복문의 어떤 싸이클에 start와 end의 차이가 1이고

2. 둘 중 하나의 포인터가 자기 자신을 가리켰을 때

두 포인터 중 하나를 증가하거나 감소하여 벗어나려고 하면 start = end 

이 때 start, end가 가리키는 값의 합이 자기 자신과 같다면, 즉 좋은 수라고 판별이 된다면,

오답이다. 

 

바로 '주어진 N개의 수에서 다른 두 수의 합으로 표현'이기 때문에다.

따라서 break를 사용하여 반복문을 빠져나와야한다.

 

# 4

좋은 수 판별이 된 경우이고, 판별 후에 cnt 증가와 함께 break를 통해 빠져나온다.

 

# 5

투 포인터 이동 규치이다.

두 포인터가 가리키는 값의 합이 num[temp]보다 작으면 start += 1

반대면 end -= 1

---

피드백

처음에는 자신을 제외시켜야한다는 사실을 모르고 계속 틀렸다.

문제를 꼼꼼히 읽고 놓친 조건이 없는지 확인해야겠다.

 

해답 코드는 양쪽 투 포인터가 아닌 한쪽 투 포인터를 사용했다.

외에도 여러 방법을 사용할 수 있을 것 같다.

---

알고리즘

투 포인터