[Java] BOJ 4929 수열 걷기

4929번: 수열 걷기

---

오답 코드

• 입력받은 데이터를 map에 list형태로 저장
• list를 순회하면서 가장 큰 값 구하는 구조
• 최대 10,000번 재귀로 인해 메모리 초과 발생

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

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

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            if (N == 0) {
                break;
            }

            Short[] arr = new Short[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Short.parseShort(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            Short[] brr = new Short[N];
            for (int i = 0; i < N; i++) {
                brr[i] = Short.parseShort(st.nextToken());
            }

            HashMap<Short, List<Short>> map = new HashMap<>();
            Short[] root = new Short[] { arr[0], brr[0] };
            for (int i = 0; i < arr.length - 1; i++) {
                map.put(arr[i], new ArrayList<>());
                map.get(arr[i]).add(arr[i + 1]);
            }

            for (int i = 0; i < brr.length - 1; i++) {
                if (!map.containsKey(brr[i])) {
                    map.put(brr[i], new ArrayList<>());
                }
                map.get(brr[i]).add(brr[i + 1]);
            }
            bw.write(Math.max(calc(map, root[0], root[0]), calc(map, root[1], root[1])));
            bw.write("\n");
        }
        bw.flush();
    }

    private static short calc(HashMap<Short, List<Short>> map, Short key, Short sum) {
        if (map.containsKey(key)) {
            short max = 0;
            for (short i : map.get(key)) {
                max = (short) Math.max(max, calc(map, i, (short) (sum + i)));
            }
            return max;
        } else {
            return sum;
        }
    }
}

---

정답 코드

• 겹치는 부분까지 최대값 구하기
• 마지막 겹치는 부분에서 끝 지점까지 거리 최대값 구하기

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

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));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            if (N == 0) {
                break;
            }

            HashSet<Integer> set = new HashSet<>();
            List<Integer> list1 = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(st.nextToken());
                list1.add(num);
                set.add(num);
            }

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            List<Integer> list2 = new ArrayList<>();

            List<Integer> same = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(st.nextToken());
                list2.add(num);
                if (set.contains(num)) {
                    same.add(num);
                }
            }

            int max = 0;
            if (same.size() > 0) {
                for (int i = 0; i <= same.size(); i++) {
                    int point = same.get(i);
                    int max1 = getMax(list1, i == 0 ? 0 : list1.indexOf(same.get(i - 1)), list1.indexOf(point));
                    int max2 = getMax(list2, i == 0 ? 0 : list2.indexOf(same.get(i - 1)), list2.indexOf(point));
                    max += Math.max(max1, max2);
                }
            } else {
                int max1 = getMax(list1, 0, list1.size());
                int max2 = getMax(list2, 0, list2.size());
                max += Math.max(max1, max2);
            }

            bw.write(Integer.toString(max));
            bw.write("\n");
        }
        bw.flush();
    }

    private static int getMax(List<Integer> list, int s, int e) {
        int sum = 0;
        for (int i = s; i < e; i++) {
            sum += list.get(i);
        }
        return sum;
    }
}