[BOJ-1062] 가르침

 

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

1062번: 가르침

---

[코드-java]

import java.util.Scanner;
import java.lang.*;

public class Main{
	//알파벳을 배웠는지 확인함.
    public static boolean isLearn[]=new boolean[26];
	public static int N,K;
	public static int MAX_LEARN=0;
	public static String[] words=new String[50];
	
	public static void learnAlphabet(int alpha, int learn_cnt) 
	{
		
		if(learn_cnt==K)  //배운알파벳 개수가 K개인가?
		{
			int tmp=0;
			//단어 N개를 읽을 수 있는지 테스트한다.
			for(int i=0; i<N; i++)
			{
				boolean isfinished=true; //아직은 다배운상태라고 가정하면
				for(int j=0; j<words[i].length(); j++) 
				{
					char charValue=words[i].charAt(j);
					//만일 words[i]의 j번째 알파벳을 배우지 않았다면
					//charAt(index): 주어진 인덱스의문자를 리턴한다.
					if(!isLearn[charValue-'a']) {
						//아직 배운상태가 아니다.
						isfinished=false;
						break;
					}
				}
				//단어 1개의 모든 알파벳을 안다면
				if(isfinished)
					tmp++;
			}
			//단어 N개를 모두 테스트했다면
			//최대로 읽을 수 있는 단어개수가 몇인지를 알아야한다.
			MAX_LEARN=Math.max(MAX_LEARN, tmp);
			return;//강제종료를 해야한다.
		}
		
		//K개가아니라면 계속 알파벳을 배운다.
		else 
		{
            //alpha부터~ z까지 모든 알파벳을 배운다.
			for(int i=alpha; i<26; i++)
			{
				if(!isLearn[i]) {
					isLearn[i]=true;
					learnAlphabet(i, learn_cnt+1);
					isLearn[i]=false; 
					//만일 K개가되어 다른 알파벳을 더이상 배울 수 없다면
					//아직 최대로 읽을수있는 단어개수를 못구한 것을 대비해서..
				}
			}
		}
	}
		
	
	public static int solution() {
		Scanner sc =new Scanner(System.in);
		N= sc.nextInt();
		K= sc.nextInt();
		//a,c,i,n,t 를 배울 수 없다면
		if(K<5)
			return 0;
		
		//모든 단어를 읽을 수 있다.
		else if(K==26)
			return N;
		
		//anta, tica를 제외한 단어를 배운다.
		for(int i=0; i<N; i++) {
			String word=sc.next();
			word=word.replace("[antic]", "");
			words[i]=word;
		}
		
		//a,c,i,n,t는 배운상태로한다.
		//words에 배운단어가 있는지 알아본다.
		char acint[]= {'a','c','i','n','t'};
		for(int i=0; i<acint.length; i++)
			isLearn[acint[i]-'a']=true;
		
		//알파벳을 배운다.
		K-=5; //앞의 a,c,i,n,t를 제외한 나머지를 배운다.
		learnAlphabet(0,0);
		return MAX_LEARN;
	}

	public static void main(String[] args) {
		System.out.println(solution());
	}
}

---

 

[코드-python]

import sys
input=sys.stdin.readline

N,K=0,0
isLearn=[False]*26
words=[]
MAX_LEARN=0

#알파벳을 가르친다.
#a~z까지 가르쳐본다.
def learn_alpha(alpha, learn_cnt):
    global N,K, isLearn, words, MAX_LEARN
    #현재 배운 단어개수가 K-5개인가?
    if learn_cnt==K-5:
        #현재 K-5개의 단어로 조합해서 최댓값을 찾는다.
        tmp=0
        for word in words:
            flag=True
            for w in word:
                #아직 남극언어 단어에 가르치지 않은 단어가 존재한다면
                if not isLearn[ord(w)-ord('a')]:
                    flag=False
                    break
            #K-5개의 단어가 모두 존재한다면
            if flag:
                tmp+=1
        MAX_LEARN=max(tmp,MAX_LEARN)
        return 

    #아직 K-5개가아니면
    for i in range(alpha,26):
        #아직 배우지 않은 상태면
        if not isLearn[i]:
            isLearn[i]=True #배운다.
            learn_alpha(i, learn_cnt+1)
            isLearn[i]=False #다음단어를 배우기위해서 False를 한다.

def solution():
    global N,K, isLearn, words
    N,K=map(int, input().strip().split())
    #선생님이 가르치는 글자수는 최소 5개(a,n,t,c,i)이다.
    if K<5:
        return 0

    #선생님이 가르치는 글자수가 26자라면
    #학생들음 모든 단어를 읽을 수 있다.
    elif K==26:
        return N

    for _ in range(N):
        word=input().strip()
        words.append(word.replace("antci",""))
        
    #먼저 a,c,i,n,t 5개는 가르쳤다고 치자.
    isLearn[ord('a')-ord('a')]=True
    isLearn[ord('c')-ord('a')]=True
    isLearn[ord('i')-ord('a')]=True
    isLearn[ord('n')-ord('a')]=True
    isLearn[ord('t')-ord('a')]=True

    #나머지 알파벳 K-5개를 배운다.
    learn_alpha(alpha=0,learn_cnt=0)
    return MAX_LEARN

def main():
    print(solution())
    

if __name__=='__main__':
    main()

ㅠㅠㅠ... 와... 119000KB...? 미쳤네...

---

