[2022 하계 모각코] 4주차 1회 계획 및 결과

4주차 1회 계획 : 컬렉션 프레임워크(collection framework(Map, Stack)) 공부

---

이번주는 Map, stack, queue에 대한 공부를 하려 한다.

고등학교 친구, 같은 과 선배들과 백준 문제를 통해 Stack에 대한 개념을 알고 있다. 또한 Map은 조금 찾아보니 Python의 딕셔너리와 같은 개념인지라 이번 시간에는 개념은 가볍게 보고, 관련 문제를 풀이해보는 시간을 가지려고 한다.

---

Map은 수학 시간에 배운 함수에서 대응된다 혹은 상을 맺는다(map, mapping)에서 따온 말이라고 한다.

Map의 저장 방식은 'key-value'이다. 그래서 어떤 자료를 찾아보고자 한다면 앞부터 순차적으로 탐색하는 것이 아니라 찾으려는 곳만 펼쳐본다고 한다. 이런 글을 보고선 본래 자료는 특이한 케이스가 아니라면 선형탐색을 통해 찾아봐야 하는 것이 아닌가 싶었다.

예를 들어 (1,1), (2,213), (3,2891) 라는 Entry(두 개의 값이 있는 pair, key-value)가 있다고 하자. 이 Entry를 Map에 넣을 때(put) 맵 안에 배열이 [0,0,0,0] 에서 [0, 1, 213, 2891]이 된다고 한다.

배열의 인덱스를 통해 자료에 접근하는 것이기 때문에 O(1)의 시간이 든다고 한다.

---

HashMap<String, String> HMap = new HashMap<String, String>();

위는 HashMap을 선언하는 코드이다. 위 코드를 보면 <> 사이에 제네릭이 있어, 타입 변수를 입력해주어야 한다.

다른 메서드들은 모두 여기를 통해 알 수 있었다. 문제를 풀기 위해서 필요한 메서드만 찾아 사용했기 때문에 모든 메서드를 아는 건 아니지만 참고하기에 좋은 문서라고 생각했다.

아래 더보기를 누르면 문제풀이를 한 내용을 볼 수 있다.

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

1620번: 나는야 포켓몬 마스터 이다솜

위 문제는 백준 사이트에 있는 문제로, '단계별로 풀어보기' - '집합과 맵' 에 있는 문제이다. 오늘 공부한 Map을 제대로 이해하고 있는지, 그리고 활용하기 좋은지 등을 알기 위해 풀어보았다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main{

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int PoketmonNum = Integer.parseInt(st.nextToken());
        int QuestionNum = Integer.parseInt(st.nextToken());

        // key에 대한 배열 만들기
        String[] Poketmons = new String[PoketmonNum];

        // 포켓몬 입력
        HashMap<String, Integer> map = new HashMap<>();
        String input;
        for (int i=1; i<=PoketmonNum; i++){
            input = br.readLine();
            Poketmons[i-1] = input;
            map.put(input, i);
        }

        // 문제에 대한 정답을 buffer에 입력
        for (int i=0; i<QuestionNum; i++){
            input = br.readLine();
            if (map.containsKey(input)){
                bw.write(map.get(input)+"\n");
            }else{
                bw.write(Poketmons[Integer.parseInt(input)-1]+"\n");
            }
        }
        // 정답 출력
        bw.flush();
        bw.close();
    }
}

기존에 파이썬으로 많이 익숙해져 있던 탓인지 금방 적용하여 문제를 풀 수 있었다.

입력으로 주어지는 포켓몬의 이름들은 모두 입력 순서와 대응시켜 key-value로 map에 넣었다. 그래서 포켓몬 이름을 입력하면 포켓몬 순서에 금방 접근할 수 있게 했다. 하지만 반대로, 포켓몬 순서를 입력했을 때 포켓몬 이름을 Map을 통해서 접근하기는 불가능하다. 그래서 이를 해결하는 방법으로 택한 것이 포켓몬 이름에 대한 배열을 하나 만드는 것이었다. 포켓몬 순서가 입력으로 주어진다면 배열에서 포켓몬 이름에 대해 인덱스로 접근하는 것이 가능하기 때문에 O(1)의 시간밖에 들지 않는다. 그래서 시간 초과 문제가 일어나지 않는다. 

