마쏘's 개발 성장기

입력)

학생의 수 1000명

각 학생의 점수는 0점 이상 100점 이하의 값

출력)

최빈수를 출력

최빈수가 여러 개 일 때에는 가장 큰 점수를 출력

입, 출력 분석)

(생략)

예시 분석)
(생략)

핵심)

히스토그램을 한 번이라도 구현해본 적이 있다면 엄청 쉬운 문제다.

0부터 100까지의 점수를 index로 가지는 배열을 만들어 빈도수를 다루는 것이 핵심이다.

1000명의 점수를 읽으면서 배열[점수]에 해당하는 count를 올려주면,

해당 배열을 앞에서부터 count 같거나 크다면 갱신해주면 된다.

실수)
- 처음엔 빈도수가 같을 때 큰 수를 출력한다는 조건을 까맣게 잊고 있다가

   if(cnt < student[n]) => if(cnt <= student[n]) 로 수정하였다.

- 마지막으로 들어오는 입력이 테스트 케이스 번호 + 1000개의 숫자들이라서,

   scanf("%d", &test_case);를 삽입하였다.

구현)

#include<iostream>
using namespace std;
int N = 1000;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		scanf("%d", &test_case);
		int MODE = 0;
		int student[101] = {0,};
		int score = 0;
		for (int n = 0; n < N; n++) {
			scanf("%d", &score);
			++student[score];
		}
		int cnt = student[0];
		for (int n = 1; n < 101; n++) {
			if(cnt < student[n]) {
				MODE = n;	
				cnt = student[n];
			}
		}
		printf("#%d %d\n", test_case, MODE);
	}
	return 0;
}

배열과 index로 설계를 했지만 코딩을 하다보면 나도 모르게 헷갈리는 경우가 있는 것 같다.

그리고 개발자는 여러 경험들을 통해 만들어진 습관이나 편견을 조심 또 조심해야하는 것 같다.

모든 문제를 꼼꼼히 보고 기억하는 습관을 들이자!

입력) 

자연수 N(2 ≤ N ≤ 1,000,000)

각 날의 매매가를 나타내는 N개의 자연수들(10,000이하)

출력)

최대 이익을 출력

입, 출력 분석)

최대 이익 = 10,000이하의 자연수들 * 1,000,000개 

최악의 경우 10,000,000,000이 나온다.

예시 분석)

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

위 경우 2번째 날까지 사고(cost:2), 3번째 날에 팔았고(profit:3*2 - cost),

4번째 날에 사고(cost:1), 5번째 날에 팔았다면(profit:1*2 - cost),

이익은 (6-2)+(2-1) = 4+1 = 5이다.

위 경우  5번째 날까지 사고(cost:7), 6번째 날에 팔았다면(profit:4*5 - cost),

이익은 13이다.

핵심)

들어오는 수열에서 가장 큰 수를 찾아서,

'가장 큰 수 * 이전 수열까지의 개수' - '그 이전의 수열까지의 합'을 구하고,

이후 수열부터 이런 과정을 수열이 끝날 때까지 반복하면 된다.

핵심은 알았는데 1,000,000개의 수열에서 어떻게 제일 큰 수를 먼저 찾지..?
한참 고민하다가 힌트를 얻었다..ㅎ https://blog.naver.com/hongjg3229/221467996183

뒤에서부터 큰 수를 갱신해오면서 이익을 더해주니 금방 PASS 했다.

구현)

#include<iostream>
using namespace std;

int arr[1000000];
int N;

int main(int argc, char** argv){
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i){
			scanf("%d", &arr[i]);
		}
		long long profit = 0;
		int maxIdx = N-1;
		for (int idx = N-2; idx >= 0; --idx){
			if(arr[idx] < arr[maxIdx]) profit += arr[maxIdx] - arr[idx];
			else maxIdx = idx;
		}
		printf("#%d %lld\n", test_case, profit);
	}
	return 0;
}

상반기 끝나고 한 달 놀고 왔더니 머리가 단단히 굳은 것 같다....

앞으로 더 꾸준히 하면 된다! 아자아자!

Difficulty 단계별로 풀어보면서 공부를 해보려고 한다.

시작은 가볍게 D1 중 가장 추천을 많이 받은 문제로 열었다.

핵심) 짝수와 홀수의 개념이다.홀수는 2로 나눈 몫이 1인 수이고, 짝수는 2로 나눈 몫이 0인 수이다.

오늘은 무조건 스타트를 끊으리라 다짐했기에 보자마자 풀 수 있는 문제로 골랐지만,

내일부터는 D2 문제를 제대로 풀 것이다.

시작이 반이다! 할 수 있다!