글 읽기 - [인간-컴퓨터 상호작용] 50점 맞은 이유를 잘 모르겠습니다.

blashi 1년 전 0

아래 코드는 찾으려는 문자에 대해 누적합 개념으로 int 배열에 저장하는데, 해당 배열들을 MAP을 통해서 접근할 수 있도록 했습니다.

그 이유는 찾아보지 않은 문자의 경우에만 문자 검색 for문을 도는 게 더 효율적이라고 생각해서입니다.

그런데 아래 코드는 50점을 맞았습니다.

그래서 혹시나해서, 시작하자마자 모든 알파벳으로 2차원 int배열에다가 누적합 개념으로 저장해두고 찾도록 코드를 짜봤습니다. 그 코드는 100점이 나왔습니다.

제 생각에는 Map을 통해서 굳이 문제에 안 나오는 문자는 안 찾으면서 진행하면 더 빠를 거 같다고 생각했는데 왜 Map은 50점이 나오는지 알 수 있을까요?

Map의 삽입과 containKey 메소드의 시간복잡도가 O(1)이라고 알고 있기 때문에 크게 느려질 거 같지도 않은데..

가르침 부탁드립니다. 감사합니다.

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		char[] S = bf.readLine().toCharArray();
		int q = Integer.parseInt(bf.readLine());

		Map<Character, int[]> save = new HashMap<>();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			if (i != 0)
				sb.append('\n');

			String[] inputs = bf.readLine().split(" ");
			char c = inputs[0].charAt(0);
			int sidx = Integer.parseInt(inputs[1]);
			int eidx = Integer.parseInt(inputs[2]);
			if (!save.containsKey(c)) {
				int count = 0;
				int[] temp = new int[S.length];
				for (int j = 0; j < S.length; j++) {
					if (S[j] == c)
						count++;
					temp[j] = count;
				}
				save.put(c, temp);
			}
			int[] arr = save.get(c);
			int result = arr[eidx] - (sidx == 0 ? 0 : arr[sidx - 1]);
			sb.append(result);
		}

		System.out.print(sb.toString());
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[인간-컴퓨터 상호작용] 50점 맞은 이유를 잘 모르겠습니다.

blashi 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말