뚝딱뚝딱

이전 내용↓↓↓

2023.11.13 - [Web Application/Backend] - [REST API] Spring Boot로 REST API CRUD 간단 구현 (3)

이전 포스팅에서 cloudVendor의 기본적인 CRUD가 동작하는 것을 확인하였다.

그런데 get mapping에서 cloud vendor가 존재하지 않을 때는 출력 시 오류가 발생하는 것을 확인하였다.

오늘은 이러한 오류가 발생했을 때, 즉 예외에 대해서는 어떻게 처리해야 하는지에 대해 알아볼 것이다.

✔ 웹 개발에 있어서 중요한 점

✅ 오류나 예외 상황 발생 시 사용자가 이해하기 쉽도록 상황에 대한 정보를 충분히 전달할 수 있어야 한다.

따라서 개발자는 로직 구현에 있어서 예외가 발생하는 부분을 찾아서, 예외처리를 해주어야 한다.

이제 프로젝트에서 발생한 오류를 가지고 예외처리를 해보자.

예외 처리를 하기 전에는 위와 같이 데이터베이스에 C3가 없을 때, C3를 get하는 mapping과정에서 반환 값이 없어서 에러가 발생하였다.

우리는 이를 CloudVendorNotFoundException이라고 할 것이다.

이 예외를 처리하기 위해서 다음 단계를 따른다.

1. 예외 처리를 위한 클래스들을 담은 exception 패키지를 하나 생성한다.

2. exception 패키지에 CloudVendorNotFoundException 클래스를 생성한다.

• 이 클래스를 예외 클래스로 인식하기 위해서 RuntimeException 클래스를 extends한다.
• 이 클래스에 대한 두 타입의 생성자를 자동생성해준다.
  - 인자로 message만 담은 생성자
  - 인자로 message와 Throwable 객체인 cause를 담은 생성자

*Throwable이 뭐야? (접은글을 확인하세요)

3. 클라이언트에게 예외 정보를 전달하기 위해서, 정보를 담는 CloudVendorException 클래스를 생성한다.

• 위 3개의 속성을 추가해준다. 
• 사용자에게 보여질 오류 메시지 = message
• 예외 정보 = throwable
• http 상태 정보 = httpStatus

• 기본 생성자와, getter들을 자동 생성해준다.

4. 이제 예외 처리를 할 CloudVendorExceptionHandler 클래스를 생성해준다. 프론트와 직접 연결되는 컨트롤러라고 생각하면 된다.

• 우리는 지금 CloudVendor를 찾을 수 없다는 예외에 대한 처리를 다루어야 하기 때문에, handleCloudVendorNotFoundException 메서드를 선언해주자.
• rest api이기 때문에 반환타입은 ResponseEntity로 하고, Object유형으로 반환하도록 한다.
• 그리고 예외 발생 시의 CloudVendorNotFoundException 객체를 인자로 받아서 이 메서드의 인수로 매핑되도록 한다.
• 로직 내에서는 예외 정보를 받아서 적절히 처리 후 반환해주어야 하기 때문에, 예외 정보를 담아 보낼 CloudVendorException 객체를 하나 생성한다.
• 인자로 받은 cloudVendorNotFoundException의 message와, cause, 그리고 HttpStatus를 not_found로 하여 생성되도록 한다.

• return 시에는 ResponseEntity에 로직내에서 생성한 cloudVendorException 클래스와 HttpStatus를 인자로 넣어 반환한다.
  
  

• 그리고 이 메서드가 어떤 예외를 처리할 지 알려줘야 하기 때문에, 메서드 위에 @ExceptionHandler라는 어노테이션을 추가해주고, 이는 메서드에 의해 처리될 예외의 목록을 value로 갖는다.
• 즉 CloudVendorNotFoundException이 발생하면 value에 명시되어 있기 때문에, 해당 메서드의 인자로 매핑될 수 있는 것이다. 만약 여러개의 Exception을 한 메서드에서 처리하는 경우, value가 {} 리스트 형태이기 때문에, 쉼표를 하고 여러 개를 추가로 작성해주면 된다.

