[코드업 - 1430] 기억력 테스트2 - Java

 

 

문제 설명

 

기억력 테스트 2

 

풀이 1 : Fail(메모리 초과)

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        HashMap<Integer, Boolean> map = new HashMap();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st_n = new StringTokenizer(br.readLine(), " ");
        while(st_n.hasMoreTokens()) map.put(Integer.parseInt(st_n.nextToken()), false);

        int i, m = Integer.parseInt(br.readLine());
        StringTokenizer st_m = new StringTokenizer(br.readLine(), " ");
        for(i=0; i<m; i++) {
            if(map.containsKey(Integer.parseInt(st_m.nextToken()))) bw.write("1 ");
            else bw.write("0 ");
        }
        bw.flush();
        bw.close();
    }
}

 

 

풀이 1 문제원인 분석

해당 문제는 N의 값(주현이가 기억해야할 숫자의 개수)이 최대 1천만이므로 알고리즘의 시간복잡도를 O(N) 정도로 맞춰야 했다.(해당 문제에서는 시간 제한을 4Sec로 여유를 두고있기는 하다.) 우선 최대한 빠른 속도의 연산을 위해 평상시 콘솔 입력값을 불러오기 위해 사용하던 Scanner 객체가 아닌 BufferedReader 객체를 사용했고, 콘솔창에 출력하기 위해 사용하던 System 객체의 println 메서드가 아닌 BufferedWriter 객체를 사용했다.

 

직관적으로는 M개의 질문의 숫자에 대해 처음 입력받았던 N개의 기억해야할 숫자가 일치하는지 이중 for문과 if문을 통해 구할 수 있겠지만 이는 알고리즘의 시간복잡도가 O(N*M)로 성능을 매우 저하시키므로 최대 데이터가 1천만개인 해당 문제에는 적합하지 않다. 이중 for문을 활용한 풀이의 예시는 아래 코드와 같다.

int result = 0; // 질문하는 숫자가 기억해야할 숫자에 포함되지 않는 경우 0 출력
for(int i = 0; i<m; i++) { // 질문하는 숫자
    for(int j = 0; j<n; j++) { // 기억해야할 숫자
        if (질문하는 숫자 == 기억해야할 숫자) {
            result = 1; // 질문하는 숫자가 기억해야할 숫자에 포함되는 경우 1 출력
            break;
        }
    }
    System.out.printf("%d ", result);
    result = 0;
}

 

이때 처음에 N개의 기억해야할 숫자들을 나중에 질문하는 숫자와 일치하는지 검사하기 위해서는 N개의 기억해야할 숫자 데이터들을 어떤 자료구조에 각각 저장해야하는데, 배열이나 맵 등의 객체를 사용할 수 있다. 우선 배열 자료구조를 이용한 풀이 방법으로는 초기에 1천만 개의 요소를 가진 배열을 초기화한 후 각각의 기억해야할 숫자를 배열의 인덱스와 매칭시켜 해당 값을 1로 설정해주는 것이다.

 

이때 각각의 숫자를 빠른 속도로 한번에 받기 위해 한 줄 전체를 문자열로 읽어오는 BufferedWriter 객체의 readline() 메서드를 이용했고, 이를 공백을 기준으로 각각의 숫자값을 나눈 후 해당 배열 인덱스별 값에 할당하기 위해 그리고 기억해야할 숫자와 질문하는 숫자를 검사하기 위해 while문과 StringTokenizer 객체의 hasMoreTokens()와 nextToken() 메서드를 이용했다. 예시는 아래 코드와 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] right_answer = new int[100000001];
        StringTokenizer st_n = new StringTokenizer(br.readLine(), " ");
        while(st_n.hasMoreTokens()) right_answer[Integer.parseInt(st_n.nextToken())] = 1; // 기억해야할 숫자에 해당하는 배열의 인덱스 값은 1로 할당

        int m = Integer.parseInt(br.readLine());
        StringTokenizer st_m = new StringTokenizer(br.readLine(), " ");
        while(st_m.hasMoreTokens()) bw.write(String.valueOf(right_answer[Integer.parseInt(st_m.nextToken())]) + " "); // BufferedWriter를 이용해 정수형을 출력시키기 위해서는 String의 변환이 필요하다.
        bw.flush();
        bw.close();
    }
}

 

