[SWEA] JAVA | 다시 풀어볼 문제들 기록(1) (feat. 누적합 알고리즘)

이러다 모든 기업의 코테 플랫폼을 다 접해볼거같다. 문제는 쉬운 문제들만 찔끔 건들이다 끝난다는거.. 깊이란 없고 얕게 찔러만 보는 블로그다. 나름 내 포트폴리오였는데 도움이 되는 걸까 이게..!

여하튼 문제 풀때마다 기본이 많이 부족한게 스스로 느껴진다. 이번 주말부터는 백준에서 유형별로 문제 풀이 방식이나 노하우를 좀 익혀야겠다. 

 

[SW Expert Academy] https://swexpertacademy.com/main/main.do

SW Expert Academy

이번에는 SW Expert Academy 문제 풀이 시작했다. 장기적으로 코테 언어를 자바로 가져가는게 좋을거같아 바꿨다. 자바 진짜 입력값 받는것부터가 왜이렇게 긴건지.. 난이도 1 부터 차근차근 푸는 중인데 난이도 2 올라가서부터 쪼금씩 막히는 문제들이 생긴다. 고로 이 포스팅은 한번에 못 풀고 다른 코드 참고했다던가, 다시 풀어보는게 좋을 거 같은 문제들 기록이다.

 

---

 

 

1859. 백만 장자 프로젝트 (D2, 33%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

최대 이익을 낼 수 있는 방법은 최대 가격으로 팔 수 있을 때 파는 것이다. 고로 매매가가 최대일 때 판매하고 이전까지는 계속 사들인다. 최대 매매가가 배열의 중간에 있을 땐, 중간에 판매하고 다시 사들인 다음 그 다음 최대가일때 판매하는 것을 반복한다. 그리고! 매매가가 높을 때 많이 팔아야함으로 뒤에서부터 순회해야한다. 이 포인트는 혼자 풀면 절대 생각 못했을 것 같다. 

모든 순회를 끝낸 후 매매가와 판매가를 계산해 이익을 얻는 것이 아니라, 매 순회마다 얻을 수 있는 이익(판매가-매매가)을 계산하여 이익만 구한다.

public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
   
   int T = sc.nextInt();
			
   for(int i=0; i<T; i++) {
      int n = sc.nextInt();
		
      List<Integer> nlist = new ArrayList<Integer>();
      for(int j=0; j<n; j++) nlist.add(sc.nextInt());
		
      long ans = 0; 
        
      int max = nlist.get(n-1); // 뒤에서부터 순회(max가 판매 가격)
      for(int j=n-2; j>=0; j--) {
         // 판매 가격이 아직 더 높을 때 그날 구매하여 max 가격으로 판매
         // 이익 = max(판매가격)-nlist[j](현재 구매가격)
         if(max>nlist.get(j)) ans+= (max-nlist.get(j)); 
         // 판매 가격이 더 높아지면 판매가격을 바꿈
         else max=nlist.get(j); 
      }
		
      System.out.printf("#%d %d\n",i+1, ans);
   }
   sc.close();
}

** 정답을 처음에 int형으로 반환했는데 이리저리 참고해보니 long 타입이여야 통과 가능하다 한다.

 

참고한 블로그1) https://thisismi.tistory.com/entry/SW-Expert-Academy-1859-%EB%B0%B1%EB%A7%8C-%EC%9E%A5%EC%9E%90-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8

[SW Expert Academy] 1859. 백만 장자 프로젝트 파이썬 정답 코드

참고한 블로그2) https://dundung.tistory.com/119

SWEA 1859 백만 장자 프로젝트 Java

 

 