• 마지막으로 CloudVedorExceptionHandler 클래스에 대해서 @ControllerAdvice 어노테이션을 달아준다
• 이 컨트롤러는 이 프로젝트 전반에 걸쳐서 전역적으로 여러 예외처리를 해야 하기 때문이다.

5. 이제 이러한 예외가 발생할 수 있는 위치로 돌아가서 어떻게 했을 때 예외가 발생하는 지 확인해야 한다.

• 서비스 레이어의 get 메서드에서 오류가 발행하였는데, 로직을 보면 return에서 findId를 호출하도록 되어 있다.
• findId를 통해 반환할 내용이 있다면, cloudVendor에 대한 정보가 출력되겠지만, 찾을 수 없다면 예외를 발생시키고 일반 내부 서버 오류 메시지가 표시된다.
• 따라서 예외 처리 기능을 추가함으로써 출력되는 메시지를 사용자가 오류에 대해 이해하기 쉽게 더 나은 메시지로 표시하고자 한다.
• 예외 처리 기능을 추가해준다.

• if문을 추가하여, findId 호출의 return이 비어있다면 예외를 표시하도록 한다.
  CloudVendorNotFoundException클래스를 throw 문법을 통해 발생시키고, 이때의 message는 오류에 대한 상황 설명을 친숙한 메시지로 제공해준다.
  => "requested cloud vendor does not exist"

6. 실행 결과

• 클라이언트가 제대로 수신한 적절한 오류 응답 404 not found와 함께 적절한 오류 메시지인 cloud vendor를 찾을 수 없다는 메시지가 출력된 것을 확인할 수 있다.

위 과정이 바로 Spring boot rest api 애플리케이션으로 예외 처리를 하는 방식이다.

= 사용자 정의 예외 처리

다음 내용↓↓↓

2023.12.15 - [Web Application/Backend] - [REST API] Spring Boot로 REST API CRUD 간단 구현 (5)-사용자 정의 ResponseEntity

https://www.acmicpc.net/problem/1005

💡 ACM Craft

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.
이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

위의 예시를 보자.
이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.
따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.
프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

[입력]
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 
둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 
마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.

[출력]
건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.
건설순서는 모든 건물이 건설 가능하도록 주어진다.

문제를 요약하자면..

1번부터 N번까지의 N개의 건물이 있을 때, 주어진 건설 순서 (1 2 = 1->2) 에 따라서 각 건물이 건설될 수 있다.

예를 들어 앞의 그림에 따르면, 2와 3은 1이 건설된 후에야 건설할수 있고, 4는 2와 3이 모두 건설된 후에야 건설할 수 있다.

각 건물을 건설하는데에는 DN의 시간이 소요되고, 입력으로 주어진다.

이때 입력으로 받는 건물 W를 건설하는데 소요되는 최소시간을 구하는 문제이다.

✅ 문제 풀이

W를 건설하기 위해서는 W하위에 연결된 모든 건물이 완료되어야 하기 때문에, W까지 연결되는 여러 경로 중 에서 소요되는 시간이 최대일 때와 같다.

=> 왜 최대이냐?

W가 건설되기 전까지는, W를 건설하기 위해 먼저 건설되어야 하는 건물들 모두가 건설을 마쳐야 W를 건설할 수 있기 때문에, 위의 예시처럼 건물 2가 1초 밖에 걸리지 않다 하더라도, 건물4가 건설되려면 건물3도 건설되어야 하므로, 둘 중 더 소요시간이 긴 건물 3에 의해 100초가 더해져야 한다. 따라서 총 10초(건물1)+100초(건물2,3)+10초(건물4)=120초가 소요된다.

따라서 이 문제는 위상정렬을 이용해서 해결할 수 있다.

다음 사항들을 고려해야 한다.

