Coding 한놈만 팬다

문제링크 문제 풀이 과정 투포인터를 이용하면 간단하게 해결되는 문제이다. 부분 수열의 합이 중복 되면 안되므로 부분수열의 합을 HashSet 에 저장하여 나중에 HashSet 의 size 를 출력하면 부분 수열의 합의 수가 출력이 된다. HashSet sumSet = new HashSet(); for(int item : elements){ sumSet.add(item); } 부분 수열의 길이가 1인 경우는 배열 원소가 해당 되므로 우선 배열 원소 각각을 set 에 넣어 주었다. 부분 수열의 길이가 2일때 초기 start 와 end 를 start 는 0, end 는 start + i(간격) 으로 지정해준다. start 부터 end 까지의 합을 sum 에다 저장해둔다. 그다음 부분수열로 움직일때 sum 에서..

문제링크 문제 풀이 과정 이 문제를 잘 보면 f(n) = f(n - 1) + f(n - 2) 피보나치 수열이라는 것을 알수 있다. 5 까지의 경우의 수이다. 칸이 3일때를 보면 칸 2일때와 1일때의 값을 더한 값이 된다. 칸이 4일때도 칸이 3일때와 2일때의 값을 더한 값이 칸이 4일때의 값이 된다. 따라서 이 문제가 피보나치 수열이라는 것을 알 수 있다. 피보나치수열은 재귀호출을 이용하여 풀이하는 것과 dp 배열을 사용하여 풀이 하는 방법이 있는데 이 문제는 재귀 호출을 이용하면 통과가 안된다. 또한 dp 을 선언 할때 배열의 칸을 n + 1 만큼 잡았었는데 이러면 케이스 1이 통과가 안된다. dp 배열의 길이를 매우 넉넉하게 잡거나 n + 2 만큼 잡으면 테스트 1이 통과가 된다. 전체 코드

문제 링크 문제 풀이 과정 체스 규칙을 잘 모르면 이 문제를 처음 접했을 때 난감할 수 있다. 사실 체스 규칙을 전혀 몰라서 퀸의 움직임에 대해서 먼저 검색했었다. 퀸은 오른쪽, 왼쪽, 위, 아래, 대각선으로 움직일 수 있다. 첫번째 퀸의 위치가 (0, 1) 일때 엑스 친 부분은 퀸이 공격 가능한 위치이다. 이 문제는 서로 다른 퀸이 공격 못하게 배치해야 되므로 다음 퀸의 자리는 (1, 3) 이 된다. 3번째 줄에는 퀸을 둘 수 있는 곳이 한곳밖에 없다. 4번째 퀸까지 배치가 가능하므로 서로다른 퀸이 공격 못하게 하는 위치가 된다. 대부분 구글에서는 1차원 배열로 풀이 하였지만, 1차원 배열보다는 직관적인 2차원배열이 이해가 잘되서 2차원 배열로 풀이 하였다. 퀸이 공격이 가능한 자리를 표시하는 visi..

문제링크 문제 풀이 과정 이 문제의 핵심은 LRU 알고리즘을 이용하는 것인데, LRU 알고리즘을 사전에 알고 있으면 쉽게 해결 되는 문제이다. 첫번째 예제를 이용하자면 캐시의 사이즈가 3이므로 3개의 도시까지 캐시에 들어 올 수 있다. 도시배열을 보면 3번째까지 도시가 겹치는 것이 없으므로 3개의 도시가 캐시 미스 되어 캐시에 들어 오게 된다. 그 다음 도시인 NewYork 은 기존 캐시에 없었으므로 캐시 미스가 발생 하게 된다. 이때 캐시 사이즈는 3이므로 LRU 알고리즘에 의해서 제일 처음에 사용했던 캐시 부분이 삭제된다. 만약 캐시에 넣을 데이터가 캐시에 존재 하고 있다면 캐시 히트가 발생 하여 기존 캐시에 있던 데이터를 삭제 할 필요가 없어진다. 전체코드