이처럼 배열을 사용할 수도 있지만 탐색 속도가 아주 빠른 Hashmap 자료구조를 이용해도 무방하다. Haspmap 이용 시 배열과 달리 처음에 크기를 초기화하지 않아도 된다. 입력받은 숫자(Token)을 Key로 저장하고, boolean형 false를 Value(값)으로 저장했는데, 추후에도 이를 활용하지 않기 때문에(Key만 활용) 메모리를 그나마 적게 소요하는 임의의 boolean형으로 값을 저장한 것이다. Hashmap을 이용한 코드는 풀이 1 최상단에 있는 코드와 같다.

 

하지만 실행결과 둘 다 약 0.3Sec로 아주 짧은 시간이 소요되었지만 문제는 "메모리 초과"였다. 정확한 메모리 사용량은 측정하진 못했지만 최소 192MB의 메모리를 상회하여 문제 제한조건을 한참 위반한 것이다. 이에 대한 원인으로는 빠른 시간을 위해 readLine을 사용하여 문자열을 받는데, 최초 입력받는 데이터 N의 개수만해도 무려 1천만개일뿐만 아니라, 각각의 요소값은 심지어 1~1천만까지 표현이 되기 때문에 메모리 사용량이 엄청났던 것이다.(단, 중복 X) 즉, 이 문제는 데이터를 입력받을 때 문자 또는 문자열이 아닌 정수(int)로 받아야 한다.

 

 

풀이 2 : Fail(시간 초과)

import java.io.*;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        HashMap<Integer, Boolean> map = new HashMap();
        int i, n = sc.nextInt();
        for(i=0; i<n; i++) map.put(sc.nextInt(), false);

        int j, m = sc.nextInt();
        for(j=0; j<m; j++) {
            if(map.containsKey(sc.nextInt())) bw.write("1 ");
            else bw.write("0 ");
        }
        bw.flush();
        bw.close();
    }
}

 

 

풀이 2 문제원인 분석

풀이 1과 달리 이번에는 콘솔에 입력되는 숫자를 Scanner 객체의 nextInt() 메서드로 받아 공백을 기준으로 해당 정수 값을 Hashmap 자료구조 Key 값으로 저장했다. 또한 Hashmap 자료구조의 containsKey() 메서드는 () 안 파라미터의 해당하는 값이 자료구조 안에 있는지 여부를 검사하는 메서드인데, 탐색 속도가 매우 빠른 특징을 갖고 있어 기억해야할 숫자와 질문하는 숫자가 일치한지 검사하기 위해 사용했다. 이때 질문하는 숫자 역시 nextInt 메서드로 각각 받았다.

 

하지만 실행결과 이번에는 메모리는 71~72MB로 제한조건 내에 있었지만 실행시간은 6초 정도로 제한조건을 훨씬 상회했다. 이에 대한 원인으로는 Scanner 객체의 nextInt() 메서드의 근본적인 느린 속도가 문제인 것으로 보인다. nextInt()의 경우 콘솔에 입력된 데이터를 공백을 기준으로 int형 데이터를 읽어올 수 있어 편리하지만, Scanner 객체 자체가 복잡한 정규 표현식과 여러가지 부가기능을 포함하고있기 때문에 1천만개 이상의 데이터를 하나씩 모두 읽어 오기에는 오랜 시간이 걸리는 것이다. Scanner 객체 역시 BufferedReader 객체처럼 콘솔에 입력된 데이터를 한 줄 전체를 문자열로 읽어오는 nextLine()이라는 메서드가 있지만 이 역시 아까 전과 동일하게 메모리 초과가 나타난다. 즉, Scanner 객체의 nextInt() 메서드와 같이 숫자만을 읽어오되 빠른 속도로 콘솔 입력 데이터를 읽어오는 방안을 찾아야 한다. 지금까지의 상황을 정리해보면 다음과 같다.

구분	객체	메서드	특성	문제점
출력	BufferedWriter	write	버퍼에 출력 데이터를 전송하고 버퍼 초과 or flush 시 콘솔에 데이터 출력	X
입력	Scanner	nextLine()	콘솔 입력 데이터 한 줄 전체를 문자열로 읽어옴	메모리 초과
입력	Scanner	nextInt()	콘솔 입력 데이터를 공백 기준 정수로 읽어옴	시간 초과
입력	BufferedReader	readLine()	콘솔 입력 데이터 한 줄 전체를 문자열로 읽어 버퍼에  전송하고 버퍼 초과 or 개행 시 프로그램에 해당 데이터 전송	메모리 초과
입력	BufferedReader	read()	콘솔 입력 데이터를 1byte씩 정수로 읽어옴	?

 

