[백준] 1940번 주몽 - 투포인터 / 시간 제한 맞추기 / 배열 정렬 / BufferReader

문제

 

 

로직

재료의 개수 변수 입력 받기 

갑옷에 필요한 수 변수 입력 받기

배열 생성

count 변수 초기화

 

1. 반복문

- 배열에 숫자 입력 받아서 저장

 

2. 반복문

- i를 start_index, j를 end_index로 생각하고 로직을 세웠다.

i와 j의 값의 변화(완쪽) / i=0, i=1일 때(오른쪽)

- if문: 배열의 2개의 값을 더했을 때 armorNum과 같으면 count에 1을 더함

 

count 값 출력

 

 

My Code

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int ingreNum = sc.nextInt();
        int armorNum = sc.nextInt();

        int[] ingreArray = new int[ingreNum];
        int count = 0;

        for (int i = 0; i < ingreNum; i++){
            ingreArray[i] = sc.nextInt();
        }
        for (int i = 0; i<ingreNum-1; i++){
            for (int j = i+1; j<ingreNum-1; j++){
                if (armorNum == ingreArray[i]+ingreArray[j]) count++;
            }
        }
        System.out.println(count);
    }
}

 

 

 

문제의 핵심 & 알게된 점

내 코드가 결과는 맞으나 백준에서는 틀렸다고 떴다.

이유는 시간제한에 맞추지 못했다.(2초 이상 걸림)

왜 일까 생각해봤는데 2가지 원인을 알 수 있었다.

1. Scanner를 사용해서 값 스캔에 시간이 더 걸림

-> BufferedReader와 StringTokenizer을 이용하여 더 빠르게 해결

 

2. 이중 반복문을 이용해서 시간 복잡도가 O(n)이 아닌 O(n^2)이 되어 비효율적

-> 배열을 오름차순 정렬하고

    while문과 if문을 이용해 시간복잡도를 O(n)가 되게 해서 해결

 

문제의 시간 제한도 잘 맞추기 위해 시간복잡도, 변수 범위를 잘 확인해야겠다고 느꼈다.

 

처음에는 BufferedReader을 사용해서 문제를 풀었는데 NoSuchElementException 오류가 나서 

Scanner 방식으로 바꾼 것이다.

왜 처음에 오류가 났나 다시 확인해 보니

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

int ingreNum = Integer.parseInt(stringTokenizer.nextToken());
int armorNum = Integer.parseInt(stringTokenizer.nextToken());
int[] ingreArray = new int[ingreNum];
int count = 0;

    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int i = 0; i<ingreNum; i++){
    ingreArray[i] = Integer.parseInt(stringTokenizer.nextToken());
    }

위의 코드가 내가 첨에 오류난 코드이다.

 

StringTokenizer을 ingreNum, armorNum에 써서 오류가 난 것이다.

이 두 변수는 토큰도 없이 한 자리 정수만 입력받는 건데 저걸 이용한 것이 문제였다.

(ingreArray에는 사용해도 됨)

 

ingreNum, armorNum는 bufferedReader.readLine()을 써서 입력받는 걸로 고쳐서 해결했다.

 

 

참고 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int ingreNum = Integer.parseInt(bufferedReader.readLine());
        int armorNum = Integer.parseInt(bufferedReader.readLine());
        int[] ingreArray = new int[ingreNum];
        int count = 0;

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < ingreNum; i++){
            ingreArray[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        
        Arrays.sort(ingreArray);
        int i = 0;
        int j = ingreNum-1;
        while(i<j){
            if (ingreArray[i] + ingreArray[j] < armorNum) i++;
            else if (ingreArray[i] + ingreArray[j] > armorNum) {
                j--;
            }
            else {
                count++;
                i++; j--;
            }
        }
        System.out.println(count);
    }
}

 

 

참고_인프런의 Do it! 알고리즘 코딩테스트 with JAVA