문제 풀이과정카드가 N개 주어질 때 3개의 카드를 골라서 M보다 크지 않으면서 M과 가장 가까운 합을 구하는 문제이다. 브루트포스 알고리즘으로 해결할 수 있다.N개의 카드 중에 3개의 카드를 고르는 모든 경우의 수에 대하여 탐색한다.3개의 카트의 합이 M 이하이면서 최대값을 구하면 정답을 찾을 수 있다. 예를 들어, [5, 6, 7, 8, 9] 5개의 카드가 주어졌을 때 경우의 수는 다음과 같다. [5, 6, 7] => sum = 18, max = 18[5, 6, 8] => sum = 19, max = 19[5, 6, 9] => sum = 20, max = 20.[7, 8, 9] => sum = 24, max = 24 몇가지 상황을 고려하면 최적화도 가능하다.첫번째 카드가 M보다 크다면 다음 카드와 상..
Algorithm
문제 풀이 과정N x M 크기의 맵이 주어진다. 그리고 맵에서 로봇청소기의 위치인 좌표(r, c)와 방향 d가 주어진다.d가 0 = 북, 1 = 동, 2 = 남, 3 = 서 로봇청소기는 각 영역에 대해서 3가지로 구분할 수 있다.0 = 청소가 필요한 영역1 = 벽2 = 청소한 영역 step1. 청소 가능 구역 탐색로봇 청소기는 반시계 방향으로 회전한다. 북 -> 서 -> 남 -> 동즉, 반시계 방향 회전 공식 => d = (d + 3) % 4 회전을 완료하면 좌표를 이동해야 한다. 좌표를 이용할 때 Direction delta를 사용한다.방향dr (행 변화량)dc(열 변화량)북(0)-10동(1)0+1남(2)+10서(3)0-1 로봇 청소기가 이동할 좌표를 구했다면, 이동할 수 있는지 파악한다.로봇 청..
문제 풀이 과정각각의 칸마다 현재 위치 기준으로 왼쪽과 오른쪽에 더 높은 블록이 존재하면, 빗물이 고일 수 있다.고일 수 있는 빗물의 양 = 좌우 중 더 낮은 블록의 높이 - 현재 블록의 높이로 계산된다. 1. 모든 블록을 순회한다.2. 현재의 블록 위치에서 왼쪽에서 가장 높은 블록의 높이와 오른쪽에서 가장 높은 블록의 높이를 구한다.2. 이 둘 중 더 낮은 값을 기준으로 현재 블록의 높이의 차가 구하여 누적한다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class ..
문제 풀이 과정문제는 길지만, 단순한 구현 문제이므로 겁먹을 필요가 없는 문제였다. 1. 입력된 학생 정보를 통해 남자와 여자를 구분한다.2. 남자의 경우는 받은 수의 배수에 해당하는 스위치 번호를 찾아 해당 스위치의 상태를 모두 반전 시킨다.3. 여자의 경우는 받은 번호를 기준으로 좌우로 대칭되는 범위를 탐색한다. [N+1], [N-1] => [N+2], [N-2] ...이런식으로 탐색한다. 탐색과정에서 배열의 범위 내에서 좌우의 상태가 같다면 스위치를 반전해준다.4. 각 스위치를 출력할 때 한 줄에 20개씩 출력해주면 성공! 스위치 번호는 1부터 시작하고 배열의 Index는 0이라는 점만 고려해주면 실수 없이 풀 수 있는 문제였다.코드import java.io.BufferedReader;import..
문제 풀이 방법방 번호 N이 주어지면 숫자를 한 자리씩 구한 다음, 0 ~ 9까지 등장 횟수를 세는 배열에 기록한다.이 때, 숫자 6과 9는 서로 뒤집어서 사용할 수 있기 때문에 같은 번호로 6으로 취급하여 카운트한다. 또한 한 세트 당 6, 9가 각각 1개씩 총 2개를 가지므로 등장 횟수를 2로 나눈 다음 반올림 해야 실제로 필요한 세트 수를 구할 수 있다. 모든 숫자의 카운트를 처리한 다음, 가장 많이 필요한 숫자의 개수가 곧 필요한 숫자 세트의 최소 개수다.카운트 배열을 하나씩 돌면서 가장 많이 필요한 숫자의 개수를 구하면 해결할 수 있다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRe..
문제 풀이 방법도화지는 가로, 세로 길이가 각각 100인 정사각형이므로, 각 영역이 색종이에 덮였는지 확인하기 위해 Boolean 타입의 100 x 100 2차원 배열을 선언한다.배열의 각 칸은 해당 영역이 색종이에 덮혀있으면 true, 그렇지 않으면 false로 표시한다. 색종이는 가로, 세로 길이가 10인 정사각형이므로, 입력으로 주어진 좌표를 기준으로 10 x 10 영역을 순회하며 해당 영역을 true로 변경한다. 이때 이미 true로 표시된 영역은 겹쳐진 부분이므로, 넓이 계산에 포함시키지 않는다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.St..
문제 풀이과정소수찾기 문제이다.1과 자신만을 약수로 가지는 수를 소수라고 한다. 3의 경우1 x 3 = 3 3의 약수는 1, 3이므로 소수에 해당된다. 4 같은 경우1 x 4 = 42 x 2 = 44의 약수는 1, 2, 4가 되므로 소수가 될 수 없다. 그리고 1 같은 경우는 소수가 자신뿐이므로 소수가 될 수 없다. 내가 생각해낸 문제 풀이 방법은 다음과 같다. 2부터 주어진 판별하려는 number - 1 까지 하나씩 나누어보면서 나누어 떨어지지 않으면 소수, 그렇지 않으면 소수로 판별하는 것이다. 소수를 판별하는 isPrime() 메서드를 유심히 보면 풀이과정 이해하는 것에 어려움은 없을 것이다. 코드import java.io.BufferedReader;import java.io.IOException..
