Log

쉬워 보였지만 생각보다 까다로운 문제였다. 0부터 시작해서 N번째 감소하는 수를 찾는 문제. 우선 문제에도 나와있다시피 0은 0번째 감소하는 수, 1은 1번째 감소하는 수이므로 10미만의 입력은 자기 자신이 n번째 감소하는 수가 된다. // 10보다 작은 수는 무조건 감소하는 수 if(N < 10) { System.out.println(N); return; } 그러면 N이 10 이상인 수에 대해서만 몇번째 감소하는 수인지 아닌지 확인하면 된다. 우선 어떤 수가 감소하는 수인지 아닌지를 확인하는 코드가 필요하다. 나는 일의자리부터 마지막자리까지 숫자가 커지지 않으면 false값을, 전부 다 커지는 숫자였으면 true값을 반환하였다. // num값은 10이상이다. public static boolean is..

그냥 크루스칼 알고리즘 문제이지만 같은 성별의 대학교는 연결되면 안된다. 따라서 대학교의 성별을 확인할 수 있는 배열을 만들고, unionSet을 할 때 먼저 대학교 성별이 같으면 false를 반환한다. public static boolean unionSet(int x, int y) { if(gender[x] == gender[y]) return false;// 같은 성별의 대학교인 경우는 union하지 않는다. int xRoot = findSet(x); int yRoot = findSet(y); if(xRoot == yRoot) return false; parents[yRoot] = xRoot; return true; } 간단한 문제였다...!! 코드는 아래와 같다. public class BJ_146..

문제를 읽고 어떤 알고리즘으로 접근해야 맞는 건지 많이 고민했다. 크루스칼 알고리즘 → 입력에 이미 연결된 간선 몇 개가 주어져 있기 때문에 서로소 집합을 이용해야 할 거 같음. 하지만 어떤 간선이 존재하는 지 정보가 없으므로 간선리스트를 정렬할 수 없다. 프림 알고리즘 → 이미 연결된 정점들은 거리를 0, 아닌 정점들은 2차원 좌표계상의 거리로 처리 / 이미 연결된 정점들이 존재하므로 서로소 집합을 이용해볼 생각이였다. 프림 알고리즘에서 minEdge 배열은 신장 트리에서 방문하지 않은 정점까지의 최소 거리를 저장한다. 하지만 신장 트리의 어떤 정점으로부터 최소인지는 알 수 없다. 입력으로 이미 연결된 정점들이 존재하는데 나머지 정점들이 저 연결된 정점들에 union 하려면 어떤 정점으로부터 최소인 ..

입력의 형태가 간선 정보를 주기때문에 크루스칼 알고리즘으로 생각했다. 문제를 보고 가장 처음 든 생각은 어떤 기준으로 두 개의 분리된 마을로 분할할까...? 였다. 그래서 집들의 부분집합을 구해야하나...? → 입력이 너무 커서 백퍼 시간초과이고 간선들을 정렬하고 가장 작은 두 개의 간선을 두 개의 마을로 잡을까? → 1. 두 개의 간선이 같은 집을 가리킬 수 도 있기 때문에 안될 듯... 문제를 다시 한 번 살펴보니 마을에는 집이 하나 이상 있어야 한다.가 눈에 들어왔다. 이 말은 마을에는 집 하나만 있으면 되겠구나... 크루스칼 알고리즘은 간선들을 오름차순으로 정렬하고 그 중에서 사이클이 안생기도록 (정점-1)개의 간선들을 선택하면 모든 정점들이 이어진다. 하지만 여기서 (정점-2)개의 간선들을 연결..

멀티탭의 플러그 빼는 횟수를 최소화하는 문제!! 처음에 생각한 로직 멀티탭에 비어있는 자리가 있으면 : 멀티탭에 추가 멀티탭에 비어있는 자리가 없으면 이미 꽂혀있는 경우 : 무시 멀티탭에 꽂혀있는 기기들의 사용빈도가 제일 낮은 기기를 뺀다. 하지만 이 경우에는 입력이 아래와 같으면 2 5 3 3 1 4 5 두 번째로 들어온 기기3이 2-1로 빠지는 게 아닌 1번으로 빠지게 되므로 오류... 두 번째로 생각한 로직 멀티탭이 비어있지 않고 이미 꽂혀있는 경우 : 무시 멀티탭에 비어있는 자리가 있으면 : 멀티탭에 추가 멀티탭에 비어있는 자리가 없으면 멀티탭에 꽂혀있는 기기들의 사용빈도가 제일 낮은 기기를 뺀다. 하지만... 이 경우에도 입력이 아래와 같으면 2 7 2 3 1 2 1 2 3 3 3 처음 기기1이..

아주아주아주 짜증나게 했던 문제..^^.. --리뷰는 나중에 추가-- import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BJ_11725 { static LinkedList[] node; // 인접리스트로 간선끼리 연결된 노드 정보 static int[] parentNode; // 2부터 N까지 부모노드 정보 static int N; // 입력받는 수 public static void main(String[] arg..