외부 문제 질문

자바 코딩테스트 - it 대기업 유제

작성

안녕하세요 강사님 혹시 괜찮으시다면

어디선가 봤는데 아직도 기억에 남는 코테 문제가 있습니다.

아직도 못풀고 제 머릿속에 남아있는데요 혹시 도움을 주실 수 있으면 감사하겠습니다.

문제는 아래와 같습니다.

N에 해당하는 개수의 숫자가 나옵니다

테스트 데이터

0 1 -1 2 -2 3

첫 줄 N은 0<=200,000 범위

수는 음의 정수 , 0 , 양의정수입니다.

위와 같이 숫자가 5개가 나오면 다 처음부터 더하는 것인데 여기서 n개의 수 중 딱 한개를 0으로 변환시킬 수 있습니다.

그랬을 때 0이 최대가 되는 개수가 몇인지 고르는 겁니다.

DP 문제인 것 같은데 아직도 해결을 못하겠네요..

가령 위 데이터에서는

처음은 0이니 0

두번째 1를 더해서 1

세번째 -1를 더해서 0

네번째 2를 더해서 2

다섯번째 -2를 더해서 0

여섯번째 3를 더해서 3입니다.

즉 0은 3개인데 여기서 0이 아닌 3개중 하나 아무거나 바꿔도 0의 최대 개수는 4개임으로

답은 4입니다.

이걸 어떻게 풀어나가야 할까요?

혹시 이러한 비슷한 백준문제나 프로그래머스 문제가 있으신가요?

도움 부탁드려요 ㅠㅠ

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

제가 문제 이해를 정확하게 했는지 모르겠지만 수열의 숫자 중 최대 한개까지만 0으로 바꾸어 첫 항부터 시작하는 누적합이 0이 되는 경우가 최대가 되도록 하는 문제라 이해했습니다. 아래는 제가 짜본 코드입니다.

이 문제는 누적합과 해시맵을 적절히 사용하면 O(n) 시간복잡도에 가깝게 해결할 수 있습니다.

아침에 짠거라 출근해야 해서 여러 케이스로 검증을 하지는 못했습니다. 시간날 때 검증을 해봐야 겠습니다.

import java.util.*;
class Solution {
	public int solution(int n, int[] nums){
		int answer = 0;
		HashMap<Integer, Integer> freq = new HashMap<>();
		int[] prefix_sum = new int[n];
		prefix_sum[0] = nums[0];
		for(int i = 1; i < n; i++) prefix_sum[i] = prefix_sum[i-1] + nums[i];
		int[] left_zero = new int[n+1]; //left_zero[i]값은 i번째 앞에까지 누적합 중 0의 개수
		for(int i = 1; i <= n; i++){
			if(prefix_sum[i-1] == 0) left_zero[i] = left_zero[i-1] + 1;
			else left_zero[i] = left_zero[i-1];
		}
		for(int x : prefix_sum){
			freq.put(x, freq.getOrDefault(x, 0) + 1);
		}
		answer = left_zero[n]; //아무것도 바꾸지 않았을 때 누적합 0의 개수
		for(int i = 0; i < n; i++){
			int tmp = left_zero[i] + freq.getOrDefault(nums[i], 0); // i번째를 0으로 변경했을 때 누적합 0의 개수
			answer = Math.max(answer, tmp);
			freq.put(prefix_sum[i], freq.get(prefix_sum[i]) - 1);  // i번째 숫자를 0으로 바꾸면 i번째 이후의 누적합만 변경되므로 그 이전 것은 다 지워줘야 함
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(6, new int[]{0, 1, -1, 2, -2, 3}));	
	}
}

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. youngyou1324님!

코딩테스트 문제와 관련하여 도움을 드릴 수 있는 자료를 찾아보았습니다. 그러나 이 문제에 해당되는 직접적인 자료는 찾기 어려웠습니다. 하지만 비슷한 유형의 문제가 여러 가지 있을 수 있는데요, 특히 동적 프로그래밍(DP) 접근법을 사용하여 배열을 탐색하고 이를 통해 원하는 결과를 도출해야 하는 문제들이 일반적입니다.

이제 문제에 대한 간단한 접근 방식을 설명드리겠습니다:

누적 합 계산: 주어진 수열을 두 번 순회합니다. 첫 번째는 원래의 누적 합을 계산하고, 두 번째는 한 원소를 0으로 바꾸었을 때의 상황을 각각 계산합니다.
0으로 바꾸기: 배열에서 각 원소를 0으로 바꾸면서, 그때의 누적 합 결과를 확인합니다. 각 경우의 수 마다 0이 발생하는 횟수를 기록합니다.
최적화된 계산: 매번 계산하는 대신, 이전 결과를 재활용하여 빠르게 계산할 수 있도록 구조를 잡습니다. 이를 통해 최다의 0이 발생할 수 있는 설정을 찾습니다.

비슷한 유형의 문제를 더 많이 풀어보시고, 그런 문제의 솔루션을 참고하시면 좋을 것 같습니다. 예시로는 프로그래머스의 ‘연속된 부분수열의 합’ 류의 문제가 있습니다. 이렇게 특정 조건 하에서 배열의 값을 조작해 최대화하는 문제를 집중적으로 분석해보세요.

아래는 알고리즘적 사고를 키우는 데 도움이 되는 링크를 소개합니다:
- 백준의 연속 부분합 문제
- 프로그래머스의 연속 부분수열 문제

위 링크들을 통해 기본적인 접근 방식을 익힌 뒤 응용하여 주어진 문제를 풀어보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

외부 문제 질문