[JAVA] 백준 data structures - 브론즈모음(2605, 12605)

 

2605 줄 세우기 - 브론즈2

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

2605번: 줄 세우기

 

• 리스트의 인덱스를 사용하여 풀어도 될 것 같고, 스택으로 원하는 만큼 뽑고 삽입해도될 것 같다
• 두 방법 모두로 풀어보겠다!

 

리스트 풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    List<Integer> list = new ArrayList<>();
    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i=1; i<=cnt; i++) {
      int num = Integer.parseInt(st.nextToken());

      int idx = list.size() - num;
      list.add(idx, i);
    }

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

• 자신이 들어갈 인덱스 값은  list.size() - 값  이다
• 그냥 List 컬렉션에 잘 넣어주고 프린트하면 된다

 

 

스택풀이

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

    for (int i=1; i<=cnt; i++) {
      int num = Integer.parseInt(st.nextToken());

      Stack<Integer> tmpStack = new Stack<>();
      for (int j=0; j<num; j++)
        tmpStack.push(stack.pop());

      stack.push(i);

      for (int j=0; j<num; j++)
        stack.push(tmpStack.pop());
    }

    StringBuffer sb = new StringBuffer();
    for (int i =0; i<stack.size(); i++) {
      sb.append(stack.get(i));
      sb.append(" ");
    }

    System.out.println(sb);
  }
}

• 받은 값만큼 스택에서 빼서 tmpStack에 push한다
• 자신의 순서번호를 스택에 넣는다
• tmpStack에 있던 걸 그대로 다시 pop해서 스택에 넣는다

 

 

리스트가 시간이 쪼끔 덜 걸리고, 스택이 메모리가 쪼끔 덜 든다.

둘이 비슷비슷한듯

 

 

 

12605 단어순서 뒤집기 - 브론즈2

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

12605번: 단어순서 뒤집기

 

• 그냥 반대로 출력해도 될 것 같다
• 스택과 리스트 반대로 훑는 방법 2가지로 풀어보겠다

 

리스트 반대로 출력방법 풀이

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

    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int i=1; i<=tcCnt; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      List<String> list = new ArrayList<>();
      while (st.hasMoreTokens())
        list.add(st.nextToken());

      sb.append("Case #" + i + ": ");
      for (int j=list.size()-1; j>=0; j--) {
        sb.append(list.get(j));
        if (j != 0)
          sb.append(" ");
      }

      sb.append("\n");
    }

    System.out.println(sb);
  }
}

 

스택사용 풀이

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

    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int i=1; i<=tcCnt; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      Stack<String> stack = new Stack<>();
      while (st.hasMoreTokens())
        stack.add(st.nextToken());

      sb.append("Case #" + i + ": ");
      while (!stack.isEmpty()) {
        sb.append(stack.pop());
        if (stack.size() != 0)
          sb.append(" ");
      }

      sb.append("\n");
    }

    System.out.println(sb);
  }
}

• 스택에 단어단위로 넣은 뒤 pop pop빼서 출력

 

• 스택이 좀 더 성능이 좋은듯

 

 

 

 

 

간단한 브론즈 문제를 풀어봤으니 바로 실버로 넘어가겠다!