[Java]문제 007번 (백준 1940번)

문제

주몽 (1940번)

내 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 
        // 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다
        //     m은 두 개의 수의 합으로 표현되어야 한다. 2+7처럼
        //     한 번 쓴 재료는 다시 못 쓰니 않나? 애초에 2로 m을 만들 수 있는 수는 딱 하나로 정해져 있음. m이 9라면 2는 무조건 7이 있어야 함.
        // 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 
        // 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램
        
        //  재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 
        //  그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
        //     n의 경우 10의 5제곱 곱하기 10의 4제곱은 10의 9제곱이고 10억이네. 
        //     m은 천만이라 연산 횟수 조심해야 하고 
        //     고유하다니까 겹치지는 않을 것이고
            
        // 6 // n, 재료의 개수가 주어짐
        // 9 // m, 갑옷 만드는 데 필요한 수
        // 2 7 4 1 5 3 // 고유 번호 주어짐
        
        // 결과는 2인데
        //     합이 9가 되어야 함. 재료는 무조건 2개로만, 그러니 2+7, 4+5 ->이렇게 두 개 
        
        // how?
        //     난 고유 번호는 배열로 받고 싶음. 
        //     연산 횟수는 15000 C 2라서 대략 10의 8제곱? 시간 제한 2초라 2억으로 제한됨
            
        //     배열로 받고, 이를 오름차순으로 정렬하고, si는 앞쪽에 ei는 뒷쪽부터 초기화해주고, 
        //     게속 si, ei 옮겨가면서 합이 m이 되는 경우를 찾으면 cnt++하고 그러면 되지 않을까
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        
        //입력값 다 받기
        int n=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(br.readLine());
        int m=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(br.readLine());
        int[] nums=new int[n+1];
        for(int i=1;i<=n;i++){
            nums[i]=Integer.parseInt(st.nextToken());
        }
        //배열 오름차순 정렬하기 
        Arrays.sort(nums);
        
        //필요 변수도 생각해보기
        int si=1; //배열 처음 부분에 위치
        int ei=n; //배열 마지막 부분에 위치 
        int cnt=0; // m이 될 때마다 ++해주기 
        
        //si+ei가 m인지 판단
        while(si<ei){
            long sum=nums[si]+nums[ei];
            if(sum==m){
                cnt++;
                si++; ei--;
            }else if(sum>m){
                ei--;
            }else{
                si++;
            }
        }
        
        System.out.println(cnt);
    }
}

• 처음에 while(si>=ei)로 해 놓고, 왜 답이 0으로 나오지, 의아하며 몇 분 고민햇음.
  • 난 처음엔 si>=ei가 아닐 때까지란 의도로 적었는데, 생각해보니 whille 괄호 안에 참일 때만 반복하는 걸 잊고 있었음. 정확힌 알고 있는데 신경이 미치지 못했음.
  • 주요 로직만 생각하면 당연하고 어이없는 사소한 실수를 하는데, 참 적어서 계속 내가 이 때 이런 식으로 생각해서 막혔구나 알게 해야 겠다. 그럼 이게 축적되면 어떻게든 고쳐지겠지.
• 입력값 받을 때 st를 남발해서 쓴 것 같음. n, m을 받을 땐 st 안 쓰고 그냥 br.readLine해주면 되는데. 물론 큰 문제 푸는 데 큰 상관은 없고 사소하지만 일단 남겨봄

교재 풀이

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();
  }
}

설명

아래 영상보면 바로 해결되는 쉬운 문제지만, 알아두면 좋을 것만 기록하자면

• n의 최대 범위가 15000이므로 O(nlogn) 시간 복잡도 알고리즘 사용해도 문제 없음 -> 일반적으로 정렬 알고리즘( Arrays.sort(A)) 시간 복잡도는 O(nlogn)
• 투 포인터 문제 90% 이상은 정렬을 이용하는 문제. 정렬을 이용해서 풀거나, 정렬된 채 주어지거나 =>  정렬을 이용해서 시간복잡도를 줄일 수 있는 알고리즘 필요하다 싶으면 투 포인터 떠올리기