[SWEA] 1005, 2001, 1989, 1986, 1984(D2)

 

1005 파스칼의 삼각형(D2)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5P0-h6Ak4DFAUq&categoryId=AV5P0-h6Ak4DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

나의 위의 2개를 어떻게 찾아낼건지가 관건이다. 

0

0 0

0 0 0

0 0 0 0

 

배열로 저장 후, 이런식으로 i-1  i 로 계산하면 못할건 없는 것 같긴하다. 끝쪽 처리만 1로 잘 해주면 되겠다

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int tc = 1; tc<=tcCnt; tc++) {
      int N = Integer.parseInt(br.readLine());
      int[][] arr = new int[N][N];

      arr[0][0] = 1;

      for (int i =1; i<N; i++) {
        for (int j=0; j<=i; j++) {
          int val = 0;
          if (j-1 >= 0)
            val += arr[i-1][j-1];

          if (arr[i-1][j] != 0)
            val += arr[i-1][j];

          arr[i][j] = val;
        }
      }

      sb.append("#"+ tc + "\n");

      for (int i =0; i<arr.length; i++) {
        for (int j =0; j<i+1; j++)
          sb.append(arr[i][j] + " ");

        sb.append("\n");
      }
    }
    System.out.println(sb);
  }
}

• 어차피 N은 10이 최대이기 때문에 그냥 N x N을 만들어주는 식으로 작성하였다
• 맨 처음은 1이다
• 현재 값 arr[i][j]는 arr[i-1][j-1] + arr[i-1][j] 로 구성된다
  • j-1 인덱스가 0이상인지 확인해야하고
  • j 값이 0인지도 확인해야한다 (0으로 초기화 되니까, 0이 될 일은 없음)
• 배열이 완성되면 값이 있는 값들을 stringbuffer에 넣어준다 

 

 

 

 

2001 파리퇴치(D2)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

최댓값으로 정렬하기엔 서로 따로따로 떨여져 있을 확률이 높기 때문에 좋은 방법이 아니다.

모든 경우를 찾아 최댓값에 더하는 브루트포스 방법을 생각해봤다. 

판의 최대 크기는 15이므로 모두 찾을 경우 최대 15x15 = 225가지 경우를 계산해야한다. 그렇게 성능이 나쁠 것 같아 보이진 않았다.

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int tc = 1; tc<=tcCnt; tc++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int size = Integer.parseInt(st.nextToken());
      int flySwatterSize = Integer.parseInt(st.nextToken());

      int[][] fly = new int[size][size];

      for (int i =0; i<size; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j=0; j<size; j++)
          fly[i][j] = Integer.parseInt(st.nextToken());
      }

      int max = 0;

      //0 <= x <= size-(flySwatterSize) + 1
      for (int i =0; i<= size - flySwatterSize; i++) {
        for (int j =0; j<= size - flySwatterSize; j++) {
          int sum = getSum(i, j, flySwatterSize, fly);

          if (sum > max)
            max = sum;
        }
      }

      sb.append("#" + tc + " " + max + "\n");
    }
    System.out.println(sb);
  }

  private static int getSum(int row, int col, int flySwatterSize, int[][] fly) {
    int sum = 0;

    for (int i =row; i<row+flySwatterSize; i++) {
      for (int j =col; j<col + flySwatterSize; j++) 
        sum += fly[i][j];
    }

    return sum;
  }
}

• 입력
  • 판 사이즈 size와 파리채 사이즈 flySwatterSize를 받는다
  • size에 대해 fly개수를 fly[][] 배열에 넣어준다
• 오른쪽 위를 기준으로 파리채 사이즈만큼 값을 더해주어 max값을 찾을 것이다
  • 오른쪽 위 기준이 될 수 있는 범위는 0 ~ (size-flySwatterSize) 이다
  • 모든 가능한 "오른쪽 위" 에 대해 합을 계산하는 getSum함수를 호출한다
  • 더한 값이 max보다 클 경우 max를 갱신한다