1. 각 건물(노드)을 건설한 바로 다음에 건설될 수 있는 건물들을 저장해야 한다.
=> vector<int> node[1005]를 vector 타입의 배열을 만들어서, 각 노드(인덱스=건물번호)에 이전 건물에 대한 정보를 vector로 추가해준다.

2. 각 건물까지 짓는데 걸리는 최소 시간을 저장하는 배열이 있어야 한다.

=> vector<int> sum(1005,0); 
=> 각 노드(인덱스=건물번호)에 저장한다.

3. 각 건물에 대한 깊이를 저장하는 배열이 있어야 한다.
=> 예시에서 보면 1은 선행 노드가 없으므로 깊이가 0, 2와 3은 선행노드가 1이 있으므로 1, 4는 선행노드가 1, 2-3이 있으므로 2이다. 

=> vector<int> degree(1005,0)

이제 코드를 하나씩 만들어가 보자.

• 테스트 케이스 T를 받아 저장한다.
• T번의 테스트 케이스를 진행하도록 for문을 작성하고, for문 안에서 아래 내용들이 동작하도록 구현한다.
• 건물을 개수를 입력받아 N에 저장한다.
• 건설 규칙의 개수를 입력받아 K에 저장한다.
• 다음을 미리 선언해준다.
  ✔ vector<int> D(1005,0) : 각 건물의 건설시간을 담은 크기가 1005인 벡터 D
  ✔ vector<int> sum(1005,0) : 각 건물을 완성하기까지 걸리는 시간을 담은 크기가 1005인 벡터 sum
  ✔ vector<int> node[1005] : 각 건물의 후행 건물을 담은 벡터 타입의 크기가 1005인 배열 node
  ✔ vector<int> degree(1005,0) : 각 건물(노드)의 깊이를 담은 크기가 1005인 벡터 degree
  =>값은 모두 0으로 초기화 
• 각 건물의 건설시간을 건물 번호에 맞게 차례로 입력받는다.
  => 벡터 D의 1번 인덱스부터 1번 건물의 건설 시간을 입력받아 저장한다.
  => 그리고 sum의 동일한 인덱스에 입력받은 각각의 건설 시간을 저장해준다. sum에는 일단 각 건물에 대한 건설시간이 저장되어 있는 것이다. = 만약 맨 아래 노드라면 해당 건물을 짓는데는 해당 건물의 건설시간만 소요될 것이므로 미리 값을 지정해준다.
• K개의 건설 규칙을 입력받자. for문을 연다.
• 건설 규칙을 입력받기 위해 선행 건물을 저장하는 x와, 후행 건물을 저장하는 y를 선언하고, 입력받아 저장한다.
• node[x]에다가 y를 넣어준다. 현재 이 배열은 벡터 타입이므로 push_back하여 y를 저장한다.
•  그리고 y 이전에 x가 먼저 건설되기 때문에, y는 선행 노드가 있다는 것이므로, degree[y]를 1 늘려줘서 깊이를 1 높인다.
• 이렇게 K개의 규칙에 대해 다 실행한 후 for문이 끝나면 경로를 하나씩 접근해가며 sum을 갱신할 수 있다.
• 그 전에 W를 입력받아서 저장해둔다.모든 건물의 sum을 구한 후 그중 sum[W]를 통해 W건물까지 짓는데 걸리는 최소시간을 구할 수 있다. 다음을 진행하여 sum을 설정하자.
• queue<int> q를 하나 생성하여 방문할 노드들을 저장하는 용도로 사용하자.
•  일단 모든 건물(=노드)를 for문을 통해 돌아보면서, 현재 노드의 degree가 0인지 확인한다.
• 현재 노드의 degree가 0이라면, 선행 노드가 없다는 것이므로, q에 현재 노드를 push한다.
• for문을 다 돌면, while문을 통해 q가 빌 때 까지 다음을 수행한다.
• q의 맨 앞에 있는 노드를 꺼내 top에 저장한다. 그리고 node[top]에 저장된 모든 후행 노드를 순회하면서 next에 저장한다.
• 만약 sum[top]+D[next] 가 sum[next]보다 크다면 sum[next]를 전자로 갱신시켜준다. =>이게 바로 같은 레벨에서는 최대로 걸리는 값으로 갱신해야 한다는 의미이다. 같은 레벨에 있는 건물은 다음 건물 짓기 전에 모두 건설완료되어야 하기 때문에 가장 오래 걸리는 건설 시간을 반영한다는 뜻이다.
• 그리고 degree[next]를 1 줄여서 선행 노드를 이미 방문했음을 표시한다.
• 그리고 degree[next]가 0이면 이 노드를 시작으로 위 과정을 반복하기 위해 q에 push한다.
• 그럼 while문을 충족하므로 과정을 반복한다.
• 맨 마지막 노드에서 degree[next]를 1 줄임으로써 0이 되면서 while문이 종료되고, 각 노드에 대한 최종 sum이 설정되었을 것이다.
• 그럼 이때 sum[W]를 출력하여 프로그램을 마친다. 