지금까지 해당 문제를 풀기 위해 여러 시도를 해봤지만 모두 입력받는 과정에서 시간 초과 또는 메모리 초과가 발생하였다. 이제 남은 유일한 방법은 BufferedReader 객체의 read() 메서드를 이용한 방법이다.

※ C언어의 경우 scanf 함수의 수행 속도가 매우 빠르므로 위 코드와 같은 알고리즘으로 작성 시 무난하게 제한 조건을 만족시키며 동작한다.

 

 

풀이 3 : Success

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        HashMap<Integer, Boolean> map = new HashMap();
        int n = Integer.parseInt(br.readLine());
        int a, mul = 10;
        int temp = br.read();
        while(true){
            a = br.read();
            if (a==32 || a==10) {
                map.put(temp, false);
                temp = 0;
                mul = 1;
                if(a==10) {
                    mul = 10;
                    break;
                }
            } else {
                temp += a*mul;
                mul *= 10;
            }
        }

        int m = Integer.parseInt(br.readLine());
        temp = br.read();
        while(true){
            a = br.read();
            if (a==32 || a==10 || a==-1) {
                if(temp!=0) {
                    if(map.containsKey(temp)) bw.write("1 ");
                    else bw.write("0 ");
                    temp = 0;
                    mul = 1;
                }
                if(a==10 || a==-1) break;
            } else {
                temp += a*mul;
                mul *= 10;
            }
        }
        bw.flush();
        bw.close();
    }
}

 

 

풀이 3 회고

이번에는 BufferedReader 객체의 read() 메서드를 이용하여 풀이에 접근했다. read() 메서드는 콘솔 입력 데이터를 1byte씩 정수형(아스키코드 번호)으로 읽어오기 때문에 원하는 결과를 도출하기 위해서는 이 데이터를 가공 처리할 필요가 있었다. 하지만 해당 문제는 기억해야할 숫자 중에 질문 숫자가 포함되어있는지 여부만 검사하면 되므로 읽어온 데이터 값(아스키코드 번호)을 콘솔 입력 데이터(십진수) 형태와 동일하게 바꾸는 작업을 굳이 할 필요없다. 예를 들면 띄어쓰기 공백(아스키코드 번호 32)이 나타날 때까지 데이터를 하나씩 읽어와(해당 풀이에서는 a 변수로 읽어 오고 있다.) -48 연산을 한 후 문자형으로 변환하고 이들을 합치고 다시 정수형으로 변환하는 등의 작업을 말한다. 그러한 작업의 예시는 다음 코드와 같다.

// 수행 시간을 늘리는 형변환 등 작업들
int a;
int temp = Integer.parseInt(String.valueOf(br.read() - 48));
while(true){
    a = br.read();
    if (a==32 || a==10) {
        map.put(temp, false);
        temp = 0;
        if(a==10) break;
    } else temp = Integer.parseInt(String.valueOf(temp) + String.valueOf(a-48));
}

 

위와 같이 하지않고 단지 read() 메서드로 띄어쓰기 공백(아스키코드 번호 32)이 나타날 때까지 숫자 하나씩 읽어와 임의의 변수(temp)에 누적시켜 더해주면 된다. 띄어쓰기 공백이 나타나면 이를 Hashmap 자료구조 Key에 저장하고, 개행 시(아스키코드 번호 10) 해당 무한 루프(while true)를 나오면(break) 된다. 질문 숫자를 읽어올 때도 똑같이 하되 입력의 끝(-1)을 만난 경우의 조건만 추가시켜주면 된다. 다만 두 자리수 이상의 숫자의 경우는 다음 자리수의 숫자를 읽어올 때마다 10을 곱하여 각각의 값을 표현해주었다. 비록 이러한 실제 문제에 나온대로 데이터가 저장되진 않겠지만 결과를 도출하는데는 전혀 지장이 없으며 오히려 수행 시간을 빠르게 해준다. 아울러, 현재까지 읽어온 정수형 데이터를 Hashmap 자료구조에 저장하는 것 외에는 특별히 메모리를 사용한 것도 없으므로 메모리 소모도 적다.

 

해당 코드로 프로그램을 실행한 결과 약 52MB의 메모리로 제한 조건 128MB의 절반 미만의 메모리만을 사용했으며 수행 시간은 약 2Sec로 제한 조건 4Sec의 절반 정도의 시간이 소요되었다. 결론적으로 코드 길이는 이전 풀이들 보다 길어졌지만 알고리즘의 시간적, 공간적 성능은 이전보다 월등히 높아졌다.

 

 

참고자료

• https://www.codeup.kr/problem.php?id=1430