최대 선호 음식 질문드립니다.

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

제출하니까 시간초과가 뜹니다. 어디가 잘 못 된건가요??

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

public class Main {
	public static int[] pow, st;
	public static int n,d,k,answer=Integer.MIN_VALUE;
	public static void main(String[] argvs) {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		d=sc.nextInt();
		k=sc.nextInt();
		pow = new int[d+1];
		st = new int[n+1];
		pow[1]=1;
		for(int i=2; i<=d; i++) pow[i] = pow[i-1]*2;
		
		for(int i=1; i<=n; i++) {
			int num, m;
			m=sc.nextInt();
			for(int j=0; j<m; j++) {
				num=sc.nextInt();
				st[i] += pow[num];
			}
		}
		dfs(0,0,0);
		System.out.print(answer);
	}
	public static void dfs(int L, int s, int bit) {
		if(L==k) {
			int cnt=0;
			for(int i=1; i<=n; i++) 
				if((bit&st[i])==st[i])cnt++; //st[i]가 bit의 부분집합이라면 cnt증가
			answer = Math.max(answer, cnt); //최대값 갱신
		}
		else {
			for(int i=s; i<d; i++) { //조합으로 탐색
				dfs(L+1, i+1, bit+pow[i]);
			}
		}
	}
}

안녕하세요, 인프런 AI 인턴입니다.

xogh7532님, 제출하신 코드에서 시간 초과 문제가 발생하는 주된 원인은 반복적인 DFS 호출과 큰 입력 사이즈에서 비효율적인 비트마스킹 연산 때문으로 보입니다. 이를 해결하기 위해 몇 가지 방법을 제안드립니다.

비트 연산 최적화: 현재 코드는 DFS를 통해 모든 가능한 조합을 생성하며, 각 조합에 대해 전체 st[] 배열을 순회하여 조건을 만족하는지 검사합니다. 비트 연산 부분은 최적화가 필요 없어 보이지만, 조합을 생성하는 과정에서 for 문이 d의 크기만큼 반복되기 때문에 이 부분에서의 최적화가 필요할 수 있습니다.
탐색 범위 축소: dfs 함수에서 for 문이 사용되어 d까지 모든 가능한 조합을 탐색하고 있습니다. 하지만, 실제로 필요한 조합만을 탐색하도록 탐색 범위를 축소할 수 있다면 시간을 단축시킬 수 있습니다. 예를 들어, 이미 선택한 요소와 연관 없는 요소는 탐색에서 제외할 수 있습니다.
빠른 입출력 사용: 자바의 경우 Scanner와 System.out.print 대신 BufferedReader와 BufferedWriter를 사용하면 입출력에서 시간을 단축시킬 수 있습니다. 대량의 데이터를 처리할 때는 이 방법이 효율적입니다.

구체적으로, 수업 관련 질문에 대한 자세한 답변은 수업의 Q&A 섹션 혹은 강사님께 직접 문의해보시는 것도 좋은 방법입니다.

수업의 핵심 포인트를 잘 파악하고, 필요한 지식을 바탕으로 문제를 해결하는 과정에서 더 많이 배울 수 있습니다. 계속해서 도전하는 자세가 중요합니다.

원하는 답변을 찾지 못하셨나요?
그럼 우측 하단의 ‘문의하기’ 에서 직접 문의해주세요. 최대한 빠르게 답변드리도록 하겠습니다!

인프런 커뮤니티 질문&답변