☑ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int N, K, W, top, next;
		vector<int> D(1005, 0);//각 건물의 건설시간
		vector<int> node[1005];//노드 별 이어지는 노드 
		vector<int> degree(1005, 0);//루트로부터 몇번째에 있는지
		vector<int> sum(1005, 0);//현재 노드까지의 총 건설 시간
		queue<int> q;

		cin >> N >> K;
		for (int j = 1; j <= N; j++) {
			cin >> D[j];
			sum[j] = D[j];
		}
		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> x >> y;
			node[x].push_back(y);
			degree[y]++;
		}

		cin >> W;
		for (int j = 1; j <= N; j++) {
			if (!degree[j]) {//내 아래로 없으면
				q.push(j);//이 노드의 후행 노드들을 살펴보자
			}
		}
		while (!q.empty()) {
			top = q.front();
			q.pop();
			for (int j = 0; j < node[top].size(); j++) {
				next = node[top][j];
				if (sum[top] + D[next] > sum[next]) sum[next] = sum[top] + D[next];
				degree[next]--;
				if (!degree[next]) q.push(next);
			}
		}

		cout << sum[W]<<"\n";

	}
	return 0;
}

https://www.acmicpc.net/problem/1026

💡 보물

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

첫째 줄에 S의 최솟값을 출력한다.

✅ 문제 풀이

크기가 각각 N인 A와 B배열을 입력받은 뒤, B는 그대로 두고, A만 재정렬 하여 A와 B의 원소를 각각 곱해서 최소의 값이 되도록 하는것이다.

여기서 구하고자 하는 것은 그때의 최소값이다.

따라서 A와 B가 어떻게 정렬이 되어 있던 간에, 결국 최소 값을 구하기 위해서는 한쪽은 가장 큰 값, 다른 한쪽은 가장 작은 값을 곱한 것이 최소가 된다.

따라서 A를 오름차순 정렬하고, B를 내림차순 정렬한 후에 각각의 원소끼리 차례로 곱한 값들을 더해주면 최소값이 나오게 된다.

B는 그대로 두되, A를 "재정렬" 하라는 말에 너무 초점을 맞추게 되면, 생각이 많아질 수 있으나, 목적인 최소값을 생각하면 쉽게 해결하는 문제이다.

☑ 코드 전문

#include<iostream>
#include<algorithm>

using namespace std;

bool compare(int a, int b) {
	return a > b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int *A = new int[N];
	int *B = new int[N];
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	sort(A, A + N);//오름차순
	sort(B, B + N, compare);//내림차순

	int answer = 0;
	for (int i = 0; i < N; i++) {
		answer += A[i] * B[i];
	}
	
	cout << answer;

	return 0;

}

https://www.acmicpc.net/problem/1010

💡 다리 놓기

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

입력
3
2 2
1 5
13 29

출력
1
5
67863915

✅ 문제 풀이

