[SWEA] 1206, 1244, 1208, 2806, 2805(D3)

 

(저는 추천순으로 문제 풀고있습니당)

 

1206 [S/W 문제해결 기본] 1일차 - View (D3)

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

SW Expert Academy

 

이것도 브루트포스로 풀어야할 것 같다.

• 일단 빌딩 높이를 배열에 저장한다
• 인덱스 2부터 len-3까지 각 빌딩에 대해 조망권을 계산한다
  • 조망권 계산을 위해 좌우 2블럭씩의 빌딩을 조사함 
  • 왼쪽 조망권 = 빌딩높이 - max(i-2, i-1)
  • 오른쪽 조망권 = 빌딩높이 - max(i+1, i+2)
  • min(왼쪽조망권, 오른쪽조망권)이 빌딩의 조망권을 가지는 세대 수이다.

 

int result = 0;

int buildingCnt = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] building = new int[buildingCnt];

for (int i =0; i<buildingCnt; i++)
    building[i] = Integer.parseInt(st.nextToken());

    for (int i=2; i<buildingCnt-2; i++) {
    int height = building[i];
    int left = Math.max(building[i-1], building[i-2]);
    if (height <= left)
      continue;
    int right = Math.max(building[i+1], building[i+2]);
    if (height <= right)
      continue;

    result += Math.min(height - left, height - right);
}

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

 

 

 

1244 [S/W 문제해결 응용] 2일차 - 최대 상금(D3)

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

SW Expert Academy

 

• 풀이법이 한 번에 생각나지 않아서 메모를 하면서 풀었다. 

 

(삽질1)

• 가장 앞 자리부터 교환할 최댓값을 찾는다
  • 3의 경우 2888을 뒤져보며 가장 큰 수를 찾는다 (만약 수가 같으면 뒤에꺼 선택)
  • 큰 수는 바로 맨 앞자리에 넣고 3은 tmp배열에 임시로 저장한다
• 이 과정을 교환횟수가 다 되거나, len-2 인덱스로 갈 때까지 반복한다.
• 만약 다 정렬이 됐는데 교환횟수가 남으면 짝수면 그대로 두고, 홀수면 맨 뒤에 두 자리를 교환해준다.

 

이렇게 구현했더니 테스트케이스 몇 개가 통과가 안됐다. ㅠㅠㅠ

사실 이 문제는 브루트포스 였음ㅋ.. 최대 자릿수도 6이고 최대교환횟수도 10이니까 브루트포스 가능

 

public class Solution {
  static int result;
  static int[] numList;
  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());
      String numString = st.nextToken();
      int exchangeCnt = Integer.parseInt(st.nextToken());

      numList = new int[numString.length()];
      for (int i =0; i<numList.length; i++)
        numList[i] = Integer.parseInt(String.valueOf(numString.charAt(i)));

      //풀이시작
      result = 0;
      if (numList.length < exchangeCnt) {
        exchangeCnt = numList.length;
//        if (numList.length-exchangeCnt % 2 == 0)
//          exchangeCnt = numList.length ;
//        else
//          exchangeCnt = numList.length + 1;
      }
      dfs(exchangeCnt);

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

  private static void dfs(int exchangeCnt) {
    if (exchangeCnt == 0) {
      int cal = 0;
      for (int i =0; i<numList.length; i++) {
        cal += numList[i];
        if (i != numList.length-1)
          cal *= 10;
      }

      if (result < cal)
        result = cal;

      return;
    }

    for (int i =0; i<numList.length-1; i++) {
      for (int j=i+1; j<numList.length; j++) {
        int tmp = numList[i];
        numList[i] = numList[j];
        numList[j] = tmp;
        dfs(exchangeCnt-1);
        tmp = numList[i]; //돌려놓기
        numList[i] = numList[j];
        numList[j] = tmp;
      }
    }
  }
}

• 이 블로그의 풀이를 참고함
  • https://velog.io/@sua_ahn/SWEA-1244-%EC%B5%9C%EB%8C%80-%EC%83%81%EA%B8%88-Java
• 교환횟수가 자릿수 이상이면 무조건 최댓값을 만들 수 있으므로, 가지치기 조건으로 자릿수 설정을 해준다
  • 내 생각엔 주석부분을 넣어야 정답인데, 주석을 빼야 pass가 된다. (이건 나중에 테스트케이스가 추가되면 수정될듯, ex. 1 \n 54321 6)
  • 주석부분: 교환횟수 - 자릿수를 했을 때 짝수만큼 남으면 자릿수만큼 스왑한 게 정답, 홀수만큼 남으면 무조건 뭔가를 스왑해야함
