Coding 한놈만 팬다

문제링크 문제 풀이 과정 보석을 가방에 넣는 로직에서 보석이 중복으로 들어가지 않는 것에 대해 오래 고민을 한 문제이다. 우선 보석의 무게와 비용을 한번에 담기 위해서 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..

서울시 공공 와이파이 서비스 정보를 이용하여 파싱하는 방법에 대해 작성하고자 한다. 우선 서울시 공공 와이파이 서비스 정보를 가져오기 위해서는 서울시 열린데이터 광장에 들어가서 KEY 를 먼저 발급 받아야한다. 발급 받은 api 를 어떻게 사용해야하는지 나와있다. 이것을 참고해서 보면 api 를 통해서 데이터는 xml, json 형태로 받을 수 있다는 것을 알 수있다. json 형태로 받기 위해서는 샘플 url 에서 (인증키)/json 으로 수정하여 사용하면 된다. 참고로 파싱하는 과정은 인텔리제이를 통하여 진행하였다. json 파싱하기 위해서는 우선 json 라이브러리를 다운 받아야한다. 다운 받은 라이브러리를 프로젝트에 추가해주면 된다. Google Code Archive - Long-term sto..

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

이 글은 인텔리제이에서 웹 어플리케이션 프로젝트 생성하다가 삽질 오만번 한 뒤에 성공하여 작성한다. 처음에는 인텔리제이 무료버전인 Community 버전을 사용하여 웹 어플리케이션 프로젝트를 생성하려고 했다. 하지만 아무리 구글링해도 구글링에서 본 생성 과정과 내가 보는 화면과 너무 달랐다. 알고보니 Ultimate 버전에 Jakarta EE 사용이 가능하다는 것을 알게되었다. 학생 이메일 계정을 가지고 있다면 Ultimate 버전을 무료로 다운이 가능하다. 설치 후 new Project 를 생성을 하면 된다. 여기서 Jakarta EE 를 누른다. 구글링 했을 때 Java EE 를 선택하는 화면이 많이 보여서 왜 내 화면에는 이게 없지 하고 당황했는데 Java EE 가 Jakarta EE 로 이름이 변..

문제링크 문제 풀이 과정 플로이드-워셜 알고리즘을 학습 할 수 있는 기본적인 문제라고 생각한다. 플로이드-워셜 알고리즘을 그대로 사용하여 문제를 해결하였다. 다만 제출 할때 항상 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 이 반복 된다. 이때는 반복문을 종료하면 된다. 전체 코드

문제 링크 문제 풀이 과정 이 문제를 처음 접했을 때 어떤 접근 방식을 이용하여 풀어야할지 고민을 많이 했다. 결국은 이 문제의 답은 이진 탐색을 이용하는 것이다. 이진 탐색으로 바위 간격의 최소값을 mid 값으로 정해두고 해결하면된다. 바위의 간격은 항상 정렬 되어 있지 않으므로 정렬 한 뒤에 시작한다. 정렬하고 나면 바위의 간격은 {2, 9, 3, 3, 4, 4} 가 된다. 여기서 중간 값은 14가 된다. 첫번째 바위와 의 거리가 2이고, mid 값보다 작으므로 바위를 한개를 제거해준다. 그러면 바위의 간격이 11이 된다. 11은 mid 보다 작으므로 다음 바위도 제거해준다. 첫 바위와의 거리가 14가 되고, mid 보다 같으므로 다음 바위를 검사한다. 다음 바위와의 거리가 3이고, 더이상 제거할 바..

문제링크 문제 풀이 방법 처음에 이 문제를 접했을 때는 이진 탐색으로 해결하려고 했다가 코드가 더 복잡해지고 시간 초과 될 것 같아서 다른 방법을 찾아야했다. 규칙을 찾으면 생각보다 쉽게 해결 되는 문제이다. 문제에 있는 예제로 설명을 하면, 우선 주어진 추들을 정렬을 해야한다. 1번추로 측정 할 수 있는 무게는 1이다. 2번째 추까지 이용하여 측정 가능한 무게는 2이다. 2번째까지 측정 가능한 무게는 2이며, + 1을 하면 3이다. 3은 3번째 추(2)보다 크므로 3은 측정이 가능하며, 3번째까지 측정 가능한 무게는 4가 된다. 4번째 추를 이용하여 측정 가능한 무게는 7이다. 5번째 추를 이용하여 측정 가능한 무게는 13이다. 6번째 추를 이용하여 측정 가능한 무게는 20이다. 여기서 20 + 1을 ..