Do It Al-go -2차원 구간합

본 포스팅은 Do-it 알고리즘 코딩테스트 자바를 기반으로 작성되었습니다.  

1.Intro

 사실 한 주간 취업 최종 합격 결과가 나와서 급하게 집 계약하고, 현재 다니고 있는 강의도 중도 퇴사 절차를 밟고, 필요한 가구 등을 준비하고 새로운 노트북을 받는 다사다난한 한주였기에,, 정말 코드를 한 줄 도 치지 못했다. 오늘이 되어서야 안정이 되어 오랜만에 알고리즘을 풀어봤고, 지난번에 이어 구간합 2차원 배열 문제이다. 

 

  * @date 2024/6/1
  * 2차원 구간합 
  * 2차원 구간합 채우는 공식 
  * D[i][j] = D[i][j-1] +D[i-1][j] - D[i-1][j-1] + A[i][j]
  * 2차월 구간합 도출 공식
  * x, y , X, Y 에 대한 질의 
  * D[X][Y] - D[x-1][Y] - D[X][y-1] + D[x-1][y-1]
  * */
	
	/** @throws IOException 
	 * @sudoCode
	 *  N(배열 크기) M(질의수) 저장하기 
	 *  for(N만큼 반복){
	 *  	for(N만큼 반복){
	 *  	원본 배열 저장 
	 *  	}
	 *  }
	 *  
	 *  for(N만큼 반복학){
	 * 		for(N만큼 반복){
	 * 			합 배열 저장 
	 * 		 D[i][j] = D[i][j-1] +D[i-1][j] - D[i-1][j-1] + A[i][j]
	 * 		}	
	 *  }
	 *  
	 *  for(M만큼 반복){
	 *  	질의 계산 및 출력
	 *  	result = D[X][Y] - D[x-1][Y] - D[X][y-1] + D[x-1][y-1];
	 *  }
	 * */

간단하게 교재에서 다루고 있는 내용과, 교안에 나와있는  Sudo 코드인데, 확실히 수도 코드를 짜보니까, 코드를 직접 짤 때 가아드 라인이 있는 것 처럼 느껴져서 이러한 습관화를 위해 지속적인 노력을 기울어야 할 것 같다고 생각했다.. 

 

2.Method

	public static int sectionSum2(int N, int M) throws IOException {
		//입 출력 셋팅
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		//결과 값 초기화
		int result = 0;
		
		int[][] D = new int[N+1][N+1];
		
		/**@Defined 2차언 배열 설정*/
		for(int i = 1; i<=N; i++) {
			// 차례대로 배열 값 입력받기
			System.out.println(String.format("S=%s, N=%s", i, N));
			st = new StringTokenizer(br.readLine());
			for(int j =1 ; j<=N; j++){
				D[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println("세팅 완료");
		/**@Defined  구간합 설정*/
		int SectionSumD[][] =  new int[N+1][N+1];
		for(int s=1; s<=N; s++) {
		
			for(int j=1; j<=N; j++) {
				SectionSumD[s][j] = SectionSumD[s][j-1] + SectionSumD[s-1][j] -SectionSumD[s-1][j-1] + D[s][j];
			}
		}
		System.out.println(SectionSumD.toString());
		
		System.out.println("구간합 세팅 완료");
		/**@Defined  구간합 도출*/
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());			
			//2차원 배열 구간합 구하는 공식
			result =  SectionSumD[x2][y2] - SectionSumD[x1-1][y2] - SectionSumD[x2][y1-1] + SectionSumD[x1-1][y1-1];
			System.out.println(result);
		}
		return result;
		
	}

우선 전체적인 코드이다. 중간중간 주석을 참고 하면 될 것인데 이 코드를 짜는데 1시간 정도 소요 된 것 같다. 

코드를 짜는 시간은 전체적으로 길지 않았으나, 공식에 대한 올바른 이해, 디버깅에 1시간 정도 사용한 것 같다.. 

 

우선 가장 시간이 오래걸렸던 디버깅 포인트는 

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//결과 값 초기화
		int result = 0;
		
		int[][] D = new int[N+1][N+1];
		
		/**@Defined 2차언 배열 설정*/
		for(int i = 1; i<=N; i++) {
			// 차례대로 배열 값 입력받기
			System.out.println(String.format("S=%s, N=%s", i, N));
			st = new StringTokenizer(br.readLine());
			for(int j =1 ; j<=N; j++){
				D[i][j] = Integer.parseInt(st.nextToken());
			}
		}

어느 포인트가 잘 못되었는 지 알겠는가,,? 나는 여기에 가장 많이 시간을 쏟은 것 같다.

바로 해당 포인트는 Method 실행시  불필요한 readLine 을 한번 받는데, 이게 화근이었다. 

계속 내 예상보다 한 바퀴를 더 돌아, 애꾿은 for 문 만을 원망하고 있었지만 역시나 나의 실수였다..ㅎㅎㅎ

 

그래서 위 코드를 아래와 같이 바꿔준다. 

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		//결과 값 초기화
		int result = 0;
		
		int[][] D = new int[N+1][N+1];
		
		/**@Defined 2차언 배열 설정*/
		for(int i = 1; i<=N; i++) {
			// 차례대로 배열 값 입력받기
			System.out.println(String.format("S=%s, N=%s", i, N));
			st = new StringTokenizer(br.readLine());
			for(int j =1 ; j<=N; j++){
				D[i][j] = Integer.parseInt(st.nextToken());
			}
		}

 이 오류를 찾는데 오래 걸린 이야기는 습관적인 초기화가 아닐까 생각한다. 스프링 작업을 하게 되면 Autowired 를 통해 멤버변수로 선언하는 경우가 종종 있긴 하지만 순정 자바에서는 저렇게 사용한 경우가 별로 없어서 이다..ㅎ 

 

 

3.Outro

아무튼 6월이 밝았다. 많은 일이 있었고, 힘을 좀 비축했던 시간이었던 5월, 6월 부터는 다시 예전 텐션으로 돌아가본다고 오늘. 다짐해본다. 

 

아마 조만간 비전공자 신입사원 포스팅을 진행하지 않을까 싶다. !