22년 1월 1주차 회고록 (스터디 자랑)

import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { static int sum = 0; static Set<Character> set = new HashSet<>(); static int k; public static void dfs(String words) { for (int i = 0; i < words.length(); i++) { if (!set.contains(words.charAt(i)) && k > 0) { set.add(words.charAt(i)); k--; } } if (checkWords(words)) sum++; } public static boolean checkWords(String word) { for (int i = 0; i < word.length(); i++) { if (set.contains(word.charAt(i))) continue; else if (!set.contains(word.charAt(i))) return false; } return true; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); k = sc.nextInt(); //nextInt()가 개행문자를 제거하지 않는다.... //nextLine을 한번 더해주니 에러해결. sc.nextLine(); String[] words = new String[n]; k -= 5; set.add('a'); set.add('n'); set.add('t'); set.add('i'); set.add('c'); for (int i = 0; i < n; i++) { words[i] = sc.nextLine(); dfs(words[i]); } System.out.println(sum); } }

import sys from itertools import combinations nums = sys.stdin.readline().split(" ") word_num = int(nums[0]) letter_num = int(nums[1]) words = [""]*(word_num) total_word = "" for i in range(word_num): word = sys.stdin.readline().replace("\n", "").replace("a", "").replace("n", "").replace("t", "").replace("i", "").replace("c", "") words[i] = words[i] + word total_word = total_word + word print(words) def max_word_count(total_word, words, letter_num): # print(letter_num) if (letter_num < 5): return 0 letter_set = set(total_word) # 전체 알파벳 word_counts = [] for combi in combinations(letter_set, letter_num-5): count = 0 for word in words: # print(combi) # print(word) if (set(word) & set(combi) == set(word)): count += 1 word_counts.append(count) return max(word_counts) print(max_word_count(total_word, words, letter_num))

import sys from itertools import combinations nums = sys.stdin.readline().split(" ") word_num = int(nums[0]) letter_num = int(nums[1]) words = [""]*(word_num) total_word = "" for i in range(word_num): word = sys.stdin.readline().replace("\n", "").replace("a", "").replace("n", "").replace("t", "").replace("i", "").replace("c", "") words[i] = words[i] + word total_word = total_word + word # print(words) def can_read_words(data, learned, letter_set): count = 0 for word in data: can_read = 1 for letter in word: if learned[letter_set.index(letter)] == 0: can_read = 0 break if can_read == 1: count += 1 return count def max_word_count(total_word, words, letter_num): # print(letter_num) answer = 0 if (letter_num < 5): return 0 letter_set = list(set(total_word)) # abcdef learned = [0]*len(letter_set) # 010101 for combi in combinations(letter_set, letter_num-5): count = 0 for letter in combi: learned[letter_set.index(letter)] = 1 count = can_read_words(words, learned, letter_set) if count > answer: answer = count for letter in combi: learned[letter_set.index(letter)] = 0 return answer print(max_word_count(total_word, words, letter_num)

import math def solution(brown, yellow): a = (brown + 4) / 2 b = brown + yellow answer = [int((a + math.sqrt(a**2 - 4*b))/2)] answer.append(int(b/answer[0])) return answer print(solution(8,1))

from itertools import combinations def solution(N, K, letters, all_letters): if(K - 5 < 0): return 0 num_read = [] for combi in combinations(all_letters, K - 5): count = 0 for j in range(len(letters)): if not letters[j] - set(combi): count += 1 num_read.append(count) return max(num_read) N, K = map(int, input().split()) letters = [] all_letters = set() for i in range(N): tmp_set = set(input())-set("antatica") if len(tmp_set) > K - 5 : continue all_letters = all_letters.union(tmp_set) letters.append(tmp_set) print(solution(N,K,letters,all_letters))

import sys from itertools import combinations def input(): return sys.stdin.readline().rstrip() N, K = map(int, input().split()) word = [input() for _ in range(N)] # 배워야 하는 글자 basic = {"a","n","t","i","c"} learnNum = K - len(basic) if learnNum < 0: print(0) exit() if K == 26: print(N) exit() wordSetList = [] for w in word: if len(set(list(w))-basic) > learnNum: continue else: wordSetList.append(set(list(w))-basic) toLearn = set() for wo in wordSetList: toLearn = toLearn | wo if len(toLearn) <= learnNum print(N) exit() alphComb = combinations(toLearn,learnNum) cntList = [] for comb in alphComb: cnt = 0 for wordSet in wordSetList: if len(wordSet - set(comb)) == 0: cnt += 1 cntList.append(cnt) print(max(cntList))

Set을 통해서 중복을 제거할 수 있으니 다른 알고리즘에서도 잘 활용하자.

다른 분들의 풀이를 보았을 때 비슷하게 로직을 구성했지만 리스트에서 원소의 위치를 찾아낸 부분에서 시간이 오래걸렸을 것 같다는 생각이 든다. 그 부분을 보완할 수 있는 방안을 여러개 정리해야할 것 같다.

1. 저렇게 수식을 구현해서 풀면 코딩테스트에는 문제가 없을 것 같은데, 면접에서는 설명하기가 좀 곤란할 것 같다. 2. 시간 복잡도를 좀 더 생각해보는 연습을 해야 할 것 같다.

BFS에서 시간 복잡도를 줄이는 방식에 대해 조금 더 공부를 해봐야할 것 같습니다...!

메소드를 따로 분리해 놓으니 가독성이 좋아진것같다. 어떻게 하면 더 가독성이 좋아질지 고민해보는것도 좋겠다

.replace()와 .index() 함수 자체가 리스트를 탐색하다보니 여기에서 메모리 초과가 발생했던 것 같다 아스키 코드를 이용하는 등 다양한 방법을 통해 탐색하는 과정 없이 사용해보자

다른 분들 코드를 보니 메소드를 의미있는 단위끼리 잘 분리하고 사용하신 것 같아서 배우게 되었다.

pypy를 사용하면 시간이 더 줄일 수 있다는 인사이트를 얻었습니다!

시간복잡도와 공간복잡도에 대한 공부를 더 해봐야겠다.

알고리즘 문제는 몸에 익은대로, 편한 방법으로 푸는 경우가 많은 것 같다. 그래서 어떻게 풀이를 할 지 정리하는 것이 중요하지 않을까라는 생각이 들었다.

시간초과가 날때는 진짜 좀 당황스러운 것 같다.

알고리즘... 이제 정말 미루면 안되겠다는 생각을 한 번 더 뼈저리게 느꼈습니다 🥲