본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준1568 - 새 처음에 문제가 이해 잘 안되서 몇번을 읽어본 것 같다. 문제를 풀어보면, N마리가 1,2,3,4...로 날아가는데 만약 다음 날아가야할 숫자보다 현재 남아있는 새의 숫자가 작으면 다시 1부터 날아간다. 한번 날아갈 때 마다 1이 걸린다고 했을 때, 총 몇초가 걸리는지 문제이다. 1마리가 날아가면 13마리가 남는다. 2마리가 날아가면 11마리가 남는다. 3마리가 날아가면 8마리가 남는다. 4마리가 날아가면 4마리가 남는다. 1마리가 날아가면 3마리가 남는다. --> 여기서 조건이 걸리게 되므로 다시 날아가야할 마리수가 1로 초기화 됨 2마리가 날아가면 1마리가 남는다. 1마리가 날아가면 0마리가 남는다. import java.util.*; public class Main { public static voi.. 2019. 7. 5.
[알고리즘 문제] 백준1543 - 문서검색 문제는 문자열에서 단어가 중복없이 최대 몇번 나오는지 검사하는 문제이다. 여기서 중복이란 문자열 ababababa에서 aba를 찾을 때, [aba]b[aba]ba 이렇게 찾은 문자열에서 index가 겹치게 사용할 수 없다는 것이다. 아이디어는 문서의 0번째 인덱스부터 끝까지 단어의 크기만큼 비교하는 것이다. aba와 aba bab와 aba aba와 aba bab와 aba baba와 aba aba와 aba 시간복잡도는 O(N^2)지만 입력받는 문자열의 길이가 길지 않기 때문에 신경쓰지 않아도 될 것 같았다. 그리고 하나씩 비교하는데 만약 단어가 같다면 단어크기만큼 index를 증가하고 다시 비교한다. 단어가 같지 않으면 그냥 index++를 한다. ababababa에서 처음 [aba]bababa는 aba와.. 2019. 7. 3.
[알고리즘 문제] 백준1343 - 폴리오미노 문자열 처리하는 문제인데, 생각보다 시간이 오래걸린 것 같다. 가장 중요한 부분은 폴리오미노, "AAAA","BB"의 크기가 모두 짝수이기 떄문에 "X"의 개수가 홀수이면 -1를 출력해야 한다. "X"의 개수는 "."을 기준으로 각각 몇개있는지 구할 수 있으며, XXXX....XXX.....XX에서 4개,3개,2개가 된다. 여기서 홀수개가 나왔기 때문에 -1을 출력하게 된다. 또한, X의 개수를 세다가 "."가 나오면 그때 "X"를 "AAAA"나 "BB"로 바꿔줘야 한다. 그리고 문제에서 "."은 덮으면 안된다고 했으니, 구한 문자열에 "."를 더해준다. 그리고 "X"를 "AAA"나 "BB"로 바꿔주는 부분은 print()함수가 맡고 있으며, 인자로 size를 받는다. 인자는 문자열에서 "."로 구분된 .. 2019. 6. 21.
[알고리즘 문제] 백준1969 - DNA 문제는 Hamming Distance의 합이 가장 작은 DNA(문자열)을 구하는 문제이다. 여기서 Hamming Distance는 길이가 같은 두 DNA의 각 index에서 다른 문자의 개수이다. 처음에, 입력으로 들어오는 DNA중에서 찾는 문제인 줄 알고 헤맸는데 그게 아니라 입력으로 받는 모든 DNA와 비교하여 Hamming Distance의 값이 최소가 되는 새로운 DNA을 구하는 문제이다. 아이디어는, 1. DNA를 모두 입력받고, 각 DNA의 첫번째, 두번째, ... 빈도수를 체크하고, 체크된 배열과 최대빈도수값은 getChar()에 넘겨준다 2. getChar() 에서는 최대빈도수 값을 가지는 문자를 찾고, 반환해준다. 문제를 풀고, 다른 사람들의 풀이를 봤는데 나의 코드보다 더 깔끔하게 했다.. 2019. 6. 19.