LeetCode의 141번을 풀다가 발견한 알고리즘. Linked List Cycle - LeetCode Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internall leetcode.com 설명과 사진은 geeksforgeeks를 참고. Floyd’s Cycle Finding Algorithm - GeeksforGe..

322. Coin Change 동전의 목록인 coins가 주어진다. coins로 만들어야하는 amount가 주어진다. coins로 amount를 만들때 가장 적은수를 사용하는 케이스를 출력해야한다. class Solution { public int coinChange(int[] coins, int amount) { // amount가 0이면 만들수 없다 if(amount == 0) return 0; int[] dp = new int[amount+1]; // dp 구현을 위한 공간 할당 Arrays.fill(dp, Integer.MAX_VALUE); // 각 dp 원소에는 Integer의 최대값으로 초기화 Arrays.sort(coins); // coins를 오름차순으로 sorting List coinLi..

LeetCode를 풀면서 고생했던(?) 문제와 재밌게 풀었던 문제들을 돌아보는 시간. 886. Possible Bipartition 서로 함께할 수 없는 번호들이 주어지고 return으로 2개의 그룹을 만들 수 있는지를 넘겨줘야하는 문제다. 탐색으로 풀어야겠다고 생각하고 접근까지는 했으나 상태를 3개로 구분하지 못해서 헤맸다. (돌아보면 진짜 아무것도 아닌데) 방문, 미방문이 아니라 미방문, 그룹1, 그룹2 이런식으로 3가지의 상태를 통해 문제를 풀었어야했다. class Solution { public static boolean possibleBipartition(int N, int[][] dislikes) { int[] peopleGroup = new int[N+1]; Map graph = new Ha..

1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 입력된 문자에 존재하는 알파벳이 연속되는지 확인하는 문제이다. 아이디어 1. 입력된 문자에 존재하는 알파벳을 구한다. 2. 알파벳이 연속되는지 확인한다. 3. 현재의 index가 이전의 index보다 +1인 경우는 연속이며 그렇지 않은 경우는 불연속이다. 4. 문자내에 알파벳이 하나만 있는 경우는 연속으로 처리한다. 구현 getAlphabet 함수를 만들어 입력된 문자내에 존재하는 알파벳을 ArrayList로 반환하도록 한다. s..

2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 입력된 문자의 갯수를 세는 프로그램을 만드는 문제다. 입력된 문자중에는 크로아티아 알파벳이라고 해서 2개이상의 문자가 조합되어 1개의 문자를 의미하는 케이스가 존재한다. 아이디어 입력받은 문자에서 크로아티아 알파벳의 갯수를 센다. 또한 크로아티아 알파벳이 있다면 "_" 문자 형태로 치환한다. 치환된 문자에서 "_"가 아닌 문자의 갯수를 센다. 구현 구현 하면서 주의할 점은 크로아티아 알파벳이 있는지 검사할때 긴문자부터 수행해..

5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 전화기의 번호를 누르기 위해선 몇초간 기다리는 시간이 필요하며, 각 번호에는 3~4개 알파벳이 매핑 되어있다. 입력은 번호가 아닌 알파벳으로 주어지며 이 알파벳을 보고 전화를 거는데 걸리는 시간을 구하는 문제다. 첫번째 아이디어. 문제에 각 알파벳을 선택하는데 소요되는 시간은 이미 확정 되어있다. A,B,C는 3초가 소요되며 D,E,F를 선택할때는 4초가 걸린다. 아스키 코드를 통해 문자를 10진수 정수로 변환했고 아래와 같은 방법으로 알파벳을 선택하는데 걸린 시간을 구했다. 이런식으로 풀면 정답일줄 알았는데 한가지 실수가 있었다. (위에 형광펜..