• 주어진 조건을 보면, n개의 사이트가 항상 일정한 순서대로 m개의 사이트와 연결되어야 하기 때문에, 순서를 고려하지 않는 경우의 수만 구하면 된다.
• 따라서 m개의 사이트 중 n개를 고르는 조합 문제이다.
• mCn을 코드로만 구현하면 된다.
• mCn의 수식을 보면 m에서 하나씩 줄여가면서 n개의 수를 곱하고, 1부터 n까지를 곱한 값을 나누어 주면 총 경우의 수와 같다.

☑ 코드 전문

#include<iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;


	for (int i = 0; i < T; i++) {
		int n, m;
		cin >> n >> m;

		long answer = 1;
		int k = 1;
		for (int j = m; j > m - n; j--) {
			answer *= j;
			answer /= k;
			k++;
		}

		cout << answer << "\n";
	}
	return 0;
}

소프티어 부트캠프 3기 코딩테스트를 보고 온 후기이다.

일단.. 2개는 완벽히 풀었다고 생각했는데, 갑자기 끝나고 나서 치명적인 실수를 해버린게 생각났다.

그리하여 예상은 1솔..

일단 전체적인 총평은.. 너~~무 어려웠다. 

문제 자체가 설명이 너무 길고, 복잡하기도 하고, 읽고 있는데 무슨 말인지를 모르겠다.

그래서 일단 간단해 보이는 문제를 먼저 풀이했는데, 하나는 모의 테스트에 나온 걸 입력 형태를 조금 변형해서 냈고, 그냥 똑같은 문제였다.

다른 하나는 계수기 만들기 문제인데, 하...이걸 진짜 열심히 생각해냈는데, 마지막에 답을 아무생각없이 내가지구.. 다 푼걸 딱 한번 생각을 못해서 틀린 케이스이다. 일단 테케는 통과했는데, 문제에서 예시로 나온 것만 넣어봤어도 바로 수정했을텐데, 내가 봤을 땐 트릭으로도 이 예제를 테케에 안넣어둔 것 같다.

너무 아쉬운 ... 코테였다.

그리고 소프티어 부캠 코테는 문제를 pdf 사진으로 첨부해놓는데, 처음에 이 pdf가 열리지 않아서 문제를 확인할 수가 없었다. 다행히 시스템 문제였고, 이것 땜에 전체가 20분 늦게 시작했다. (좀 서툰 느낌..?)

문제는 총 7문제, 시간은 6시 20분 부터 8시 40분까지 총 140분 봤다.

1번 문제는, 배?인가 어디에 입력으로 주어진 것들을 태우는데, 뭐 농부랑 뭐가 같이 타면 안되고..이런 조건이 엄청 많았다. 문제 이해부터 안되서 패스했다.

2번 문제는 bfs인 것 같기도 하고.. n개의 마을이 있고 연료가 k일 때 주어진 경로에서 물건을 사고 팔고.. 그때의 비용이며.. 아무튼 최종 답은 최대의 이익을 내는 경로와, 그 때의 최대 이익, 그리고 잔여 연료를 출력하는 것이었다.

소프티어 입력도 출력도 너무 복잡해서 솔직히 힘들었다.

3번 문제는 이전 부캠 코테 기출을 좀 더 난이도 높혀서 변형한 느낌. 

백준에 있는 쿼드 트리 문제 같은 느낌인데, 그런 배열을 하나 주고서는, 0은 물 1은 섬이라고 하고, 강의 넓이와 그 안에 있는 섬, 강의 넓이를 계속 출력하는 문제였다. 분할과 정복 문제 인 것 같다.

4번 문제는 모의고사로 나왔던 문제이다. 배열에서 연속적인 영역의 개수와 영역의 크기를 구하는 문제이다. bfs 문제이다.

5번 문제는 도메인 주소와 ip 주소를 이용하는 것이었는데, 입력으로 유형을 적어서 도메인을 등록하거나 검색하도록 하는 것이다. 이것도 너무 복잡..