• max를 StringBuffer에 넣어준다

 

 

 

1989 초심자의 회문 검사(D2)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PyTLqAf4DFAUq&categoryId=AV5PyTLqAf4DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

회문인지 판별하는 문제는 백준에서도 많이 풀어봤다. 

인덱스로 하나하나 비교하는 방법도 나쁘진 않지만 큐로 푸는 게 가독성면에서 괜찮았던 기억이 난다. 

이번에는 큐로 풀어보겠다!

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int tc = 1; tc<=tcCnt; tc++) {
      String word = br.readLine();
      int isPalindrome = 1; //회문이면 1
      Queue<Character> queue = new LinkedList<>();

      for (int i =0; i<=word.length()/2 - 1; i++)
        queue.add(word.charAt(i));

      int idx = word.length()-1;
      while (!queue.isEmpty()) {
        char c = queue.poll();
        if (c != word.charAt(idx)) {
          isPalindrome = 0;
          break;
        }
        idx--;
      }

      sb.append("#" + tc + " " + isPalindrome + "\n");
    }
    System.out.print(sb);
  }
}

• 0부터 len/2 - 1 인덱스까지의 값을 큐에 넣는다 (더 많아도 상관은 없지만 시간 조금 줄이기 위해 최솟값으로 설정)
• idx를 배열 맨 끝 값으로 시작하여 큐에서 하나씩 값을 뺀다
  • idx 인덱스 값이 큐에서 뺀 값과 같은지 확인한다
  • 만약 같지 않으면 회문이 아니므로 isPalindrome을 false(0) 로 설정해주고 while문을 끝낸다
  • 같으면 idx를 줄여가면서 회문비교를 계속한다

 

<= 에서 등호 안붙여줘서 틀렸다! ㅜㅜ

간단하게 메모를 하면서 구현을 했는데, 등호를 좀 대충썼다... 이제 메모할 때도 등호를 제대로 표시해줘야겠다.

 

 

 

1986 지그재그 숫자(D2)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PxmBqAe8DFAUq&categoryId=AV5PxmBqAe8DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

그냥 죽죽 늘리면서 홀수면 더하고 짝수 빼면 된다 

설명할 게 딱히 없는 것 같다

 

간단한 풀이

int N = Integer.parseInt(br.readLine());
int result = 0;

for (int i =1; i<=N; i++) {
    if (i % 2 == 0)
      result -= i;
    else
      result += i;
}

 

 

 

 

1984 중간 평균값 구하기(D2)

수가 같은 숫자가 나올 수 있는지, 최대 수와 최소 수에 중복이 있을 때는 둘 다 포함하면 안되는지에 대한 상세한 설명이 없어서 헷갈렸다. 일단 최대 최소 수만 저장해서 빼고 8을 나누는 식으로 풀었는데 틀렸다고 나올까봐 마음 졸였다.

근데 통과했다..! 다행이다

 

코드자체는 굉장히 간단하다. 그냥 최대 최솟값만 잘 저장하면 되는 문제. 설명할 건 딱히 없다

StringTokenizer st = new StringTokenizer(br.readLine());

int sum = 0;
int min = 10001;
int max = -1;

for (int i =0; i<10; i++) {
    int tmp = Integer.parseInt(st.nextToken());

    sum += tmp;

    if (tmp < min)
      min = tmp;

    if (tmp > max)
      max = tmp;
}

sum -= (max + min);

sb.append("#" + tc + " " + Math.round((double)sum/8) + "\n");

 

 

 

 

 

 

D2 레벨의 기준이 뭔지 모르겠다. 백트래킹이 나왔다가 갑자기 홀수짝수 더하기 문제가 나오고...

백준이랑 비교해보면 브론즈랑 실버가 우루루 섞여있는 느낌이다. 

그래도 열심히 해보자!