https://programmers.co.kr/learn/courses/30/lessons/42578 from collections import defaultdict def solution(clothes): answer = 1 clothing=defaultdict(int) for name, kind in clothes: clothing[kind]+=1 for kind in clothing: answer*=(clothing[kind]+1); return answer-1; 처음엔 옷 종류 조합을 구해서 각 옷 종류 별 수를 곱해주려다가, 조합을 사용하니 1번 테케에서 시간초과가 발생했다. 그래서 조합을 사용하지 않고, (옷 종류 별 옷 수+1) 를 옷 종류 별로 다 곱해준다. +1 해준것은 해당 옷 종류를 ..
https://www.acmicpc.net/problem/19236https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net #include #include #include #include using namespace std; int dx[8] = { -1,-1,0,1,1,1,0,-1 }; int dy[8] = { 0,-1,-1,-1,0,1,1,1 }; struct fish { int num; int pos; }; struct info ..
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net #include #include #include #include #include using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int classroom[21][21] = { 0, }; struct info { int like, vacant, row, col; bool operator b.col;//열 오..
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net #include #include #include #include #include using namespace std; int N; int A[21][21]; int ans = 987654321; int graph[21][21]; //x,y,d1,d2 가능한 조건인지 체크 bool isPossible(int x, int y, int d1, int d2) { if (x + d1 + d2 > N) { ret..
https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr from collections import defaultdict, deque def solution(tickets): answer = [] neighbors=defaultdict(list) for start, end in tickets: neighbors[start].append(end) q=deque() q.append((["..
https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3 코딩테스트 연습 - 9주차_전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr adj=[[] for _ in range(101)] visit=[] def dfs(i): visit[i]=True; for t in adj[i]: if not visit[t]: dfs(t) def check(n, visit): cnt=0 for i in range(1,n+1): if visit[i]: cnt+=1 return ..
https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr #include #include #include #include using namespace std; struct { bool operator()(string &first, string &second){ return first.size() < second.size(); } } cmp; bool solution(vector phone_book) { bool a..
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import heapq q=[] V, E=map(int, input().split()) parents=[0] cnt=0 ans=0 def find(a): if parents[a]==a: return a parents[a]=find(parents[a]) return parents[a] def union(a, b): pa=find(a) pb=find(b)..
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net #include #include #include #include #include using namespace std; int N; int populations[11]; vector adj(11); int ans = INT_MAX; bool visit[11]; vector A; vector B; int calc(vector& v){ int sum=0; for (int i=0; i x; adj[i].push_back(x)..
https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net #include #include #include #include #include #include using namespace std; int N; string s; vector operands; vector operators; bool visit[19]; long long ans = (long long) -1 * pow(2, 31); long long calc() { long lo..