수익 4097번
내가 떠올린 풀이 해설
입력이 많지 않아 BufferedReader보단 Scanner를 사용했습니다. 처음 코드를 작성했을 때 max 값을 0으로 선언을 해주었지만 입력값이 음수일 경우 max 값을 구할 때 max 값이 0이 되므로 max 값을 Integer.MIN_VALUE로 선언해 주어야 합니다. 총수입을 담을 sum 변수를 만들었습니다. 입력의 마지막은 0으로 구분해서 입력 n이 0이면 break 하고 0이 아니면 for 문으로 n 미만까지 for 문을 수행한다. for 문에는 입력 값을 담을 num을 선언해 주었고 입력받은 값을 sum에 누적해서 더합니다. Math.max를 이용해 max와 sum을 비교해 큰 값을 max에 담았습니다. sum의 값이 음수가 되면 sum 값을 0으로 다시 초기화하였습니다.
정확한 풀이
import java.util.*;
public class Baek4097 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
int n = sc.nextInt();
int max = Integer.MIN_VALUE;
int sum = 0;
if(n == 0) {
break;
}
else {
for(int i = 0; i < n; i++) {
int num = sc.nextInt();
sum += num; // -3, 1, 10, 8, 3, 11
max = Math.max(max, sum); // 0, 1, 10, 10, 10, 11
if(sum < 0) {
sum = 0;
}
}
System.out.println(max);
}
}
}
}풀이 2
문제 분류가 다이나믹 프로그래밍이어서 DP로 풀어보려 했는데 방법이 떠오르지 않아 DP를 이용해서 푼 풀이를 가져왔습니다. 위의 코드와 차이점은 배열을 이용해서 현재 i의 값과 직전 값과 현재 i의 값을 더한 게 더 클 때 arr[i]의 값을 직전 값과 현재 i의 값으로 바꿔주는 것입니다. DP의 메모리제이션을 이용해서 해결한 것 같습니다.
https://velog.io/@pss407/%EB%B0%B1%EC%A4%804097-%EC%88%98%EC%9D%B5
[백준]#4097 수익
문제연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.오늘이 창업한지 6일 되었고, 수익이 다
velog.io
정확한 풀이
import java.util.*;
public class Baek4097 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
int n = sc.nextInt();
int max = Integer.MIN_VALUE;
int sum = 0;
int[] arr = new int[n];
if(n == 0) {
break;
}
else {
for(int i = 0; i < n; i++) {
int x = sc.nextInt();
arr[i] = x;
if(i > 0) {
int y = arr[i-1];
if(x + y > x) { //직전 값과 현재 i의 값을 더한게 더 클 때
arr[i] = x + y;
}
}
}
max = Math.max(max, arr[i]);
}
System.out.println(max);
}
}
}단지 번호 붙이기 2667번
내가 떠올린 풀이 해설
상하좌우를 탐색할 int 배열 dx, dy를 선언합니다. 지도 크기를 입력받을 n, 2차원 배열의 map, DFS의 visit 배열, 총 단지 수를 구하기 위한 total, 각 단지에 속하는 집의 수를 구하기 위해 cnt를 선언해 주었습니다. BufferedReader를 이용해 입력을 받았습니다. map의 입력은 split를 이용해 잘라서 map의 2차원 배열에 넣어 주었습니다.(split("")[i]의 참고 자료: https://crazykim2.tistory.com/549) 전체 map을 탐색하기 위해 이중 for 문을 이용하였고 map의 (i, j)가 1이고 방문하지 않았다면 총 단지 수와 cnt의 수를 늘려주고 DFS를 호출합니다. DFS에서는 상하좌우 탐색을 진행하면서 cnt를 늘려줍니다. 마지막으로 cnt의 값을 List에 담아줍니다. 각 단지 내 집의 수를 오름차순으로 정렬하여 출력해 주어야 하므로 Collections.sort()를 이용해 정렬하였습니다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek2667 {
static int[] dx = {1, 0 ,0, -1};
static int[] dy = {0, 1, -1, 0};
static int n; // 지도 크기
static int[][] map;
static boolean[][] visit;
static int total = 0; // 총 단지 수
static int cnt;
static List<Integer> cnts = new ArrayList<>(); // 각 단지에 속하는 집의 수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
visit = new boolean[n][n];
String str;
for(int i = 0; i < n; i++) {
str = br.readLine();
for(int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(str.split("")[j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cnt = 0;
if(map[i][j] == 1 && !visit[i][j]) {
total++;
cnt++;
dfs(i, j);
cnts.add(cnt);
}
}
}
System.out.println(total);
Collections.sort(cnts);
for(int i = 0; i < cnts.size(); i++) {
System.out.println(cnts.get(i));
}
}
private static void dfs(int i, int j) {
visit[i][j] = true;
for(int k = 0; k < 4; k++) {
int nx = dx[k] + i;
int ny = dy[k] + j;
if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
if(!visit[nx][ny] && map[nx][ny] == 1) {
cnt++;
dfs(nx, ny);
}
}
}
}
}오늘의 회고
요즘 스터디와 공모전으로 너무 바빠서 코딩 테스트 문제를 풀지 못했더니 많이 까먹은 것 같습니다. 이제 곧 하반기 채용 시작인데 다시 코딩 테스트 공부를 좀 해야겠습니다. 알고리즘 너무 어려워 이번에 알고리즘 스터디에 참여하게 되었는데 다들 실력이 좋으셔서 놀랐습니다. 분발하자
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| LeetCode Valid Parentheses, Merge Two Sorted Lists (0) | 2022.10.03 |
|---|---|
| 프로그래머스 최솟값 만들기, JadenCase 문자열 만들기 (0) | 2022.09.23 |
| 백준) HashMap (0) | 2022.07.23 |
| 백준) BFS, 다익스트라 (0) | 2022.07.19 |
| 백준) 우선순위 큐, DP (0) | 2022.07.18 |
