문자열
❌ 9251번 : LCS (골드5)
- 문제 유형 : dp, String
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 두 문자열의 위치를 나타내는 2차원 int 배열 dp 선언(0으로 초기화, 인덱스는 i, j로 표현)
- 각 문자열의 현재 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]
- 다를 경우 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) -> 현재까지 구한 LCS의 길이를 뜻함
- dp의 마지막 값이 LCS의 길이를 뜻함
⭕️ 9252번 : LCS2 (골드4)
- 문제 유형 : dp, String
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 9251번과 같은 방식으로 dp 배열을 구하고 마지막 값부터 시작하여 dp[i-1][j]와 dp[i][j-1] 중 dp[i][j]가 같은 값이 존재할 경우 해당 위치로 이동
- 같은 값이 없을 경우 해당 위치의 문자를 Stack에 추가 후 dp[i-1][j-1]로 이동 -> 해당 dp의 위치가 두 문자열에서 현재 문자를 찾은 순간이기 때문에 현재 문자를 stack에 추가하고 현재 문자 전 위치의 dp로 이동
⭕️ 5052번 : 전화번호 목록 (골드4)
- 문제 유형 : String, sort
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 문자열을 입력받아 문자열 오름차순 sorting 함
- 정렬된 문자열 배열에서 현재 요소와 다음 요소를 비교햐여 현재 요소가 길이가 더 길면 continue, 길이가 같거나 짧으면 현재 요소의 길이만큼 비교하여 같으면 일관성이 없는 것이기 때문에 "NO" 출력
Union Find
⭕️ 20040번 : 사이클 게임 (골드4)
- 문제 유형 : union-find
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- Union-Find 알고리즘을 이용해서 연결되는 점을 하나의 집합으로 묶어가다가 만약 연결할려는 두 점의 최상위 부모가 같을 경우 사이클이 형성되기 때문에 사이클이 완성된 현재 순서를 출력
⭕️ 16724번 : 피리부는 사나이 (골드3)
- 문제 유형 : graph, dfs, union-find
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 각 노드별로 방향이 정해져 있어 단방향 탐색을하기 때문에 엄밀히 따지면 dfs 탐색을 하게 됨
- 탐색할 때마다 1씩 커지는 인덱스를 탐색을 하면서 방문하는 노드에 채워 넣음
- 동시에 방문 체크를 하면서 탐색하다가 이미 방문한 노드를 만났을 때 해당 노드에 들어있는 숫자가 현재 인덱스와 같으면 현재 경로에 사이클이 발생한 것이기 때문에 세이프존을 한 개 설치하고, 다르면 이미 세이프존이 설치된 사이클에 속하는 경로이기 때문에 세이프존을 설치하지 않음
- 모든 노드를 방문하고 난 뒤의 세이프존 개수를 출력