Do it! 코딩테스트 - 배열과 리스트(2)

투포인터

투포인터는 2개의 포인터로 알고리즘의 시간복잡도를 최적화한다.

연속된 자연수의 합 구하기

단순하게 구현할 수 있는 문제이다.

초깃값은 다음과 같다

• 무조건 뽑히는 경우의 수인, 자기자신을 뽑는 경우 ! 해당 경우 1가지를 디폴트로 설정해놓는다 cnt = 1
• start , end 는 1을 가리키는 경우부터 시작하기 때문에 1로 설정한다.

원리는 간단하다. sum 이 얼마냐에 따라서 다르게 나눌 수 있다. sum 이 주어진 수 보다 작을 경우 추가적인 값이 더 필요하기 때문에 값을 추가해주는 end 인덱스를 추가한다. 반대의 경우도 마찬가지다, sum 이 주어진 수 보다 크기 때문에 필요없는 데이터를 빼기 위해서 start 인덱스를 당겨서 맨 앞에 있던 값을 버리고 그 다음값을 새로운 start 값으로 설정한다.

from sys import stdin

num = int(stdin.readline())
cnt = 1
#자기자신을 뽑는 경우는 있기 때문에 1로 초기화

start = 1
end = 1

s = 1

while end != num:
    if s == num :
        cnt+=1
        end += 1
        s += end
    elif s > num :
        s -= start
        start += 1
    elif s < num :
        end += 1
        s += end

print(cnt)

2018번: 수들의 합 5

주몽

문제의 핵심은 두개의 재료를 합한 값이 m을 충족하면 된다는 것이다.

합 을 구한 뒤 조건에 충족하는 것의 갯수를 세는 것이기 때문에 주어진 재료 배열을 정렬해서 구하는 것이 좋다. 정렬된 배열은 왼쪽이 작은 쪽 오른쪽이 큰 쪽이라는 것이 명확하기 때문이다.

정렬을 사용하기 전에 고려해야할 사항이 있다. 정렬 알고리즘은 nlogn의 시간 복잡도를 가지고 있다. 이 알고리즘을 사용해도 되는지를 확인하는 것은 n의 크기를 통해서 알 수 있다.n의 최대범위가 15,000으로 O(nlogn) = 약 20만회를 계산한다. 일반적인 알고리즘 계산 컴퓨터는 1초당 1억번 정도니 정렬 연산을 사용해도 괜찮다.

from sys import stdin

n = int(stdin.readline())
m = int(stdin.readline())

arr = sorted(list(map(int,stdin.readline().split())))

start = 0
end = n-1 # 인덱스가 0부터 시작하니까

cnt = 0

while start < end :
    #두 인덱스는 교차하면 안된다.
    if arr[start] + arr[end] < m:
        start += 1
    elif arr[start]+arr[end] > m:
        end -= 1
    else:
        cnt +=1
        start +=1
        end -=1
print(cnt)

1940번: 주몽

‘좋은 수’ 구하기 - 좋다

시간제한 2초 (최대 2억번) - N의 크기는 2000개이므로 적어도, 좋은 수 하나를 찾는 알고리즘의 시간복잡도는 O(n^2)이하여야한다.n^2알고리즘을 사용하면 최종 시간 복잡도는 n^3이 되어 제한 시간안에 문제를 풀 수 없기 때문이다.

따라서 좋은 수 하나를 찾는 알고리즘은 최소 nlogn이어야 한다. 정렬 알고리즘과 투포인터 알고리즘을 사용하되,정렬된 데이터에서 자기자신을 좋은 수 만들기에 포함하면 안된다.

해당 문제를 필요한 내용은 다음과 같다

1. 대상이 되는 숫자를 루프로 돌려버린다 → 이건 마지 용의선상에 올라간 모두를 하나하나 보는 것과 같다.

2. 더하는 수 두개가 서로 다른 수여야 한다는 점을 예외 처리 해주어야한다.

   문제에 다음과 같이 명시되어있다 수의 위치가 다르면 값이 같아도 다른 수이다

   이러한 점을 예외처리해주어야 한다. 인덱스가 다르면 값이 같아도 다른 수라는 것을 명시해주어야한다.더불어 이런 점은 세 수의 인덱스가 모두 달라야 한다는 예외처리를 해주어야한다는 말이 된다 !

   		if s != i and e != i:
                #더하는 수 두개가 서로 다른 수여야함
                cnt +=1
                break
   		elif s == i :
                s +=1
           elif e == i:
                e -=1

   

from sys import stdin

n = int(stdin.readline())
arr = sorted(map(int,stdin.readline().split()))
answer = set()
cnt = 0

for i in range(0,n):
    find = arr[i]
    s = 0
    e = n - 1
    while s < e :
        if arr[s] + arr[e] < find :
            s +=1
        elif arr[s] + arr[e] > find:
            e -=1
        else :
            if s != i and e != i:
                #더하는 수 두개가 서로 다른 수여야함
                cnt +=1
                break
            elif s == i :
                s +=1
            elif e == i:
                e -=1
						 #대상이 되는 수의 인덱스가 같으면 지나치도록 함

print(cnt)