• dfs를 사용하여 가능한 횟수만큼 스왑을 해준다
  • 스왑할 땐 list배열을 수정했다가 다시 원위치로 돌려줌
  • 만약 횟수가 다 됐을 땐 계산해서 최댓값을 구해준다

 

1208 S/W 문제해결 기본] 1일차 - Flatten(D3)

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

SW Expert Academy

 

• 인덱스를 계산해야할 것 같아서 메모를 하면서 풀었다

• 일단 내림차순으로 정렬했다 (오름차순도 상관없을듯)
• max와 min 인덱스가 각각 최댓값과 최솟값을 가리킨다
  • 만약 같은 값이 있다면 max의 경우 가장 오른쪽 거를 가리킨다
  • 이렇게 해야 가장 왼쪽이 최댓값, 오른쪽이 최솟값을 유지할 수 있음
• max에서는 1을 빼고 min에는 1을 더한 후 
• max--, min++을 해준다
• 그리고 같은 값이 오른쪽에 있다면 max를 오른쪽으로 쭉 땡겨주고
  • min도 마찬가지로 왼쪽으로 쭉 땡겨줌
• 이 작업을 차이가 1이 될 때까지 반복한다!

 

코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringBuffer sb = new StringBuffer();
for (int tc =1; tc<=10; tc++) {
  int dumpCnt = Integer.parseInt(br.readLine());
  StringTokenizer st = new StringTokenizer(br.readLine());
  Integer[] height = new Integer[100];
  for (int i =0; i<100; i++)
    height[i] = Integer.parseInt(st.nextToken());

  Arrays.sort(height, Collections.reverseOrder());

  int max=0;  //오른쪽으로 쭉 당기기
  while (max<height.length-1 && height[max]==height[max+1])
    max++;

  int min=height.length-1;  //왼쪽으로 쭉 당기기
  while (min>0 && height[min]==height[min-1])
    min--;

  while (height[0] - height[height.length-1] > 1) {
    height[max]--; height[min]++;
    dumpCnt--;

    if (dumpCnt == 0)
      break;

    if (height[0] - height[height.length-1] <= 1)
      break;

    if (max > 0)
      max--;

    if (min < height.length-1)
      min++;

    while (max < height.length-1 && height[max] == height[max+1])
      max++;   //오른쪽으로 쭉 당기기

    while (min>0 && height[min]==height[min-1])
      min--;  //왼쪽으로 쭉 당기기
  }

  sb.append("#" + tc + " " + (height[0] - height[height.length-1]) + "\n");
}
System.out.print(sb);

• 당기기를 열심히 해주면 된다 ㅎㅎ

 

 

 

2806. N-Queen

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

SW Expert Academy

 

오 최근에 백준에서 푼 N-Queen 문제다!

브루트포스로 풀어야한다는 걸 아는데, 일차원배열로 기깔나게 풀 수 있다는 말을 들어본 것 같다.

브루트 포스와 일차원 배열 둘 다 써보려고 한다.

 

• 한 행, 한 열에 하나의 퀸만 놓아야함
• 행마다 배치하고, 놓을 수 없는 행이 생기면 가지치기
• 위에서 아래로만 놓으니 퀸 존재 여부는 위쪽만 보면 됨

 

2차원 배열 풀이