1983. 조교의 성적 매기기 (D2, 58%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PwGK6AcIDFAUq

뭔가 키와 그에 따른 값이 주어지고 정렬이 필요할 때 난 늘 map을 가지고 연산하려는 습관이 있다. 파이썬 문제풀이의 습관인지..

망한 나의 첫번째 풀이는 map을 value 기준으로 정렬하여 k번째 해당하는 학생의 점수를 가져오려 하였다.

public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
		
   int T = sc.nextInt();
   for(int test_case=0; test_case<T; test_case++) {
      int n = sc.nextInt(); // 학생 수  
      int k = sc.nextInt(); // 알고 싶은 학생의 번호 
			
      Map<Integer, Float> scoremap=new HashMap<>(); 
      for(int i=0; i<n; i++) {
         float mid = sc.nextFloat();
         float fin = sc.nextFloat();
         float assign = sc.nextFloat();
         float score = (float)((mid*0.35) + (fin*0.45) + (assign*0.2));
				
         scoremap.put(i+1, score);
      }
			
      // (등급읇 부여하기 위해) map value 기준으로 내림차순 정렬하기 
      List<Map.Entry<Integer, Float>> entrylist = new LinkedList<>(scoremap.entrySet());
      entrylist.sort(new Comparator<Map.Entry<Integer, Float>>() {
         @Override
         public int compare(Entry<Integer, Float> o1, Entry<Integer, Float> o2) {
            return (int)(o2.getValue()-o1.getValue());
         }
      });
			
      int grade = 0;
      String[] gradelist={"A+", "A0", "A-", "B+", "B0", "B-", "C+", "C0", "C-", "D0"};
      for(Map.Entry<Integer, Float> entry: entrylist) {
         grade+=1;
         if(entry.getKey()==k) {
            System.out.printf("#%d %s\n",test_case+1,gradelist[grade-1]);
         }
      }
   }
}

난 저 map의 Entry 자료형이 낯설고 어렵다.. 나중에 따로 포스팅 해야겠다.

해당 풀이는 이유는 모르겠지만 SWEA에서 계속 컴파일 에러나서 버렸다. 그리고 찾아보니 저렇게 풀려고한건 나밖에 없는 듯 하다. 에혀

 

정렬 전 특정 순서의 값을 정렬 후에도 해당 키로 찾아야하기에 map 자료형으로 정렬 전 순서값을 기억하고 있어야 한다 생각했다. 근데 다른 소스들 찾다보니! 꼭 정렬 전의 키값을 기억할 필요가 없었다. 정렬 전 키에 해당하는 값을 가지고 있으면 굳이 map에 저장 안하고, 배열로 값만 저장했을 때 그 값을 찾는다는 것!!! 왜 이 쉬운 방법을 여지껏 생각 못했던 것일까.. 난 아직 멀었다.

public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
		
   String[] gradelist={"A+", "A0", "A-", "B+", "B0", "B-", "C+", "C0", "C-", "D0"};
		
   int T = sc.nextInt();
   for(int test_case=0; test_case<T; test_case++) {
      int n = sc.nextInt(); // 학생 수  
      int k = sc.nextInt(); // 알고 싶은 학생의 번호
			
      double kScore = 0; // 알고 싶은 학생의 점수 저
			
      List<Double> scores = new ArrayList<Double>(); 
      for(int i=0; i<n; i++) {
         int mid = sc.nextInt();
         int fin = sc.nextInt();
         int assign = sc.nextInt();
				
         double score = 0.35*mid + 0.45*fin + assign*0.2;
         scores.add(score);
				
         if(i==k-1) kScore = score;
      }
			
      Collections.sort(scores, Collections.reverseOrder());
			
      // n/10명의 학생들에게 동일한 평점 부여 
      int tmp = n/10;
      String grade = gradelist[(int)(scores.indexOf(kScore)/tmp)];
      System.out.printf("#%d %s\n", test_case+1, grade);

   }
   sc.close();
}

그리고 문제 설명 중 "N/10 명의 학생들에게 동일한 평점을 부여할 수 있다" 라는 말이 있다.

예를 들어, 20명의 학생이 있을 때 20/10인 2명의 학생들에게 A+, A0, A-.. 학점을 부여한다는 의미로, 동일한 학점을 가질 수 있는 학생 수를 알려주었다. 따라서 정답 등급을 출력할 때 동점자의 수를 계산하는 로직도 필요하다.

 

 