글을 쓰는 와중에 든 생각이다. '만약 배열 하나만 가지고서 이 문제를 풀려고 했다면 어땠을까?' 하는 의문이다. 배열만으로 이 문제를 풀려 든다면 아마 선형탐색(순차탐색) 방법을 써야만 한다. 왜냐하면 입력 순서대로 포켓몬 순서가 되기 때문에 포켓몬 이름을 알파벳 순으로 정렬할 수도 없기 때문이다. 그렇기 때문에 k 번째 포켓몬 이름은 배열의 인덱스 접근을 통해 O(1) 만에 접근이 가능하지만 포켓몬의 순서를 묻는다면 순차적으로 탐색하며 입력과 이름을 비교하는 과정을 거쳐야 한다. 그럼 최악의 경우는 배열의 처음부터 끝까지 다 뒤져보는 경우가 될 것이다. 

정리해보겠다. 입력으로 주는 N, M의 범위는 1~100,000 이다. N은 배열에 입력하는 것이므로 N으로 10만이 주어지더라도 6초라는 제한 시간에는 흠집조차 내지 못한다. 하지만 N이 10만으로 주어졌을 때 M 또한 10만으로 주어진다면 얘기는 다르다. 최악의 경우 길이가 10만 인 배열의 처음부터 끝까지 10만 번 찾아보는 불상사가 발생하게 되면 100,000 * 100,000인 10,000,000,000(100억) 번을 찾아보게 되어 시간 초과에 걸리게 된다. 그래서 시간 초과에 걸리지 않기 위해선 시간이 상수 시간으로 걸리는 인덱스 접근이 가능한 Map을 통해 풀어야 하는 것이다.

(1초에 1억 번을 돈다고 하니, 100억 번이면 100초가 필요하다. 하지만 이 문제는 자바는 6초의 시간만 주고 있다.)

---

• Stack

스택은 선입 후출, 혹은 후입 선출을 하는 자료구조의 개념 중 하나이다. 영어로는 LIFO(Last In First Out)이라고 하니 후입 선출로 외워두는 게 나중 가서도 덜 헛갈릴 것 같다.

Stack은 자바를 사용하는 데에 있어서 필수적이다. 자바는 메모리를 관리하는 곳이 세 군데나 있다. 하나는 Heap 영역, Method영역, 마지막 하나는 Stack영역이다. Stack 영역에서는 프로그램에서 실행되고 있는 메서드들을 실행 순서대로 바닥부터 차곡차곡 쌓아두는 곳이다. 그리고 메서드가 종료되면 Stack영역에서 사라진다.

아래 더보기를 누르면 문제풀이를 한 내용을 볼 수 있다.

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

10773번: 제로

Stack을 공부하며 이 문제도 풀어보았다.

아래는 java.util의 stack을 불러와서 풀이한 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
    static int sToi(String s){return Integer.parseInt(s);}
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack<Integer> st = new Stack<>();
        int n = sToi(br.readLine());
        for (int i=0; i<n; i++){
            int input = sToi(br.readLine());
            if (input == 0){
                st.pop();
            }else{
                st.push(input);
            }
        }

        int ans = 0;
        while (st.iterator().hasNext()){
            ans += st.pop();
        }
        System.out.println(ans);
    }
}

아래는 내가 직접 stack을 구현해서 풀이한 코드이다. stack 개념에서 필요한 부분만 가져와서 작성한 코드이다 보니 위의 코드보다 메모리도 적게 소모하고, 시간도 약 60ms 정도 더 빠르게 작동했다. 하지만 보통 직접 구현한 stack은 java.util의 stack보다 느린데 이번 문제가 특이 케이스라고 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    static int sToi(String s){return Integer.parseInt(s);}
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = sToi(br.readLine());
        int[] arr = new int[testCase];
        int input;
        int idx = 0;
        for (int i=0; i<testCase; i++){
            input = sToi(br.readLine());
            if (input == 0){
                idx--;
                arr[idx] = 0;
            }else{
                arr[idx] = input;
                idx++;
            }
        }
        int ans = 0;
        for (int elem : arr){
            if (elem == 0){break;}
            ans += elem;
        }
        System.out.println(ans);
    }
}