Algorithm - String CodingTest Tip

• Java로 코딩테스트를 준비하며 부족한 부분을 공부하기 위해 정리하였음.
• 코딩테스트 Array와 관련된 정리내용임.

1. 배열을 입력 받을 때 주의할 점

• Scanner 로 배열을 입력받을 일이 많다.
• int[][] aArr = new int[a][b]; 이렇게 입력 받는데, 믄제를 꼼꼼하게 잘 읽고, a와 b에 꼭 필요한 만큼의 숫자만 넣어야한다.안그러면 시간 초과 에러가 발생할 수 있다.

2. continue & break

• Array 문제에서는 for문을 쓸 일이 많다. 물론 다른 곳에서도 쓸 일은 많을 것이다.
• continue; break; 를 적절히 잘 사용해주어야 시간 복잡도에 걸리지 않을 수 있다.

3. 에라토스테네스의 체

• 이건 배열 문제에서 정말 중요한 알고리즘인 거 같다.

    public class A {
        public static int eratosthenesSieve(int num) {
  
            boolean[] isPrime = new boolean[num+1];
            Arrays.fill(isPrime, true);
            isPrime[0] = isPrime[1] = false;
  
            for ( int i=2; i*i<=num; i++) {
                if(isPrime[i]) {
                    for ( int j=i*i; j<=num; j+=i ) {
                        isPrime[j] = false;
                    }
                }
            }
  
            int answer = 0;
            for ( boolean tf : isPrime ) {
                if(tf) answer++;
            }
  
            return answer;
        }
    }
  

4. List 관련 함수들

• List 관련 함수들을 몇 개 적어두려 한다.
• Collections 를 이용하는건데, Collection이 아니라 Collections 이다.
• List 를 가지고 문제를 풀어야 할 때 좋다. ```bash
  • Collections.sort(iList); : 리스트 정렬
  • Collections.sort(iList , reverseOrder()); : 리스트 역순으로 정렬
  • Collections.max(iList); Collections.min(iList); : 최대, 최소값
  • Collections.shuffle(iList); : 리스트 랜덤 섞기
  • Collections.binarySearch(iList, Key); : 오름차순으로 정렬된 리스트에서 이진검색을 통해 위치를 반환, 실패시 -1반환
  • Collections.disjoint(iList, iList2); : 두 리스트의 값이 완전히 다른지 검사 , 하나라도 같은값이 있으면 False ```

5. 숫자를 뒤집는 방법

• 숫자를 뒤집는 방법은, String.valueOf(i); 로 String으로 만든 다음, 그걸 StringBuilder를 통해 reverse() 해주는 방법이 있다.
• 하지만 StringBuilder를 사용하지 못하는 경우, 즉 손코딩을 해야하는 경우가 있다.
• 이럴경우는 아래와 같은 방법을 사용해주면 된다. ( 이건 외워두면 좋다. )

    public class A {
        public static void main(String[] args) {
  		  
          int i = 1234567;
          int res = 0;
          while ( i != 0 ) {
              res = ( res * 10 ) + ( i % 10 );
              i /= 10;
          }
  		  
       }
    }
  

6. 소수인지 판별하는 메서드

• 소수 구하는 메서드도 외워두면 좋다.

    public class A {
        public boolean method(int num) {
  		  
          if ( num <= 1 ) return false;
  		  
          for ( int i=2; i<num; i++ ) {
             if ( num % i == 0 ) return false;
          }
  		  
          return true;
  		  
       }
    }
  

7. 이차원 배열에서 앞, 뒤로 숫자를 받지 않는 경우

• 아래처럼 count + 2 를 배열의 개수로 받으면 된다.

    public class A {
        public static void main(String[] args) {
  		
            Scanner scan = new Scanner(System.in);
            int count = scan.nextInt();
            int[][] peaksArr = new int[count+2][count+2];
            for (int i=1; i<=count; i++) {
                for (int j=1; j<=count; j++) {
                    peaksArr[i][j] = scan.nextInt();
                }
            }
  			
        }
    }
  

8. 이차원 배열에서 주변 숫자보다 자기가 클 경우의 갯수를 구하는 문제

• 이것도 풀이 방법을 외워두면 좋다.

    public class A {
        // 정석적인 풀이 방법 ( 꼭 4방향만이 아닐 수 있으므로, if문만으로 하는건 바람직하지 못하다. )
        // 8방향이라면,
        // static int[] dx = {-1, 0, 0, 1, -1, -1, 1, 1};
        // static int[] dy = {0, -1, 1, 0, -1, 1, -1, 1};
        // 이렇게 해야한다.
        static int[] dx = {-1, 0, 0, 1};
        static int[] dy = {0, -1, 1, 0};
        public static int peaksCount(int count, int[][] peaksArr) {
            int peaksCount = 0;
            for ( int i = 1; i <= count; i ++ ) {
                for ( int j = 1; j <= count; j ++ ) {
                    boolean check = true;
                    for (int k=0; k<dx.length; k++) {
                        int nx = i + dx[k];
                        int ny = i + dy[k];
                        if ( peaksArr[i][j] <= peaksArr[nx][ny] ) {
                            check = false;
                            break;
                        }
                    }
                    if ( check ) peaksCount ++;
                }
            }
            return peaksCount;
        }
    }
  

9. 이차원 배열에서 가로, 세로, 대각선의 합 중 가장 큰 합을 구하는 문제

• 이것도 풀이 방법을 외워두면 좋다.

    public class A {
        public static int gridMaxSum(int count, int[][] gridArr) {
  		
            int answer = Integer.MIN_VALUE;
  			
            // 가로, 세로
            int sum1, sum2;
            for ( int i=0; i<count; i++ ) {
                sum1 = sum2 = 0;
                for ( int j=0; j<count; j++ ) {
                    sum1 += gridArr[i][j];
                    sum2 += gridArr[j][i];
                }
                answer = Math.max(answer, sum1);
                answer = Math.max(answer, sum2);
            }
  
            // 대각
            sum1 = sum2 = 0;
            for (int i=0; i<count; i++) {
                sum1 += gridArr[i][i];
                sum2 += gridArr[i][count-i-1];
            }
            answer = Math.max(answer, sum1);
            answer = Math.max(answer, sum2);
            return answer;
        }
    }
  

10. 배열 정렬 문제에서 중간에만 정렬상태가 다른 값이 끼어있을 경우

• 똑같은 배열을 clone(); 으로 만들고

• 이후 clone 배열만 정렬을 한 후, 다른 부분을 비교해주면 된다.

11. 이차원 배열 오름, 내림 차순 정렬 방법

• 오름차순 정렬

  • Arrays.sort(arr, (o1,o2) -> (o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]));

  • 이해하고, 외우는 것이 좋다.

• 내림차순 정렬

  • Arrays.sort(arr, (o1,o2) -> (o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0]));

  • 이해하고, 외우는 것이 좋다.