파워코딩

HackerRank link Organizing Containers of Balls 풀이 핵심 각 타입의 총 수와 각 컨테이너가 갖고 있는 ball의 총 수가 일치 해야 함. ex) type 0번의 총 갯수가 1, container 0의 총 갯수는 2 type 1번의 총 갯수가 3, container 1의 총 갯수는 2 container의 0에 type 0을 다 swap해서 넣는다고 할때, type 0은 1개만 있어서 container 0에서 총 담아야 하는 갯수는 1개이다. 하지만, container 0은 총 2개를 담고 있으므로, 절대 type 0만 담을 수 없다. Algorithm type 별 총 갯수를 구한다. (각 행의 합) container가 갖고 있는 수를 구한다. (각 열의 합) 한쪽으로 ..

HackerRank link Prime Dates 풀이 핵심 HacerRank에서 몇없는 debugging 문제인데.. 역시 너무 쉬움. Algorithm Source Code import java.util.*; import java.lang.*; import java.io.*; import java.math.*; public class Main { public static void main (String[] args) throws java.lang.Exception { Scanner kb = new Scanner(System.in); int test_cases = kb.nextInt(); for(int cs = 1; cs

HackerRank link Zig Zag Sequence 풀이 핵심 HacerRank에서 몇없는 debugging 문제인데.. 역시 너무 쉬움. 주의 할점은.. 코드를 더 좋게 만들려고 했다가 라인수가 조금이라도 벗어나면 에러로 판단됨. Algorithm Source Code import java.util.*; import java.lang.*; import java.io.*; import java.math.*; public class Main { public static int month[]; public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); month = new..

HackerRank link Forming a Magic Square 풀이 핵심 경우에 따라선 복잡한 알고리즘으로 구하는 것보다 모든 경우를 직접 구해서 비교하는 방법이 더 빠르다. 3x3 마방진의 경우 모든 경우의 수는 9가지가 된다. (기본 형태 + 좌/우/상/하 대칭 + 90도씩 회전 = 9가지) Algorithm 9가지의 마방진을 미리 입력해 둔다. 입력으로 들어온 3x3행렬을 미리 입력 된 마방진을 통하여 cost의 최솟값을 구한다. Source Code import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; imp..

HackerRank link Crossword Puzzle 풀이 핵심 십자말 퍼즐에 전부 단어를 넣어 보는 수 외에는 없다. 십자말에 지속적으로 단어를 넣는 과정은 재귀함수를 통하여 구현한다. 알고리즘이 어렵지 않는 문제 유사 문제: Ema's Supercomputer Algorithm 다 풀렸는지 체크 한다. 다 풀렸으면 정답을 리턴한다. Stack으로 부터 넣을 단어를 가져온다. 현재 단어가 들어갈 위치를 구한다. 해당 단어가 넣을 곳이 있다면, 차례 차례 그 단어가 들어갈 위치에 순서데로 단어를 넣는다. 다음 단어를 넣는다. (재귀 호출 과정 1부터 다시) 넣었던 단어 빈 공간으로 다시 원상 복귀 시키고, 다음 위치에 단어를 넣는다. 과정3. 과정 3에서 단어를 넣을 곳이 없다면, stack..

HackerRank link Recursive Digit Sum 풀이 핵심 이름 그대로 재귀 함수를 이용하여 풀이 입력에 k 번 반복의 경우 k번 반복 할 필요 없이 k를 곱하면 간단하게 해결 Algorithm 문자열의 길이가 1이면 구할 필요가 없음. 바로 리턴. 각 문자열의 숫자를 합하고 k를 곱한다. 문자열의 길이가 1이 될때까지 각 문자열의 숫자를 합하여 super digit을 구한다. (재귀함수) Source Code import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*..

HackerRank link Cut the Tree 풀이 핵심 node의 탐색 방법으로는 DFS를 이용. node를 탐색하면서 노드의 값을 더하면서 값을 계산함. 이 문제 에서 Java의 경우 input reference 코드의 퍼포먼스가 매우 안좋게 되어 있어서, 풀이법이 맞아도 계속적으로 timeout error가 발생함. 유사한 문제 : Even Tree 퍼포먼스를 좋게 하기 위한 방법 입력을 받을 때 총합을 미리 계산한다. => node 탐색 시 계산에 용이 입력 시 아래 코드와 같이 scanner.nextInt(); 를 사용하는 방법이 훨씬 빠름. String[] arrItems = scanner.nextLine().split(" "); // 쓰지 말것 int[] input = new int[i..

HackerRank link Project Euler #89: Roman numerals 풀이 핵심 주어진 사양에 맞게 코딩 문자열→숫자, 숫자→문자열 변환 Algorithm 로마 숫자를 숫자로 변환한다. 변환된 숫자를 로마 숫자로 변환한다. Source Code import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int RomanNumStr2Num(String str) { int[] number = new int[] { 1, 5, 10, 50,100,500,1000}; char[] romanStr = new char..

HackerRank link The Maximum Subarray 풀이 핵심 두가지를 풀어야 됨. [max subsequence] 단순히 양수를 더하면 최댓값을 알 수 있음. [max subArray] 동적 프로그래밍으로 풀이 아래의 표와 같이 최대 subArray의 sum은 sum의 최대값 - sum의 최소값(단, 최대값 이전 index) 이다. index 0 1 2 3 4 5 6 arr -2 2 -1 2 3 4 -5 sum -2 0 -1 1 4 8 -3 답은 10 Algorithm 현재까지의 sum 값을 구한다. 최소 값과 최대값을 업데이트 하며, subArrMax를 업데이트한다. 양수를 더하며 subsequence의 최대값을 구한다. 과정 1~4를 반복한다. Source Code import jav..

HackerRank link Alice and Bob's Silly Game 풀이 핵심 Alice와 Bob이 서로 반복하기 때문에 계속 반복할 필요 없이 소수의 총수를 구하면 간단하게 구할 수 있다. Algorithm 소수를 구하면서 전체 소수의 갯수를 센다. 소수의 수가 짝수이면 Bob, 아니면 Alice를 리턴한다. Source Code import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { /* * Complete the sillyGame function below. */ static String sillyGame(int..