반응형 알고리즘 문제 풀이/백준6 백준: 사탕 게임 본 풀이는 java 언어를 사용하였습니다. 3085번: 사탕 게임 풀이 아래처럼 보드의 각 칸마다 해당 칸의 사탕을 상, 하, 좌, 우 움직이면서 다른 사탕과 바꾼 후 바꿀 때마다 행, 열의 연속된 사탕 최대 개수를 구하면서 그 중에 가장 큰 개수를 구하면 풀 수 있을 것 같았다. (완전 탐색) 먼저, 사탕을 움직이기 전에 현재 보드에 있는 행, 열의 연속된 최대 사탕 개수를 구한다. 해당 로직은 checkMaxCountOfCandyToEat() 메서드로 분리한다. public int solution(String[][] board, int n) { int maxCountOfCandyToEat = checkMaxCountOfCandyToEat(board, n); } 행, 열의 연속된 최대 사탕 개수는 아래.. 2022. 2. 11. 백준 : 섬의 개수 (4963) *** 본 풀이는 java언어를 사용하였습니다 *** 문제 보러가기 요약 섬과 바다가 적힌 지도가 주어진다. 섬 주변에 (360 도) 다른 섬이 있으면 하나의 섬이라고 가정한다. 섬의 개수를 출력하라. 문제를 보자마자 그래프 탐색으로 풀어야 겠다는 생각이 들었다면 문제를 쉽게 풀 수 있었을 것이다. 그래프 탐색은 BFS와 DFS가 있는데, 필자는 BFS로 풀었다. 참고 ) 보통 DFS는 스택이나 재귀함수를 통해서 구현하고, BFS는 큐를 이용해서 구현한다. 풀이 여러가지 방법이 있겠지만, 필자의 경우 탐색하는 위치가 섬 일 경우 BFS 탐색을 시작하게끔 구현했다. public static int solution(int[][] map) { int result = 0; boolean[][] visited =.. 2020. 4. 8. 백준 : 한수 (1065) *** 본 풀이는 java언어를 사용하였습니다 *** 문제 보러가기 요약 정수의 각 자리가 등차수열을 이루면 한수다. 한수의 개수를 출력하라. 각 자리가 등차수열이란?? 처음에는 한수라는 용어가 잘 이해가 안갔는데, 간단하게 예를 들면 다음과 같다. 예시 1 ) 123이라는 수가 있다면 각 자리의 수는 1, 2, 3이다. 수는 +1 씩 일정하게 증가하는 등차수열 이므로, 이것은 한수다. 예시 2 ) 111이라는 수가 있다면 각 자리의 수는 1, 1, 1이다. 수는 +0 씩 일정하게 증가하는 등차수열 이므로, 이것 또한 한수다. 예시 3 ) 110이라는 수가 있다면 각 자리의 수는 1, 1, 0이다. 첫 번째 수와 두 번째 수의 차이는 +0이다. 두 번째 수와 세 번째 수의 차이는 -1이다. 따라서 일정하.. 2020. 4. 8. 백준 : 신입 사원 (1946) *** 본 풀이는 java언어를 사용하였습니다 *** 문제 보러가기 요약 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발 위 말은 A 지원자의 서류심사 성적이 B 지원자의 서류심사 성적보다 낮더라도 A 지원자의 면접시험 성적이 더 높다면 A 지원자가 선발 된다는 말이다. 풀이 다음 예시를 보자. 3 2 1 4 4 1 2 3 5 5 지원자들의 성적이 다음과 같이 들어왔다면, 비교를 위해 먼저 성적을 서류심사 순으로 오름차순 정렬한다. 1 4 2 3 3 2 4 1 5 5 맨 처음 지원자는 서류심사가 1등. 즉, 적어도 하나가 다른 지원자 보다 떨어 질 수 없는 조건이므로 무조건 합격이다. 서류심사 기준 오름차순 정렬 상태 이므로 다음 지원자는 무조건 서류심사 점수가 .. 2020. 3. 27. 백준 : 회의실배정 (1931) *** 본 풀이는 java언어를 사용하였습니다. *** 문제 보러가기 풀이 회의실 사용시간과 끝나는 시간의 회의들을 그래프로 나타내면 다음과 같다. 우리가 원하는 것은 최대 사용할 수 있는 회의의 개수를 구하는 것이다. 최대한 많은 회의의 개수를 구하는 방법은 다음과 같이 구할 수 있다. 회의가 끝나는 시간별로 오름차순 정렬 현재 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교 다음 회의의 시작 시간이 더 크다면 최대 사용할 수 있는 회의 개수 1 증가 회의가 끝나는 시간별로 오름차순 정렬되어 있으니 3번을 통과한다면 그 시간에서 나올 수 있는 최대 회의 개수가 되기 때문 주의할 점은 회의가 끝나는 시간이 같을 경우는 회의 시작 시간을 비교 해 정렬해야 한다. 회의는 Conference 객체로 분리했.. 2020. 3. 26. 문제 1152 - 단어의 개수 단어의 개수 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초128 MB69122153931093322.507% * 사용 언어 : java (자바)문제 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 예제 입력 1 복사 The Curious Case of Benjamin Button 예제 출력 1 복사 6 예제 입력 2 복사 Maz.. 2018. 10. 19. 이전 1 다음
