Coding 한놈만 팬다

문제 링크 문제 풀이 과정 이 문제를 처음 접했을 때 어떤 접근 방식을 이용하여 풀어야할지 고민을 많이 했다. 결국은 이 문제의 답은 이진 탐색을 이용하는 것이다. 이진 탐색으로 바위 간격의 최소값을 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을 ..

문제링크 문제 풀이 과정 정답률이 50% 정도이고 level3 라서 어렵겠구나 싶었는데 생각보다 단순하게 생각하니깐 잘 풀리던 문제였다. A, B 모두 정렬한 뒤에 큰수부터 비교해서 풀면 된다. A 와 B 의 배열 인덱스를 다르게 한 이유는 A 보다 B 가 작을때 그 카드를 쓰지 않고 A 의 다음 카드와 비교해서 B 카드가 클 수 있는 가능성이 있기 때문에 다른 인덱스를 사용하였다. 전체 코드

문제링크 문제 풀이 과정 스트림과 람다식으로 간단하게 코드를 작성 할 수 있었다. 코드 실행 시에 11번 케이스만 오류가 나고 나머지는 모두 통과가 되었다. 반례를 생각해보니 0,0,0,0,0 일때는 0이 return 이 되어야 한다는 점이다. 문자열이기때문에 0,0,0,0,0 일때 00000이 나온다. 이것을 해결하기 위해서 코드 초반 부분에 배열의 전체 합을 구한 다음 합이 0일 때는 return 0으로 하는 것으로 해결이 되었다. int sum = Arrays.stream(numbers).sum(); if(sum == 0){ return "0"; } 전체 코드

문제링크 문제 풀이 과정 탐색을 이용하여 문제를 풀이하였습니다. 모든 배열 원소를 탐색하여 방문 여부로 true / false 로 구별하였으며, 모든 배열 탐색이 끝났으면 방문 배열에서 true 인 경우는 +, false 인 경우는 - 하여 나온 값이 타겟 넘버와 비교하였습니다. 전체 코드

문제링크 문제 풀이 과정 크루스칼 풀이 방법을 그대로 적용하면 되는 문제이다. 크루스칼을 적용하기 전에 한단계 준비 작업이 필요하다. 주어진 데이터는 별들의 좌표만 주어지기 때문에 서로 다른 별들의 거리를 먼저 구한 다음 크루스칼을 적용하면 된다. 두점 사이의 거리 구하는 방법이다. public static double dist (Point p1, Point p2){ return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); } 별들의 좌표는 Point class 를 별도로 구현하였다. public static class Point{ double x; double y; int idx; public Point(double x, double..

문제링크 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요..

문제링크 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 ..

문제링크 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 ..

문제링크 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양..