[JAVA] 백준 data structures - 실버모음(2161, 1158, 2346, 1927)

 

 

2161 카드1 - 실버5

https://www.acmicpc.net/problem/2161

2161번: 카드1

 

• 길이가 7이라면 7+6+5+...+2+1 = (7+1)*7/2 길이의 배열을 만드는 방법도 사용할 수 있고
• 큐를 사용할 수 있다.
• 정수는 1000까지니까 최대 (1000+1)*1000/2 = 500500 길이의 배열이 만들어질 것이니까..
• 큐를 사용하는 게 좋을 것 같다!

 

큐를 이용한 풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    Queue<Integer> queue = new LinkedList<>();
    for (int i =1; i<=n; i++)
      queue.add(i);

    List<Integer> list = new ArrayList<>();

    while (queue.size() != 1) {
      list.add(queue.poll());

      if (queue.size() == 1)
        break;

      int tmp = queue.poll();
      queue.add(tmp);
    }

    StringBuffer sb = new StringBuffer();
    for (int num: list) {
      sb.append(num);
      sb.append(" ");
    }

    sb.append(queue.poll());

    System.out.println(sb);
  }
}

• 정말 문제에서 요구하는 그대로 구현하면 됨

 

 

1158 요세푸스 문제 - 실버4

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

• 원형 큐를 사용하면 어렵지않게 풀릴 것 같다

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    int manCnt = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    Queue<Integer> queue= new LinkedList<>();

    for (int i= 1; i<=manCnt; i++)
      queue.add(i);

    int cnt = 1;
    StringBuffer sb= new StringBuffer();
    sb.append("<");

    while (!queue.isEmpty()) {
      if (cnt == k) {
        sb.append(queue.poll());
        if (!queue.isEmpty())
          sb.append(", ");

        cnt = 1;
      } else {
        queue.add(queue.poll());
        cnt++;
      }
    }
    sb.append(">");

    System.out.println(sb);
  }
}

• 큐에 값을 하나씩 넣은 후 하나씩 빼면서 k번째 값인지 확인한다
  • cnt를 세며 k가 됐을 때 stringBuffer에 값을 넣는다
  • k가 되지 않았을 경우엔 poll()한 값을 다시 큐에 넣어준다
  • 이 과정을 큐가 빌 때까지 반복한다

 

 

 

2346 풍선 터뜨리기 - 실버3

https://www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기

 

• 왼쪽과 오른쪽으로 모두 이동이 가능해야한다 -> 데크를 사용하는 게 좋을듯
• 양수이면 원래 큐처럼 이동시키고, 음수이면 반대로 이동시키면 될 것 같다
• 풍선 번호와 이동 숫자를 저장해야함
  • 풍선번호를 인덱스로 하고, 이동숫자를 값으로 하는 배열 하나를 만들어야할 것 같고
  • 데크에는 풍선번호만 저장하면 될 듯

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] moveArr = new int[cnt+1];
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 1; i<cnt+1; i++) {
      moveArr[i] = Integer.parseInt(st.nextToken());
      deque.add(i);
    }

    StringBuffer sb = new StringBuffer();
    int move = moveArr[deque.poll()];
    sb.append(1); sb.append(" ");

    while (!deque.isEmpty()) {
      int val;
      if (move > 0) {
        //큐처럼 이동
        while (move != 1) {
          deque.addLast(deque.removeFirst());
          move--;
        }

        val = deque.removeFirst();
      } else {
        //큐 반대로 이동
        while (move != -1) {
          deque.addFirst(deque.removeLast());
          move++;
        }

        val = deque.removeLast();
      }

      sb.append(val);
      if (!deque.isEmpty())
        sb.append(" ");

      move = moveArr[val];
    }

    System.out.println(sb);
  }
}

• 순서번호를 인덱스로 이동방향&이동정도을 알 수 있는 moveArr을 저장
• 이동방향&이동정도가 양수이면 원래 원형큐처럼 이동하고
• 음수이면 원형큐 반대 방향으로 이동한다

 

• 배운 점: 나는 while문에서 (1)이동 후 (2)값을 빼서 출력 하는 방식을 사용했다
  • 구글링을 해보니 (1)값을 빼고 출력 후 (2)이동 하는 방식을 많이 사용하셨다
  • 이 방식이 코드길이도 줄어들고 보기 좋았다
  • 또한 나처럼 while문으로  하는 것보다 그냥 횟수를 for문으로 지정해서 삭제&삽입하는 방식이 더 좋은 것 같다
  • sb.append(num).append(" "); 이런 문법이 있는 것도 처음 알았다!
  • deque 크기가 1일때까지만 반복하고, 마지막에 append(" ")를 안해주는 게 매번 queue.isEmpty를 검사하지 않아도 되어 좋은듯
  • 참고한 풀이: https://velog.io/@brince/%EB%B0%B1%EC%A4%80-2346%EB%B2%88-%EC%9E%90%EB%B0%94-%ED%92%80%EC%9D%B4

 

 

1927 최소 힙 - 실버2

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

• 문제 이름에서 알 수 있듯 최소 힙 사용을 연습하기 좋을 것 같다
• 자바에서 힙은 PriorityQueue를 사용한다 -> 사용법만 알면 어렵지 않은 문제인 것 같음

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    StringBuffer sb = new StringBuffer();

    for (int i =0; i<cnt; i++) {
      int cal = Integer.parseInt(br.readLine());

      if (cal == 0) {
        if (minHeap.isEmpty())
          sb.append(0);
        else
          sb.append(minHeap.poll());
        sb.append("\n");
      } else {
        minHeap.add(cal);
      }
    }

    System.out.println(sb);
  }
}

• 그냥 하라는대로 따라가면 된다

 

 

 

 

 

 

 

 

 

 

 

다음 공부: 데크,스택, 큐, 최소힙&최대힙 사용법 제대로 정리 및 공부!