Algorithm44 [알고리즘] 프로그래머스 - 순위 1. 문제 2. 나의 풀이 어떻게 풀어야할지 감을 못잡아서 여러 풀이 방법을 찾아 보았는데 플로이드-와샬 알고리즘을 사용해서 푸는 문제 였다. A가 B를 이기고 B가 C를 이길 경우 A가 C를 이긴다는 형태로 접근을 해야한다. 우선 그래프에서 입력으로 온 경기 결과를 입력해준다. 그리고 플로이드-와샬 알고리즘을 이용하여 하나의 노드에서 다른 노드로 갈 수 있는 경로가 있는지 파악한다. 만약 a노드에서 b노드로 갈 수 있다면 a는 b를 이긴 것이다. 역으로 b는 a한테 진 것이다. 플로이드-와샬 알고리즘을 수행하고 나면 graph에는 각 선수끼리 싸웠을 때 누가 이기고 졌는지의 결과가 저장되있거나, graph[i][j] = false, graph[j]i[] = false 라면 결과를 알 수 없는 경우 이다.. 2021. 3. 24. [알고리즘] 2018 카카오 블라인드 - 프렌즈4블록 1. 문제 2. 문제 풀이 블록을 아래로 내리는 부분이 좀 까다롭고 나머지는 문제에 주어진대로 풀면 되는 문제였다. 1. 주어진 1차원 배열을 2차원 배열로 옮긴다. 2. 2*2영역이 같을 경우 해당 영역을 check 2차원 배열에 true로 표시한다. 3. check 2차원 배열에 true로 표시된 공간을 블록이 터졌다는 의미로 "*"로 바꾼다. 4. 블록을 터트린 후 위에 있던 블록들을 아래로 내린다. 블록을 내리는 downBlock() 메서드의 경우 하나라도 내려간 블록이 있으면 해당 열의 블록을 내리는 작업을 다시 반복하였다. 내려가는 블록이 없을 경우 다음 열을 검사한다. import java.util.*; class Solution { public static int solution(int m.. 2021. 2. 3. [알고리즘] 2018 카카오 블라인드 - 뉴스 클러스터링 1. 문제 2. 문제 풀이 HashMap을 이용하면 풀 수 있는 간단한 문제였다. 이 문제의 포인트는 합집합을 구할 때는 2개의 집합중 key의 개수가 더많은쪽을 합집합의 사이즈에 더해주면되고 교집합을 구할 때는 2개의 집합중 key의 개수가 더 작은쪽을 교집합의 사이즈에 더해주면 된다. 마지막에 answer을 계산 할 때는 합집합과 공집합의 사이즈가 모두 0일 경우 집합 A와 집합 B가 정의되지 않으므로 J(A,B)는 1로 정의한다. import java.util.*; class Solution { static int answer = 0; public static int solution(String str1, String str2) { //1. 소문자 변환 str1 = str1.toLowerCase().. 2021. 2. 1. [알고리즘] 가장 먼 노드(그래프) 1. 문제 2. 나의 풀이 그래프를 bfs 알고리즘을 이용해서 풀었다. 처음에는 노드의 번호와 1번으로부터 해당 노드까지의 edge 길이를 저장하는 Node 클래스를 선언해서 사용했는데 8,9번쪽에서 메모리 초과 오류가 나서 Integer를 사용하였고 edge 길이의 경우 dist 배열을 하나 선언하여 1번부터 해당 노드까지 이동하는데 드는 비용을 저장했다. 이렇게 변경 후에도 메모리 오류가 나서 graph의 경우는 방문했다 안했다만 저장하면 되므로 int[][] graph에서 boolean[][] graph로 변경하였다. import java.util.*; class Solution { private static int max = -1; private static int maxCount = 0; pub.. 2021. 1. 20. [알고리즘] [2020 카카오 블라인드] 괄호 변환 1. 문제 문제를 딱 보면 엄청나게 많은 조건들이 있다. 사람은 한번에 여러가지를 기억하지 못하기 때문에 조건을 이해하는데 시간이 오래 걸렸다. 2. 나의 풀이 문제를 봤을 때 재귀를 이용하는 문제라는 것을 알았다. 우선 문제의 조건대로 주어진 문자열의 길이가 0일 경우 빈 문자열을 반환하게 하고, 현재 문자열이 올바른 괄호 문자열일 경우 해당 문자열을 그대로 반환했다. 또한 문자열 u는 균형잡힌 괄호 문자열이므로 문자열 w를 u와 v로 나누어주는 getBalanceIndex() 메서드를 만들어 주었다. 여기서 return할 때 1을 더해주어 문자열 u와 v를 구분하는 인덱스를 구한다. 그리고 u가 올바른 괄호 문자열일 경우는 문자열 u에 v를 다시 나누는 재귀함수를 호출해서 더해준다. u가 올바른 괄호.. 2021. 1. 18. [알고리즘] [2020 카카오 블라인드] 문자열 압축 1. 문제 2. 나의 풀이 처음에 리스트에 단어를 넣지 않고 현재 단어와 다음 단어를 구해서 풀려고 했더니 인덱스를 벗어나는 등의 엄청난 시간 낭비가 있었다. 비효율적이지만 푸는게 우선이니 스트링 리스트를 먼저 하나 선언하고 리스트에 단어를 집어 넣는데, 마지막 단어의 경우는 남은 단어를 모두 넣도록 처리했다. 리스트에 넣은 단어가 현재 인덱스의 단어와 뒤의 단어를 비교해서 같을 경우 몇개가 같은지 개수를 세어 주었고, 같지 않은 경우는 count가 1일 경우와 1보다 클 경우로 나누어서 문자열 앞에 숫자를 붙여줄지 안붙여줄지를 정하였다. 그리고 마지막 단어의 경우는 마지막 단어와 그 앞의 단어가 같은 경우와 같지 않은 경우로 구분하여 숫자를 붙여줄지 안붙여줄지를 정하였다. import java.util.. 2021. 1. 18. 이전 1 2 3 4 5 ··· 8 다음
