[백준] 1253번 : 좋다 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1253번: 좋다

 

1. 문제 설명

2. 풀이과정

N의 개수가 2,000이라고 가정하면 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다.

좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다.

하여 정렬, 투 포인터 알고리즘을 사용하여 문제를 해결할 수 있다.

단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에서 제외해야 한다.

 

수를 입력받아 리스트 A에 저장한 후, 오름차순으로 정렬한다.

투 포인터 s, e를 배열 A 양쪽 끝에 위치시키고 A[s] + A[e]가 판별의 대상이 되는 수와 동일하면 좋은 수를 찾았으므로 종료한다.

반면에 A[s] + A[e]가 판별의 대상이 되는 수보다 크면 뒤쪽을 가리키는 포인터를 앞으로 이동하고, 판별의 대상이 되는 수보다 작으면 앞쪽을 가리키는 포인터를 뒤로 이동한다.

판별의 대상이 되는 수가 N이 될 때까지 반복하며 좋은 수가 몇 개인지 세어준다.

 

슈도코드

1. N (데이터 개수) 입력받기
2. A (수 데이터 저장 리스트) 입력받기
3. A 리스트 정렬하기
4. answer (좋은 수 개수 저장할 변수) 초기화
5. for N만큼 반복
6. 찾고자 하는 값 value = A[i] 초기화
7. 투 포인터 s = 0, e = N - 1 초기화
8. while (s < e)
9. if (A[s] + A[e] == value)
10. 두 포인터 s, e가 자기 자신이 아니면 (s != i and e != i) 좋은 수 개수 1 증가, 좋은 수 판별 종료
11. 두 포인터 s, e 중 하나라도 자기 자신이면 포인터 변경, 계속 판별 수행
12. elif (A[s] + A[e] < value) : 포인터 s 증가
13. else : 포인터 e 감소
14. 좋은 수 개수 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A.sort()

answer = 0
for i in range(N):
    value = A[i]
    s = 0
    e = N - 1
    while (s < e):
        if (A[s] + A[e] == value):
            if (s != i and e != i):
                answer += 1
                break
            elif (s == i):
                s += 1
            elif (e == i):
                e -= 1
        elif (A[s] + A[e] < value):
            s += 1
        else:
            e -= 1
            
print(answer)