SIU
article thumbnail

문제 링크

 

1940번: 주몽

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고

www.acmicpc.net

접근법

투 포인터는 값이 정렬되어 있을 때 규칙을 찾기 편하다. 이 문제는 입력 값이 순차적으로 증가하지 않아 정렬을 해주고나서 투 포인터 방향에 대한 규칙을 세웠다. 맨 앞과 뒤 인덱스를 포인터 삼아 sum을 계산했다.

 

주의

처음 이 문제 0번째 인덱스를 비우고 1번부터 시작했는데 start = 0 end= N-1로 잡아 값이 잘못 나왔다. 0번째 인덱스를 비우고 1번 인덱스부터 시작했으려면 start=1로 end=N으로 잡아야지 올바르게 계산된다. 정렬이나 이런 인덱스를 활용하는 문제에서 0번째 인덱스를 포함시킬건지, 뺄건지에 따라 인덱스 설정을 잘해주자. 

 

성능 요약

메모리: 15084 KB, 시간: 144 ms

 

분류 : 정렬(sorting), 두 포인터(two_pointer)

 

전체코드 (JAVA)

import java.util.*;
import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int num = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		// 배열 초기화
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		// 순차 정렬 할 때 0인덱스 확인 잘하기 (배열크기랑), 배열크기 1크게 잡으면 인덱스 변화시켜야함
		Arrays.sort(arr);
		// start, end 투 포인터가 양 끝에서 시작
		int start = 0;
		int end = N-1;
		int count = 0;
		int sum = arr[start] + arr[end];
		// 재료는 고유한 번호이기 때문에 똑같은 번호 불가
		while( start < end) {
			if(sum == num) { // start , end 둘 다 변화
				end--;
				start++;
				count++;
				
			}else if (sum < num) { // 값이 더 커져야 되는 상황 -> start 인덱스 증가
				start++;
			}else { // sum > num 값 더 줄여야 되는 상황 -> end 인덱스 감소
				end--;
			}
			sum = arr[start] + arr[end]; // sum 갱신
		}
		System.out.println(count);
		br.close();
	}
}

 

공부자료 https://m.blog.naver.com/kks227/220795165570

 

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다. 첫 번째로 소개해드릴 기법은 투 포인터(t...

blog.naver.com

 

profile

SIU

@웹 개발자 SIU

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!