2001. 파리 퇴치 (D2, 70%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

처음 봤을 때 4중 반복문이 생각났으나, 설마 ? 했지만 완전 탐색으로도 문제 통과는 가능하다.

public static void main(String[] args) {
		
   Scanner sc = new Scanner(System.in);
   int T = sc.nextInt();
	
   for(int test_case = 0; test_case<T; test_case++) {
      int n = sc.nextInt(); // 배열 크기 
      int m = sc.nextInt(); // 파리채 구역 크기 
			
      int[][] arr = new int[n][n];
					
      for(int i=0;i<n;i++) {
         for(int j=0;j<n;j++) arr[i][j] = sc.nextInt();
      }
			
      int ans = 0;
      int tmp = 0;
      for(int i=0;i<n-m+1;i++) {
         for(int j=0;j<n-m+1;j++) {
            tmp=0;
            for(int k=0; k<m; k++) {
               for(int l=0; l<m; l++) {
                  tmp += arr[i+k][j+l];
               }
            }
            ans = Math.max(ans, tmp);
         }
      }
      System.out.printf("#%d %d\n", test_case+1, ans);			
   }
}

 

댓글 보다 찾은 누적합 알고리즘!

누적합이란 말 그대로 배열에서 해당 인덱스까지 모든 값을 더한 값들이다.

입력받은 배열의 빨간색 부분의 합은 누적합 배열에서 동일한 인덱스(I, J)의 값에서 M(빨간 부분 길이) 이전의 값들을 빼주고 그 과정에서 중복으로 빠진 (I-M, J-M) 값을 한번 다시 더해줌으로써 구할 수 있다.

public static void main(String[] args) {
		
   Scanner sc = new Scanner(System.in);
   int T = sc.nextInt();
	
   for(int test_case = 0; test_case<T; test_case++) {
      int n = sc.nextInt(); // 배열 크기 
      int m = sc.nextInt(); // 파리채 구역 크기 
      int[][] sum = new int[n+1][n+1]; // 누적합 배열 
			
      // 누적합 배열 초기화  		
      for(int i=0; i<n+1;i++) {
         sum[i][0] = 0;
         sum[0][i] = 0;
      }
      
      // 누적합 배열 (현재까지의 모든 수의 합)
      for(int i=1; i<=n; i++) {
         for(int j=1; j<=n; j++) {
            int input=sc.nextInt();
            sum[i][j] = input + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
         }
      }

      int ans=0;
      // 누적합 최대 구하기 
      for(int i=m; i<=n; i++) {
         for(int j=m; j<=n; j++) {
            int tmp = sum[i][j]-sum[i][j-m]-sum[i-m][j]+sum[i-m][j-m];
            ans = Math.max(ans, tmp);
         }
      }
			
      System.out.printf("#%d %d\n", test_case+1, ans);
			
   }		
}

1. 누적합 구할 때 이전 인덱스값을 활용하려고 주어진 배열보다 길이가 1 더 큰 누적합 배열을 만들어 인덱스 0인 값들을 0으로 채워줬다.
2. 입력받음과 동시에 누적합을 구한다.
3. 누적합의 최대를 구하는 반복문이 m부터 시작하는 이유는 어차피 파리채 내려치는 배열의 크기는 m이기 때문이다. 

 

 

2005. 파스칼의 삼각형 (D2, 68%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5P0-h6Ak4DFAUq

이건 문제 설명을 제대로 이해 못했던 문제 ("왼쪽과 오른쪽 위"를 "왼쪽 숫자"와 "오른쪽 위의 숫자"로 이해함)

public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
		
   int T = sc.nextInt();
   for(int test_case=0; test_case<T; test_case++) {
      int n = sc.nextInt();
			
      int[][] arr = new int[n][n];
			
      // 초기화 (가장 처음 수와 마지막 수는 1)
      arr[0][0]=1;
      for(int i=1; i<n ; i++) {
         arr[i][0]=1;
         arr[i][i]=1;
      }
			
      if(n>2) {
         for(int i=2; i<n; i++) {
            for(int j=1; j<i; j++) {
               arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
            }
         }
      }
			
      System.out.println("#"+(test_case+1));
			
      for(int i=0; i<n; i++) {
         for(int j=0; j<=i; j++) {
            System.out.print(arr[i][j] + " ");
         }
         System.out.println("");
      }
   }
}

 

 

2007. 패턴 마디의 길이 (D2, 76%)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5P1kNKAl8DFAUq

뭔가 특별한 알고리즘이 있을까 하였지만 그냥 문제 그대로 풀었으면 잘 풀렸을 문제.. 이런 문제는 고민도 안하고 빠르게 푸는 날이 오길

문제 내용 그대로 맨 앞에서부터 마디 길이 j 만큼 문자열을 잘라서 비교한다. 처음엔 한 글자씩 비교해야하나 생각했지만 마디 길이가 정해져있어 더 쉽게 탐색할 수 있다.

public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
		
   int T = sc.nextInt();
   for(int i=0; i<T; i++) {
      String s = sc.next();
			
      for(int j=1; j<10; j++) { // 마디 최대 길이 10
         String repeat = s.substring(0, j); // 반복 체크할 마디 지정 
         String repeatCk = s.substring(j, j+j); // 지정한 마디 뒤로부터 반복 체크할 구간 
				
         if(repeat.equals(repeatCk)) {
            System.out.printf("#%d %d\n",i+1, repeat.length());
            break;
         }
      }
   }
}