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

 

1940번: 주몽

 

1. 문제 설명

2. 풀이과정

해당 문제의 시간 제한은 2초인데 N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있다.

O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있기 때문에 정렬을 사용할 수 있다.

하여 재료들의 번호를 입력받은 뒤, 오름차순으로 정렬하여 양쪽 끝의 위치를 투 포인터로 지정해 문제를 해결한다.

 

투 포인터 start, end를 정렬한 재료들의 번호 양쪽 끝에 위치시킨 후 포인터를 이동시키며 탐색한다.

만약 두 포인터의 위치 번호의 합이 갑옷을 만드는데 필요한 수와 동일하다면 갑옷을 만들 수 있는 경우다.

그게 아니라면 양쪽 포인터의 위치를 변경하며 start 위치가 end 위치를 넘어가기 전까지 탐색한다.

 

슈도 코드

1. N(재료의 개수), M(갑옷이 되는 번호) 입력받기
2. li(재료 데이터 저장할 리스트) 입력받기
3. li 리스트 오름차순으로 정렬하기
4. start(시작 인덱스 = 처음 재료 위치)
5. end(끝 인덱스 = 마지막 재료 위치)
6. answer(갑옷을 만들 수 있는 경우의 수 = 0)
7. while (start < end)
8. if (두 재료의 합 == M) : 경우의 수 증가, 양쪽 위치 각각 변경
9. elif (두 재료의 합 > M) : 큰 번호 재료를 한 칸 아래로 변경
10. else : 작은 번호 재료를 한 칸 아래로 변경

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))

li.sort()
start = 0
end = N - 1
answer = 0

while (start < end):
    if (li[start] + li[end] == M):
        answer += 1
        start += 1
        end -= 1
    elif (li[start] + li[end] > M):
        end -= 1
    else:
        start += 1
        
print(answer)