public class Solution {
  static int result = 0;
  static boolean[][] isQueen;
  static boolean[] visitCol;
  public static void main(String args[]) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int tcCnt = Integer.parseInt(br.readLine());
    for (int tc =1; tc<=tcCnt; tc++) {
      int N = Integer.parseInt(br.readLine());
      isQueen = new boolean[N][N];
      visitCol = new boolean[N];
      result = 0;

      dfs(0);

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

  private static void dfs(int row) {

    for (int i=0; i< visitCol.length; i++) {
      if (!visitCol[i] && canLayQueen(row, i)) {
        if (row == isQueen.length-1) {
          result++;
          continue;
        }

        isQueen[row][i] = true;
        visitCol[i] = true;
        dfs(row+1);
        isQueen[row][i] = false;
        visitCol[i] = false;
      }
    }
  }

  private static boolean canLayQueen(int row, int col) {
    int i = 1;
    while (row-i >=0 && col-i >= 0) {
      if (isQueen[row-i][col-i])
        return false;
      i++;
    }

    i = 1;
    while (row-i >=0 && col+i < isQueen[0].length) {
      if (isQueen[row-i][col+i])
        return false;
      i++;
    }

    return true;
  }
}

• Queen의 위치는 isQueen 이차원 배열에 저장한다
• visitCol로 이미 방문한 컬럼을 저장한다
• dfs로 한 행씩 퀸의 위치를 구한다
• 방문 가능한 컬럼에 대해 퀸을 놓을 수 있는지 판별한다
  • 왼쪽 위 대각선, 오른쪽 위 대각선에 퀸이 존재하는지 확인하여 판별
• 만약 놓을 수 있다면 퀸을 놓고, visitCol을 true로 해주고 다음 행에 대해 dfs를 수행한다
  • 이 때 마지막 행에 퀸을 놓은 상태라면 result++해주고 continue해준다
• 행마다 하나씩 놓고, 한 행에 아무것도 못놓으면 다음 행으로 갈 수 없기 때문에 알아서 가지치기가 된다

 

 

1차원 배열 풀이

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

public class Solution {
  static int result = 0;
  static int[] queenLoc;
  static boolean[] visit;
  public static void main(String args[]) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int tcCnt = Integer.parseInt(br.readLine());
    for (int tc =1; tc<=tcCnt; tc++) {
      int N = Integer.parseInt(br.readLine());
      queenLoc = new int[N];
      visit = new boolean[N];
      for (int i =0; i<queenLoc.length; i++)
        queenLoc[i] = -1;

      result = 0;

      dfs(0);

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

  private static void dfs(int row) {
    //놓을 컬럼 찾기
    for (int i =0; i<visit.length; i++) {
      if (!visit[i]) {
        if (canLayQueen(row, i)) {
          if (row == queenLoc.length-1) {
            result++;
            continue;
          }
          queenLoc[row] = i;
          visit[i] = true;
          dfs(row+1);
          queenLoc[row] = -1;
          visit[i] = false;
        }
      }
    }
  }

  private static boolean canLayQueen(int row, int col) {
    int i = 1;
    while (row-i >=0 && col-i >= 0) {
      if (queenLoc[row-i] == col-i)
        return false;
      i++;
    }

    i = 1;
    while (row-i >=0 && col+i < queenLoc.length) {
      if (queenLoc[row-i] == col+i)
        return false;
      i++;
    }

    return true;
  }
}

• 위의 2차원 배열과 거의 유사하고 row마다 column값을 저장하는 일차원 배열을 사용한다는 것만 다르다
• 비교 방식도 비슷하다 
• visit에 이미 사용된 컬럼들이 저장되어있음
• 방문할 수 있는 컬럼들에 대해 퀸을 놓을 수 있는지 확인한다
  • 확인 방법은 왼쪽 위, 오른쪽 위에 퀸이 있는지 확인함
  • 위 코드에서는 isQueen[row-1][col-1] = true로 확인했다면 여기서는 isQueen[row-1] = col-1 로 확인
• 솔직히 좀 헷갈려서 시간이 많이 들었다. 실제 시험장에서 일차원 배열로 풀 수 있을지 잘 모르겠음(연습 좀 더 해야할듯)

 

2805 농작물 수확하기(D3)

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

SW Expert Academy

• 규칙이 딱 보인다. 인덱스만 잘 설정해주면 될 듯. 별 그리기 문제랑 유사한 것 같다
• 1행은 idx/2 부터 하나
• 2행은 idx/2 -1 부터 3개
• ...
• N/2+1 행은 0부터 N개
• N/2+2 행은 1부터 N-2개

 

public class Solution {
  public static void main(String args[]) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int tcCnt = Integer.parseInt(br.readLine());
    for (int tc =1; tc<=tcCnt; tc++) {
      int N = Integer.parseInt(br.readLine());
      int result = 0;

      int cnt = 1;
      int idx = N/2;
      for (int i =0; i<=N/2; i++) {
        String s = br.readLine();
        for (int j = idx; j<idx+cnt; j++)
          result += Integer.parseInt(String.valueOf(s.charAt(j)));

        cnt += 2;
        idx--;
      }

      cnt = N-2;
      idx = 1;
      for (int i =N/2+1; i<N; i++) {
        String s = br.readLine();
        for (int j = idx; j<idx+cnt; j++)
          result += Integer.parseInt(String.valueOf(s.charAt(j)));

        cnt -= 2;
        idx++;
      }
      
      sb.append("#" + tc + " " + result + "\n");
    }
    System.out.print(sb);
  }
}

• 1 3 5 7 ... 순으로 늘어나는 길이를 cnt에 저장
• 1 3 5 7 얘네를 세기 시작할 인덱스를 idx에 저장
• 중간을 포함한 반까지는 늘어나면서 result++
• 중간 이후 반은 줄여가면서 result--

 

 

 

 

 

 

 

 

 

더 공부할 것: sort 에 comparator 까먹음... 다시 복습하기