첫 코딩테스트. 완전 망이다.
접근 자체를 너무 소프트하게 가져가는 것 같다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제는 아래와 같다
25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.
예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.
위의 문제를 읽는 순간 나의 접근은 "for 문을 돌려서 최대값과 그 자리를 찾고, 자 자리로부터 앞의 값들을 FOR문을 돌려 합한 후 (최대값 * 자리-합)으로 처리"하려 했다.
즉 아래와 같다.
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
//케이스 수
int listCnt;
listCnt=sc.nextInt();
//날짜 수
int[] array =new int [listCnt]; //날짜
int max=0; //최대값
int place =0;//자리
int buy=0; // 구매저장
int income =0;//수익
int start=0; //시작구간
for(int test_case = 1; test_case <= T; test_case++)
{
for (int a=0; a<array.length; a++) {
array[a]= sc.nextInt();
}
while(start<array.length){
for (int b=start; b<array.length; b++)
{
if(max<array[b])
{
max=array[b];
place = b;
}
}
for(int c =start; c < place; c++)
{
buy = buy + array[c];
}
income = (max*place) - buy;
System.out.println("buy : "+ buy+"income: "+income);
start = place+1;
}
}//test_case
} //main METHOED
}//CLASS
근데, CASE가 많거나 날짜(listCnt)가 많아질수록 메모리를 쳐먹고, 결국 out of memory 현상이 발생한다.
이것이 바로 문과에서 코딩을 시작한 나의 한계이다.
최적화는 무슨, 나의 경우 프로그래밍은 언어와 같으며 읽기 편하고 검증이 잘돼야 한다고 생각 했는데 이런 것들이 '무지한 나의 합리화'라고 생각 하게 만들었다.
문제를 자세히 바라보면 나의 접근 방법은 정말 단순하다. 만약, 코딩이아니라 논리적으로 효율적인 사고를 한다면
- 뒤에서부터 최대값을 구하는 과정을 통해 해당날짜마다 그 이후로의 최대값을 기억해둔다.
- 이후로의 최대값과 같으면 차익이 없고, 최대값보다 작으면 그 차이만큼의 차익을 낼 수 있다.
라고 간단하게 생각 하면 되는 문제다...
앞에서부터 비교하기보다 이미 최대값을 알 수 있는 조건인 만큼, for문을 통해 뒤에서부터 값을 저장하면서 최대값을 찾고 최대값이 존재한다면 최대값에 저장하고 최대값보다 작다면 차익을 저장하는 방법으로 가면된다.
아래는 답안지라 할 수 있다.
SWEA 1859 백만 장자 프로젝트 - 제타위키
다음 문자열 포함...
zetawiki.com
import java.util.Scanner;
class Solution {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int t=1; t<=T; t++) {
int i, N = sc.nextInt();
int nums[] = new int[N];
int maxs[] = new int[N];
for(i=0; i<N; i++) nums[i] = sc.nextInt();
int max = 0;
for(i=N-1; i>=0; i--) {
if( nums[i] > max ) max = nums[i];
maxs[i] = max;
}
long sum = 0;
for(i=0; i<N; i++) sum += maxs[i] - nums[i];
System.out.format( "#%d %d\n", t, sum );
}
}
}
댓글