6번 문제는 계수기 만들기 문제.. 이거 첨에 포기하려다가 끈질기게 잡고 겨우 풀어냈는데, 마지막에 출력 내는 과정에서 실수가 있었던 게 생각나 버려서 아깝게 1솔 버려졌다... ㅠㅠ

7번은 뭐였는지 기억이 안난다.

정말 하고싶었는데... 코드만 봐서라도 합격 시켜줄 순 없는 건가요...ㅠㅠ

좋은 소식으로 찾아왔으면!

https://www.acmicpc.net/problem/1806

💡 부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

입력예시
10 15
5 1 3 5 10 7 4 9 2 8

출력예시
2

✅ 문제 풀이

부분합이라고 해서 무조건 크기가 N인 배열에 누적합을 구해 놓으면 해결될 문제가 아니다.

이 문제에서 핵심은 "한번만" 순회하여 해결해야 한다는 것이다.

처음에는 for문 안에 부분 while문을 넣어서 결론적으로는 o(n^2)의 시간복잡도로 구현하였다. 결과는 역시 시간초과였다.

부분합 문제는 특히 o(n)으로 해결해야 한다.

그럼 어떻게 해결할 수 있을까?

문제를 풀면서 인지하고 있었던 것은, 앞에서부터 누적해 나가되, 그 값이 S이상이 되면 멈추는 것이다. 그리고 다시 앞에서부터 하나씩 줄여갔을 때에도 여전히 S이상이라면 이전 보다는 더 짧은 길이가 될 수 있다는 점이다.

그러면 여기서 알 수 있는 점은, 시작 점과 끝점을 가리키는 두개의 포인터가 필요하다는 것이다.

우리는 그것을 st, en이라고 할 것이다. 그리고 그 값은 각각 1부터 시작한다.

그리고 부분합을 가리키는 total을 선언하고, st와 en이 현재 1을 가리키므로, total은 수열의 1번째 값을 갖도록 한다.

answer는 최소 길이인데, 현재 수열의 최대 값은 100000이기 때문에, 초기값을 100001로 설정하여 min값을 찾아가도록 한다.

이제 while문을 통해 수열을 순회하는데, 시작점인 st는 끝점인 en보다는 작거나 같아야 하며, en이 N과 같아질 때까지 순회하도록 한다.

그리고 아래의 조건에 따라 수행한다.

만약 현재 total이 S보다 크다면, 조건을 만족한 것이므로, 현재의 answer값 (st-en+1)=현재 total을 이루는 길이를 비교해서 더 작은 값으로 answer를 갱신한다.

만약 total이 S보다 작다면, en을 하나 늘려서 다음 값을 total에 누적해주고, total이 S보다 크다면, total에서 st가 가리키는 값을 빼준 후 st를 하나 줄여준다.

=> 이렇게 되면, st를 줄였을 경우에도 total이 S조건보다 커서 answer가 더 작은 값으로 갱신될 수 있기 때문에, 이런식으로 한번의 순회로 답을 찾아갈 수 있는 것이다.

순회가 끝나고 난뒤에는, answer가 초기값 100001이 아니라면 한번이라도 S보다 큰 부분합이 있었다는 것이므로 answer를 출력하고, answer가 초기값 그대로였다면, S보다 큰 부분합이 없었다는 것이므로 0을 출력하도록 한다.

전체코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, S;
	cin >> N >> S;

	vector<int> vec(100001, 0);

	for (int i = 1; i <= N; i++) {
		cin >> vec[i];
	}

	int answer = 100001;
	int total = vec[1];//첫번째 값부터 담아서 시작
	int st = 1;//시작 포인터
	int en = 1;//끝 포인터

	while (st <= en && en <= N) {
		if (total >= S) answer = min(answer, en - st + 1);
		if (total < S) {
			en++;
			total += vec[en];
		}
		else {
			total -= vec[st];
			st++;
		}
	}

	if(answer!=100001) cout << answer;
	else cout << 0;

	return 0;
}