백준 1940번 자바

문제

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

1940번: 주몽

import java.util.Scanner;

public class Main1940 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] arr = new int[N];
		int startIndex = 0;
		int endIndex = 1;
		int cnt = 0;
		
		for (int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		while (startIndex != N-2) {
			if (arr[startIndex]+arr[endIndex] == M) {
				cnt++;
				startIndex++;
				endIndex = startIndex + 1;
			} else if (endIndex == N-1){
				startIndex++;
				endIndex = startIndex + 1;
			} else {
				endIndex++;
			}
		}
		
		System.out.println(cnt);
	}
}

1. 이번엔 투포인터를 활용해 문제를 해결했다. 

 

2. 문제 해결 자체는 어렵지 않았으나 다른 해답과 비교했을 때 시간 차이가 너무 많이 났다. 내 코드는 굳이 탐색을 하지 않아도 될부분까지 탐색을 확률이 높기때문에 시간이 더 오래걸렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1940_주몽 {
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int M = Integer.parseInt(bf.readLine());
    int[] A = new int[N];
    StringTokenizer st = new StringTokenizer(bf.readLine());
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(A);
    int count = 0;
    int i = 0;
    int j = N - 1;
    while (i < j) {
      if (A[i] + A[j] < M) {
        i++;
      } else if (A[i] + A[j] > M) {
        j--;
      } else {
        count++;
        i++;
        j--;
      }
    }
    System.out.println(count);
    bf.close();
  }
}
// 출처 : https://github.com/doitcodingtestjava/answer/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/P1940_%EC%A3%BC%EB%AA%BD.java

3. 위 코드와 내 코드의 차이는 일단 BufferedReader와 Scanner 사용에 따른 시간, 메모리 차이가 존재한다. 하지만 내 코드의 입출력을 BufferedReader로 진행해도 시간은 약 1.5배 정도 차이가 난다.

그 이유는 접근 방식에 있었다.  위 코드는 N의 최대값이 크지 않기에 정렬을 해도 시간 복잡도가 작아 정렬 후, 투포인터를 양쪽 끝에서 중간으로 좁히면서 탐색을 했기 때문이다. 

 

정리 : 같은 투포인터를 사용했음에도 시간에서 1.5배나 차이가 난다. 항상 단순하게 풀 생각보단 어떻게하면 시간, 메모리를 단축 시킬 수 있을지에 대해 고민하자.