stonesy

해결방법서로소 집합을 통해 여행 계획인 도시들의 대표자가 모두 같으면 “YES”, 하나라도 다르다면 “NO”를 출력한다.서로소 집합시에 경로 압축 + 랭크 기반 유니온을 사용하면 find 및 union시 거의 상수시간이 소요되므로 O(N+M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;// 160ms, Disjoint Setpublic class Main_1976_G4_여행가자_서로소집합 { static int N; // N: 도시의 수 static int M; // M: 여행 계획에 속한 도시들의 수 static int[][] graph; static int[] plan; static int[] parents; s..

해결방법스택을 이용하여 문제를 O(N)의 시간 복잡도로 해결할 수 있다.핵심은 스택에 자신보다 작은 높이만 유지해야 한다.현재 높이를 스택의 peek() 값과 비교하여, 만약 peek() 값이 현재 높이보다 크다면, 스택에서 해당 값을 pop() 한다. 이때 pop()할 때마다 정답을 증가시킨다.스택에 값을 넣을 때는 다음 조건을 확인한다.현재 높이가 0이 아닌 경우스택의 peek() 값이 현재 높이와 다른 경우 코드import java.util.*;import java.io.*;// 216ms, 스택, O(N)public class Main_1863_G4_스카이라인쉬운거_스택 { public static void main(String[] args) throws IOException{ ..