[백준] 1940 주몽 - 투 포인터 + 정렬 JAVA

https://www.acmicpc.net/problem/1940

1940번: 주몽

코드설명

투포인터 문제입니다.

 

처음에는 아래의 문제조건을 제대로 이해하지 못하고 일반적인 투포인터로 풀었다가 해당 조건을 읽고 다시 풀었습니다.

- 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다.

 

투포인터 같은경우

• 포인터 2개가 처음부터 같은방향으로 진행해나가는 방법
• 포인터 2개가 양끝에서 반대로 진행해나가는 방법

이렇게 2가지가 있습니다.

 

첫번째방법인, 포인터 2개가 처음부터 같은 방향으로 진행해나가는 방법으로 풀경우,

투포인터의 시간복잡도인 O(N)이 나오지않고, O(N*N) 이 나오게됩니다. 

일반적인 For문을 도는것과 같습니다. ( 그렇지만, 문제는 통과합니다. )

 

두번째 방법인 포인터 2개가 양끝에서 반대로 진행해나가는 방법으로 풀어야만,

O(N)의 시간복잡도로 해결할 수 있습니다.

또한, 이 방법 같은경우 오름차순 정렬을 해야만 합니다.

 

이 문제같은경우 두가지 방법으로 풀어도 모두 시간초과가 나오지 않지만,

시간이 빡빡하다면, 첫번째 방법으로 풀경우 시간초과가 나올 것으로 보입니다.

 

이 문제의 For문으로 풀경우 시간복잡도를 확인할경우

 N(1 ≤ N ≤ 15,000) -> 15,000 * 15,000 = 225,000,000 으로 약 2.25초의 시간이 Limit 입니다.

 

코드

 

포인터 2개가 양끝에서 반대로 진행해나가는 방법

- 오름차순 정렬필요 (Arrays.sort의 시간복잡도는 퀵정렬로 운이 안좋을경우 O(N^2), Collections.sort는 O(n log n)을 보장)

- 만약 투포인터로 풀었는데도 시간초과가 나온다면 Sort를 변경해보기

- 시간복잡도 O(N)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	Arrays.sort(arr);
    	
    	twoPointer();
    	
    	System.out.println(answer);
    }
    
    public static void twoPointer() {
    	int start = 0;
    	int end = N - 1;
    	int intervalSum = 0;
    	
    	while(start < end) {
    		intervalSum = arr[start] + arr[end];
    		
    		if(intervalSum < M) {
    			start += 1;
    		}
    		else if(intervalSum > M) {
    			end -= 1;
    		}
    		else if(intervalSum  == M) {
    			answer += 1;
    			start += 1;
    			end -= 1;
    		}
    		
    	}
    }
    
}

 

포인터 2개가 처음부터 같은 방향으로 진행해 나가는 방법

- 시간복잡도 O(N^N)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	twoPointer();
    	
    	System.out.println(answer);
    }
    
    public static void twoPointer() {
    	int start = 0;
    	int end = 0;
    	int intervalSum = 0;
    	
    	while(start < N) {
    		end = start + 1;
    		while(end < N) {
    			intervalSum = arr[start];
    			intervalSum += arr[end];
    			end += 1;
    			if(intervalSum == M) {
    				answer += 1; 
    				break;
    			}
    		}
    		start += 1;
    		
    	}
    }
    
}

 

갑옷을 두개의 재료라는 것을 반영하지 않은 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	twoPointer();
    	
    	System.out.println(answer);
    }
    
    public static void twoPointer() {
    	int start = 0;
    	int end = 0;
    	int intervalSum = 0;
    	
    	while(start < N) {
//    		System.out.println(intervalSum);
    		while(intervalSum < M && end < N) {
    			intervalSum += arr[end];
    			end += 1;    			
    		}
    		
    		if(intervalSum == M) {
    			answer += 1;
    		}
    		    		
    		intervalSum -= arr[start];
    		start += 1;
    		
    	}
    }
}