[Do-it 코딩 테스트] 008. '좋은 수'구하기(1253)

문제

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

1253번: 좋다

---

코드

내가 작성한 코드

n = int(input())
m = list(map(int, input().split()))
m.sort()
s, e = 0, len(m)-1
count = 0

for i in range(len(m)):
    s, e = 0, len(m)-1
    while s != e:
        if i == s:
            s += 1
        if i == e:
            e -= 1
        if s == e:
            break
        if  m[i] == (m[s]+m[e]):
            count += 1
            break
        elif (m[s]+m[e]) > m[i]:
            e -= 1
        else:
            s += 1
print(count)

---

해석

예제 입력	예제 출력
10 #수의 개수 1 2 3 4 5 6 7 8 9 10	8

n = int(input())
m = list(map(int, input().split()))
m.sort()
s, e = 0, len(m)-1
count = 0

이 문제는 주어진 N개의  수에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 '좋은 수'라고 하는데 주어진 수 중에 좋은수가 몇개 있는지 개수를 구하는 문제이다.

 

예를 들어 1 2 3 4 5 6 7 8 9 10이라고 주어졌을 때 1, 2 빼고는 전부 '좋은 수'이기 때문에 답은 8이 된다.

여기서 주의해야 하는 점은 나 자신은 계산에서 제외해야하는 점이다.

 

이 문제도 이전 문제들과 동일하게 투 포인터를 사용하여 문제를 풀 수 있는데 해당 문제에서는 투 포인터가 맨 앞, 맨 뒤 에서 시작한다.

for i in range(len(m)):
    s, e = 0, len(m)-1
    while s != e:
        if i == s:
            s += 1
        if i == e:
            e -= 1
        if s == e:
            break
        if  m[i] == (m[s]+m[e]):
            count += 1
            break
        elif (m[s]+m[e]) > m[i]:
            e -= 1
        else:
            s += 1
print(count)

이 문제는 start포인터와 end 포인터값을 더했을때 입력받은 값에 있으면 count를 1 올리고 없을 경우 상황에 따라 end포인터, start포인터를 이동시켜주면 된다.

 

우선 for문으로 입력받은 배열의 길이만큼 반복을 시켜주고 그 안에 다시 while문으로 반복을 진행해준다. 다른 문제와 같이 while문에 조건을 주지 않으면  무한루프에 빠져 s != e start포인터와 end 포인터가 같을때 반복문을 탈출할 수 있도록 조건을 걸어주었다.

 

그리고 그 안에 if문을 사용해서 조건에 따라 포인터를 움직여주는데 위에 말했던것처럼 나 자신은 계산에서 빠져야하기때문에 i(인덱스) 와 start 포인터가 같을 시 start 포인터를 앞으로 1 더해주고 i와 end 포인터가 같을 경우 end 포인터를 1 빼주고 s==e start와 end포인터가 같을 경우에는 반복문을 빠져나오게 break를 써주었다.

 

1. m[i] 내가 (m[s] + m[e]) 더한값과 같을때

두 값이 같을 경우 '좋은 수' 이므로 count 를 올려주고 반복문을 빠져나와준다.

 

2. m[i] 내가 (m[s] + m[e]) 더한값보다 작을때

내가 (m[s] + m[e]) 보다 작을 때에는 e 포인터를 1 빼준다 이유는 포인터를 빼줘야 더한 값이 작아지기 때문에 end 포인터에서 -  1을 빼야한다.

 

3.  m[i] 내가 (m[s] + m[e]) 더한값보다 클때

내가 (m[s] + m[e])를 더한 값보다 클 때 start 포인터를 1 증가시켜준다

우리가 얻고싶어했던  연속된 합이 N을 나타내는 수를 구할  수 있다.