논리적으로는 문제가 없으나, 테스트를 돌려봤지만,,,, 시간초과로 뜬다.

이유알았다.. alpha부터 시작해야한다!

그런데 이 아래 코드는 그냥 a부터 ~z까지 시작한것이다.. 그러니 시간 초과가 뜰수밖에!

 

[실패코드-JAVA]

import java.util.Scanner;
import java.lang.*;

public class Main {
	//알파벳을 배웠는지 확인함.
	static boolean isLearn[]=new boolean[26];
	static int N,K;
	static int MAX_LEARN=0;
	static String[] words=new String[50];
	
	public static void learnAlphabet(int alpha, int learn_cnt) 
	{
		
		if(learn_cnt==K)  //배운알파벳 개수가 K개인가?
		{
			int tmp=0;
			//단어 N개를 읽을 수 있는지 테스트한다.
			for(int i=0; i<N; i++)
			{
				boolean isfinished=true; //아직은 다배운상태라고 가정하면
				for(int j=0; j<words[i].length(); j++) 
				{
					
					char charValue=words[i].charAt(j);
					//만일 words[i]의 j번째 알파벳을 배우지 않았다면
					//charAt(index): 주어진 인덱스의문자를 리턴한다.
					if(!isLearn[charValue-'a']) {
						//아직 배운상태가 아니다.
						isfinished=false;
						break;
					}
				}
				//단어 1개의 모든 알파벳을 안다면
				if(isfinished)
					tmp++;
			}
			//단어 N개를 모두 테스트했다면
			//최대로 읽을 수 있는 단어개수가 몇인지를 알아야한다.
			MAX_LEARN=Math.max(MAX_LEARN, tmp);
		}
		
		//K개가아니라면 계속 알파벳을 배운다.
		else 
		{
			for(int i=0; i<26; i++)
			{
				if(!isLearn[i]) {
					isLearn[i]=true;
					learnAlphabet(i, learn_cnt+1);
					isLearn[i]=false; 
					//만일 K개가되어 다른 알파벳을 더이상 배울 수 없다면
					//아직 최대로 읽을수있는 단어개수를 못구한 것을 대비해서..
				}
			}
		}
	}
		
	
	public static int solution() {
		Scanner sc =new Scanner(System.in);
		N= sc.nextInt();
		K= sc.nextInt();
		//a,c,i,n,t 를 배울 수 없다면
		if(K<5)
			return 0;
		
		//모든 단어를 읽을 수 있다.
		else if(K==26)
			return N;
		
		//anta, tica를 제외한 단어를 배운다.
		for(int i=0; i<N; i++) {
			String word=sc.next();
			word=word.replace("[antic]", "");
			words[i]=word;
		}
		
		//a,c,i,n,t는 배운상태로한다.
		//words에 배운단어가 있는지 알아본다.
		char acint[]= {'a','c','i','n','t'};
		for(int i=0; i<acint.length; i++)
			isLearn[acint[i]-'a']=true;
		
		//알파벳을 배운다.
		K-=5; //앞의 a,c,i,n,t를 제외한 나머지를 배운다.
		learnAlphabet(0,0);
		return MAX_LEARN;
	}

	public static void main(String[] args) {
		System.out.println(solution());
	}

}

---

[실패코드-Python]

import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

N,K=0,0
isLearn=[False]*26
words=[]
MAX_LEARN=0

#알파벳을 가르친다.
#a~z까지 가르쳐본다.
def learn_alpha(alpha, learn_cnt):
    global N,K, isLearn, words, MAX_LEARN
    #현재 배운 단어개수가 K-5개인가?
    if learn_cnt==K-5:
        #현재 K-5개의 단어로 조합해서 최댓값을 찾는다.
        tmp=0
        for word in words:
            flag=True
            for w in word:
                #아직 남극언어 단어에 가르치지 않은 단어가 존재한다면
                if not isLearn[ord(w)-ord('a')]:
                    flag=False
                    break
            #K-5개의 단어가 모두 존재한다면
            if flag:
                tmp+=1
        MAX_LEARN=max(tmp,MAX_LEARN)
        return 

    #아직 K-5개가아니면
    for i in range(26):
        #아직 배우지 않은 상태면
        if not isLearn[i]:
            isLearn[i]=True #배운다.
            learn_alpha(i, learn_cnt+1)
            isLearn[i]=False #다음단어를 배우기위해서 False를 한다.

def solution():
    global N,K, isLearn, words
    N,K=map(int, input().strip().split())
    #선생님이 가르치는 글자수는 최소 5개(a,n,t,c,i)이다.
    if K<5:
        return 0

    #선생님이 가르치는 글자수가 26자라면
    #학생들음 모든 단어를 읽을 수 있다.
    elif K==26:
        return N

    for _ in range(N):
        word=input().strip()
        words.append(word[4:len(word)-4])
        
    #먼저 a,c,i,n,t 5개는 가르쳤다고 치자.
    isLearn[ord('a')-ord('a')]=True
    isLearn[ord('c')-ord('a')]=True
    isLearn[ord('i')-ord('a')]=True
    isLearn[ord('n')-ord('a')]=True
    isLearn[ord('t')-ord('a')]=True

    #나머지 알파벳 K-5개를 배운다.
    learn_alpha(alpha=0,learn_cnt=0)

def main():
    solution()
    print(MAX_LEARN)

if __name__=='__main__':
    main()