글 읽기 - 자바 시간초과 어떻게 해결해야할까요?

lms990108 1년 전 0

원래 처음엔 if(map.containsKey(list.get(i))) { map.replace(list.get(i), cnt[i]); } 여기안에 cnt 배열대신 cnt = 1 나올때마다 ++ 하는 방식으로 해결하려했는데

다시 cnt = 1로 초기화를 어디서 시켜야할지 애매해서
cnt[i] = Collections.frequency(list, list.get(i)); 이렇게 그냥 갯수를 세주는 함수를 이용해서 배열로 생성했습니다..

답은 잘 나오는데 시간초과가 뜨네요

아무래도 저 배열에서 문제가 있는거같은데 어떻게 수정해야 시간초과가 안 뜰지 잘 모르겠습니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Baek_10816 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		int m = Integer.parseInt(br.readLine());
		int[] card = new int[m];
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++) {
			card[i] = Integer.parseInt(st2.nextToken());
		}
		
		// 입력 끝
		
		int[] cnt = new int[n];
		for(int i=0; i<n; i++) {
			cnt[i] = Collections.frequency(list, list.get(i));
		}
		
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<n; i++) {
			if(map.containsKey(list.get(i))) {
				map.replace(list.get(i), cnt[i]);
			}else{
				map.put(list.get(i), 1);
			}
		}
		// 상근이 카드 n개를 맵으로. key는 카드숫자, value는 갯수
		
		StringBuilder sb = new StringBuilder();
		
		for(var i : card) {
			if(map.get(i)==null) {
				sb.append(0+" ");
			}else {
				sb.append(map.get(i)+" ");
			}	
		}
		System.out.println(sb);
	}

}

chldn323 1년 전 1

입력받는 값들을 list, card 배열에 저장했다가 다시 HashMap에 넣어줄 필요가 없습니다.

입력받으면서 바로 HashMap에 넣어주고, 개수를 확인하면 됩니다.

제가 작성했던 코드 일부를 첨부합니다.

// 둘째 줄 입력 -> st
int num = Integer.parseInt(st.nextToken());
map.put(num, map.getOrDefault(num, 0) + 1);

// 넷째 줄 입력 -> st
int num = Integer.parseInt(st.nextToken())
sb.append(map.getOrDefault(num, 0)).append(" ");

// 함수 설명
getOrDefault(key, defaultValue); // -> key가 있으면 저장된 값, 없으면 defaultValue 반환

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

문제

문제

출처

ICPC

자바 시간초과 어떻게 해결해야할까요?

lms990108 1년 전 0

chldn323 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말