문제링크 문제 풀이 과정 보석을 가방에 넣는 로직에서 보석이 중복으로 들어가지 않는 것에 대해 오래 고민을 한 문제이다. 우선 보석의 무게와 비용을 한번에 담기 위해서 Item 클래스를 만들었다. static class Item implements Comparable{ int idx; int weight; int cost; public Item(int idx, int weight, int cost) { this.idx = idx; this.weight = weight; this.cost = cost; } @Override public int compareTo(Item o) { if(this.weight == o.weight){ return o.cost - this.cost; } return this.we..

문제링크 문제 풀이 과정 효율성을 통과하기 위해서 HashMap 을 사용하여 문제를 접근 하였다. HashMap 의 key 는 현재 지정한 방 번호이며, value 값은 현재 지정한 방의 다음 위치를 나타낸다. 예약하고자 하는 방의 번호가 예약 되었는지 여부를 containsKey 를 통해서 빠르게 찾을 수 있다. 키가 존재 하면 이미 예약된 방이며, 키가 없다면 예약이 가능하다. 이 문제는 재귀방식으로 코드를 작성해야지 효율성 테스트를 통과할 수 있다. 처음에는 재귀 방식이 아닌 반복문으로 작성 하였는데 정확성은 맞지만, 효율성에서 모두 다 통과하지 않는 상황이 생긴다. 전체코드

문제링크 문제 풀이 과정 플로이드-워셜 알고리즘을 학습 할 수 있는 기본적인 문제라고 생각한다. 플로이드-워셜 알고리즘을 그대로 사용하여 문제를 해결하였다. 다만 제출 할때 항상 98% 에서 틀렸습니다가 나와서 의문이였다. 알고보니 MAX 값으로 잡았던 값이 작아서 문제가 되었다. 여기서 MAX 값을 Integer.MAX_VALUE 로 잡으면 오버플로워가 발생하게 된다. 전체 코드

문제링크 문제 풀이 과정 문자열 일부분에 PPAP 가 있을 때 이 문자열을 P 로 치환을 하여 마지막에 문자열 P 하나만 남아 있다면 이 문자열은 PPAP 문자열이다. 처음에는 이 문제를 문자열을 배열로 변환한 뒤 스택을 이용하여 풀었더니 시간초과가 되었다. 문자열을 배열로 변환하지 않고 문자열의 인덱스를 이용하여 문제를 풀었더니 해결되었다. 문자열에서 P 가 나오면 P 의 갯수를 카운트를 해준다. 이것을 A 가 나올때까지 카운트 해준다. A 가 나왔을 때 P 의 갯수가 2개 이상이며, 다음 문자열이 P 일때만 PPAP 문자열이 되므로, P 의 수를 한개 줄여주고 문자열의 인덱스를 증가시킨다. 여기서 P 의 갯수를 한개 줄이는 PPAP 는 다시 P 로 치환되기때문에 다시 P 가 추가 된다. 결국 -2 +..

문제 링크 문제 풀이 과정 이 문제는 탐색을 통해서 해결해한다. 다이나믹 프로그래밍으로 해결 하기위해서는 우선 dp 용 배열을 하나 만들어 둔다. 탐색 할때 첫번째 행과 열일 때는 별도의 탐색을 하지 않는다 첫번째 열과 행이 아니면서 1일때는 현재 기준으로 위, 왼쪽, 왼쪽 대각선의 값을 확인 해봐야한다. 그 중에서 최소값에다가 + 1을 한 값이 사각형의 크기가 된다. (1, 1) 인 경우에는 현재값이 1이라 위, 왼쪽, 왼쪽 대각선의 값을 비교해야한다. 이 세개의 최소 값은 0 이고 이 값에 + 1한 값은 1이 된다. (2, 2) 일때는 위, 왼쪽, 왼쪽 대각선의 값의 최솟값이 1이며, 이 값에 + 1 하면 2가 된다. 여기서 나온 2는 이 사각형의 크기가 된다. 전체 코드

문제링크 문제 풀이 과정 이 문제의 알고리즘 분류는 투 포인터라서 투 포인터로 쉽게 해결 할 수 있었다. 현재 몸무게를 p1, 기억하는 몸무게를 p2 로 지정 한 뒤 문제를 풀었다. p1 * p1 - p2 * p2 를 한 결과 값이 n 보다 작으면 p1 을 증가하였고, n 보다 클 때는 p2 를 증가하였다. 결과 값이 n 과 같을 때는 list 에 값을 저장을 해두었다. 더이상 값이 없을 때는 p1 * p1 - p2 * p2 결과 값이 n 보다 크면서 p1 - p2 값이 1 이 반복 된다. 이때는 반복문을 종료하면 된다. 전체 코드