일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- SpringBoot
- nextline()
- BufferedReader
- 백준
- A+B - 7
- Java
- 산술 연산자
- 서버개발
- 코딩테스트
- 11021
- 문자열메서드
- 15552
- 포맷팅
- 코딩은체육과목입니다
- 백준11021
- 백준15552
- 인스턴스화
- 연산자 우선순위
- 그라운드시소
- 비교 연산자
- A+B - 6
- BufferedWriter
- nextInt()
- 이너클래스
- 백준10953
- 인스턴스
- 10953
- 조건 연산자
- 알고리즘
- 논리 연산자
- Today
- Total
Coded by Juny
1859. 백만 장자 프로젝트 본문
미래를 예측하는 이가 하루마다 바뀌는 물건의 시세를 알고 있다.
테스트케이스 수, 시세 변동 날, 물건의 시세를 입력값으로 받는다.
미래를 예측하는 이의 가장 큰 이득을 예상하라는 문제였다.
예시로, 입력값이
3 //테스트 케이스 수
5 //케이스1의 시세 변동 총 날짜
1 2 3 4 5 //케이스1의 5일동안의 시세 변동
4 //케이스2의 시세 변동 총 날짜
2 5 1 3 //케이스2의 4일동안의 시세 변동
3 //케이스3의 시세 변동 총 날짜
5 4 3 //케이스3의 3일동안의 시세 변동
일 때,
출력값은 다음과 같다.
#1 10 // 1일부터 4일까지 물건을 구매해서 가장 높은 5일에 판매하면 예상 최대 이익은 4, 3, 2, 1을 더해 총 10
#2 5 // 3일의 5원때 2원으로 첫 째날에 구매해 3원의 이득과 3일차 때 1원으로 구매해 마지막날 3원으로 판매해 총 4원의 이득
#3 0 // 갈수록 하락하여 이득을 취할 수 없음
그렇게 가장 먼저 접근했던 방식은 시세가 점차 증가 추세일 때, 변수 down에 해당 시세 값을 더해주고 최고가에서 각 편차들을 더해주기 위해 temp 변수에 매 회마다 1씩 더해준다. 그 후 만약 최고가보다 최소값이 나왔을 때, 해당 최고가에서 temp를 곱한 후 down에 더해놨던 시세들을 빼주면 해당 최고가 그 전의 시세들의 이득들의 합을 더할 수 있다.
예시로, 입력값 테스트 케이스 1의 경우 5일차 최고가 전 까지 시세 1, 2, 3, 4들을 계산할 때까지 down의 변수는 10(1+2+3+4), temp 변수는 4(1+1+1+1)일 것이다. 5일차 때 최고가이므로 내가 생각했던 방법을 쓰면 5(최고가)*4(temp) - 10(down)으로 출력값은 10이 된다.
해당 방식의 코드는 다음과 같다.
import java.util.Scanner;
import java.io.FileInputStream;
class D2_1859
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int day = sc.nextInt();
sc.nextLine();
int[] dayCoin = new int[day+1]; //for문에서 다음 원소와 비교할 때 마지막 원소 비교를 위해 마지막에 0을 넣어줌
for(int i = 0; i < day; i++){
dayCoin[i] = sc.nextInt();
}
sc.nextLine(); // 줄바꿈을 없애줌
int result = 0; // 결과값
int down = 0; // 증가세일 때 전의 숫자를 더해줄 변수
int temp = 0; // 증가세일 때 전의 숫자를 더해 가장 최고가일 때 증가세의 합을 temp * 최고가에서 빼줄 때 사용할 변수
for(int i = 0; i < day; i++){
if(dayCoin[i] <= dayCoin[i+1]){
down += dayCoin[i];
temp ++;
}
if(dayCoin[i] > dayCoin[i+1]){
result += dayCoin[i]*temp - down;
down = 0;
temp = 0;
}
}
System.out.printf("#%d %d", test_case, result);
System.out.println();
}
}
}
일단 코드 작성은 내가 예상했던 방식으로 잘 짜여졌고 출력값도 잘 나왔다. 여기서 문제점을 몇개 꼽자면
1. 해당 문제는 상당히 많은 양의 데이터를 처리할 수 있고 많은 양의 테스트케이스가 존재할 수 있어서 배열을 다루는 로직 특성상 런타임 에러가 발생할 가능성이 있었다.
2. 배열을 계산하면서 처음 최고가를 찍고 다시 가격이 내려갈 때 이익을 계산하는 형태였는데 만약에 그 후에 계산했을 시점보다 더 높은 최고가가 나왔을 때를 감안해야하는지 궁금했다. 예시로 입력 케이스로 6일 동안 시세 변동이 1, 2, 3, 2, 4, 6으로 들어왔을 때, 내가 작성한 코드의 예상 출력값은 9가 될 것이다. 하지만 만약에 가장 최고가인 6으로만 계산한다면 출력값은 5+4+3+4+2로 18이 되어야 한다.
그렇게 2번의 케이스의 경우 코드를 돌려보고 수정하면 되는 것이므로, 코드를 실행해보았으나 역시 런타임 에러가 발생했다. 2의 문제여도 런타임에러는 수정하지 않는 한 또 일어날 것이므로, 1번 문제의 가능성을 중점으로 코드를 수정해보았다.
해결책을 생각하고 혹시나 해서, 각 변수들의 데이터타입을 long으로 바꾸어주었더니 런타임에러가 발생하지 않고 오답이라는 메시지가 떴다. 결국 2번문제가 이유일거라고 생각하고 배열을 사용하지 않는 것과, 시세처리 방식을 배열의 뒤에서부터 계산하기로 해보았다.
그렇게 수정된 최종 코드
import java.util.Scanner;
class D2_1859 {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
int day = sc.nextInt();
int[] prices = new int[day];
for (int i = 0; i < day; i++) {
prices[i] = sc.nextInt();
}
int maxPrice = 0;
long result = 0; // 이익 계산 변수 (long 타입으로 오버플로우 방지)
// 뒤에서부터 최대값을 찾아서 이익을 계산
for (int i = day - 1; i >= 0; i--) {
if (prices[i] > maxPrice) {
maxPrice = prices[i]; // 현재까지의 최대 가격 갱신
} else {
profit += maxPrice - prices[i]; // 현재 가격이 최대 가격보다 낮으면 이익 계산
}
}
System.out.printf("#%d %d\n", test_case, result); // 결과 출력
}
sc.close();
}
}
짜란! 접근 방식과 사재기 이득 계산 방식에 착오가 있었던 것 같다.
'Coding & Algorithm > 기타' 카테고리의 다른 글
Scanner - nextInt() & nextLine() (2) | 2024.10.18 |
---|