포스트

AC(5430)

게시
By Kim Jung Wook 7 분읽는 시간

AC(5430)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int t = Integer.parseInt(br.readLine());
    
    while(t-- > 0) {
      String tmp = br.readLine();
      String[] str = tmp.split("");

      int n = Integer.parseInt(br.readLine());

      String num = br.readLine();
      num = num.substring(1, num.length()-1);
      List<String> list = new ArrayList<String>(Arrays.asList(num.split(",")));
      
      int cnt = 0;
      boolean flag = true;
      for(int i = 0; i < str.length; i++) {
        if(str[i].equals("R")) {
          cnt++;
          continue;
        }
        
        if(n != 0) {
          if(cnt % 2 == 0) {
            list.remove(0);
          } else {
            list.remove(list.size()-1);
          }
          n--;
        } else {
          sb.append("error");
          flag = false;
          break;
        }
        
      }
      
      if(flag) {
        if(cnt % 2 == 1) {
          Collections.reverse(list);
        }
        sb.append("[");
        for(int i = 0; i < list.size(); i++) {
          if(i != list.size()-1) sb.append(list.get(i)).append(",");
          else sb.append(list.get(i));
        }
        sb.append("]");
      }
      
      sb.append("\n");
    }

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

1차 풀이과정

  1. 처음에는 String[] 과 switch를 사용하여 하나씩 접근하여 명령을 수행하였다
  2. 시간초과 발생
  3. 그 다음에는 R을 만나면 reverse를 하지 않고, 카운트를 하여 reverse를 하는 횟수를 줄이려 하였다.
  4. 이유는 R을 만나다가 D를 만나는 시점에 R이 짝수번 나왔으면 결국은 원래 형태이고, 홀수이면 뒤집힌 형태였기 때문이다.
  5. 시간초과 발생
  6. 그 다음은 String[]을 하나씩 접근하지 않고, int idx = String.indexOf(“D”)를 사용하여 R의 갯수를 구하였다.
  7. 마찬가지로 idx의 값이 짝수이면 제자리, 홀수이면 뒤집힌 형태이기 때문이다.
  8. 시간초과 발생
  9. Collections.reverse()도 결국은 반복문의 사용이 있기 때문에 사용하지 않기로 생각하였다.
  10. 어차피 뒤집히고 앞에 수를 빼는 것이기 때문에 reverse를 수행하지 않고 list의 마지막 수를 제거하면 되었기 때문이다.
  11. R을 계속 카운트하여 최종 결과에서 홀수이면 뒤집어주고 짝수이면 그대로 출력하기로 하였다.
  12. 성공을 하였다. 하지만 메모리 : 114424 KB, 시간 : 2528 ms 로 남들과 비교하였을 때 응답시간이 2배 넘게 차이가 났다.
  13. Collections.reverse(list)를 제거하고 for문을 역순으로 돌며 출력을 해보았다. 큰 변화는 없었다.

2차 풀이과정

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
  
    int t = Integer.parseInt(br.readLine());
    
    while(t-- > 0) {
      String tmp = br.readLine();
      String[] str = tmp.split("");

      int n = Integer.parseInt(br.readLine());

      tmp = br.readLine();
      String[] num = tmp.substring(1, tmp.length()-1).split(",");
      
      Deque<String> dq = new ArrayDeque<>();
      
      for(int i = 0; i < n; i++){
        dq.offerLast(num[i]);
      }
      
      boolean rev = false;
      boolean flag = true;
      for(int i = 0; i < str.length; i++) {
        if(str[i].equals("R")) {
          rev = !rev;
          continue;
        }
        
        if(n != 0) {
          if(rev) {
            dq.pollLast();
          } else {
            dq.pollFirst();
          }
          n--;
        } else {
          sb.append("error");
          flag = false;
          break;
        }
        
      }
      
      if(flag) {
          
        sb.append("[");
        
        if(rev) {
          while(!dq.isEmpty()){
            if(dq.size() != 1) sb.append(dq.pollLast()).append(",");
            else sb.append(dq.pollLast());
          }
        } else{
          while(!dq.isEmpty()){
            if(dq.size() != 1) sb.append(dq.pollFirst()).append(",");
            else sb.append(dq.pollFirst());
          } 
        }
        
        sb.append("]");
      }
      
      sb.append("\n");
    }

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}
  1. 리스트에서 앞과 뒤를 제거하기 위해 getIndex를 하고 있는데 결국은 요소 삭제는 앞과 뒤만 된다는 것을 생각하였다.
  2. 그래서 Deque를 이용하여 앞과 뒤의 요소를 삭제하는 것이 좋겠다 생각하였다.
  3. 왜냐하면 리스트의 마지막 요소를 삭제하기 위해 계속하여 리스트의 크기를 구하고 -1을 해왔기 때문이다.
  4. 그리고 숫자를 카운트하여 %로 나눠 나머지를 계산하였는데 결국 이것도 1과 0 즉, true false로 할 수 있다고 생각하였다.
  5. 그래서 reverse를 나타내는 boolean rev를 생성하여 R을 만나면 값을 변화시켰다.
1
2
3

- 성공
- 메모리 : 118496 KB
- 시간 : 952 ms

보안점

  1. Arrays.asList()라는 메소드를 알게되었는데, 여기서 중요한 점이 있었다.
  2. new ArrayList()로 새로운 객체를 만들며 값으로 Arrays.asList()를 넣고 생성된 list는 값을 추가/삭제할 수 있지만
  3. 하지만 이미 만들어진 list에 Arrays.asList를 통해 값을 넣는 것은 값을 추가 삭제는 안되고 set을 통해 값을 수정할 수 있다는 것이다.
  4. new ArrayList<>() : 원소 추가/삭제 (O), set 사용 (O)
  5. Array.asList() : 원소 추가/삭제 (X), set 사용 (O)
  6. List.of() : 원소 추가/삭제 (X), set 사용 (X)
  7. 그리고 모듈러스를 통해 짝수, 홀수, 0과 1을 파악할 때 boolean을 써보는 생각을 해봐야겠다
알고리즘, 문제
알고리즘문제