📌 문제 007) 주몽의 명령
시간 제한 2초, 실버 IV, 백준 1940번
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
6 9 2 7 4 1 5 3
출력
첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
2
1단계 문제 분석
• 두 숫자의 합, 즉, 두 숫자 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있다. N의 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 된다. 정렬을 써도 된다.
• 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근하자.
• 리스트 A에 재료 데이터를 저장한 후, 오름차순 정렬을 한다.
• 투 포인터 i, j를 양쪽 끝에 위치시킨 후 문제 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행한다.
[투 포인터 이동 원칙]
• A[i] + A[j] > M: j--;
• A[i] + A[j] < M: i++;
• A[i] + A[j] == M: i++; j--; count++;
2단계 슈도 코드
N(재료의 개수), M(갑옷이 되는 번호)
A(재료 데이터 저장 리스트)
A 리스트 정렬하기
i(시작 인덱스 = 0)
j(종료 인덱스 = N-1)
count(정답값 = 0)
while i < j:
if 재료 합 < M: 작은 번호 재료를 한 칸 위로 변경
elif 재료 합 > M: 큰 번호 재료를 한 칸 아래로 변경
else 경우의 수 증가, 양쪽 index 각각 변경
count 출력3단계 코드 구현
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
i = 0
j = N-1
while i < j: # 투 포인터 이동 원칙에 따라 포인터 이동하며 처리
if A[i] + A[j] < M:
i += 1
elif A[i] + A[j] > M:
j -= 1
else:
count += 1
i += 1
j -= 1
print(count)📌 문제 008) '좋은 수' 구하기
시간 제한 2초, 골드 IV, 백준 1253번
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
10 1 2 3 4 5 6 7 8 9 10
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
8
1단계 문제 분석
• 수를 입력 받아 리스트 저장 후 정렬한다.
• 투 포인터 i, j를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙을 활용해 탐색을 수행한다.
• 판별의 대상이 되는 수는 K라고 가정한다.
[투 포인터 이동 원칙]
• A[i] + A[j] > K: j--;
• A[i] + A[j] < K: i++;
• A[i] + A[j] == K: count++; 프로세스 종료
2단계 슈도 코드
N(데이터 개수)
Result(좋은 수 개수 저장 변수)
A(수 데이터 저장 리스트)
A 리스트 정렬
for N만큼 반복:
변수 초기화(찾고자 하는 값 find = A[k], 포인터 i, 포인터 j)
while i < j:
if A[i] + A[j] == find:
두 포인터 i, j가 k가 아닐 때 좋은 수 개수 1 증가 및 while 문 종료
두 포인터 i나 j가 k가 맞을 때 포인터 변경 및 계속 수행
elif A[i] + A[j] < find: 포인터 i 증가
else: 포인터 j 감소
좋은 수 개수 출력3단계 코드 구현
import sys
input = sys.stdin.readline
N = int(input())
Result = 0
A = list(map(int, input().split()))
A.sort()
for k in range(N):
find = A[k]
i = 0
j = N - 1
while i < j: # 투 포인터 알고리즘
if A[i] + A[j] == find: # find는 서로 다른 두 수의 합이어야 함을 체크
if i != k and j != k:
Result += 1
break
elif i == k:
i += 1
elif j == k:
j -= 1
elif A[i] + A[j] < find:
i += 1
else:
j -= 1
print(Result)