[JAVA] 백준 data structures - 실버모음2(2841, 4889, 13335, 15903)

 

 

 

2841 외계인의 기타 연주 - 실버1

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

2841번: 외계인의 기타 연주

 

• 스택문제이다
• 기타줄에 따른 프렛을 스택으로 저장하면 될 것 같다
• 나보다 큰 프렛이 스택의 peek에 저장되어있다면 계속 뺀 후 나를 추가시키면 될듯

 

풀이

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 melodyCnt = Integer.parseInt(st.nextToken());
    st.nextToken(); // 필요없음

    Stack<Integer>[] FretStack = new Stack[7];
    for (int i =1; i<FretStack.length; i++)
      FretStack[i] = new Stack();

    int result = 0;

    for (int i=0; i<melodyCnt; i++) {
      st= new StringTokenizer(br.readLine());

      int line =Integer.parseInt(st.nextToken());
      int fret =Integer.parseInt(st.nextToken());

      if (FretStack[line].isEmpty()){ //스택이 비었다면 그냥 삽입
        FretStack[line].push(fret);
        result ++;
      } else {
        //스택이 비거나, 스택의 peek이 나보다 작을 때까지 스택에서 뺌
        while (!FretStack[line].isEmpty() && FretStack[line].peek() > fret) {
          FretStack[line].pop();
          result++;
        }

        //만약 스택의 peek이 나랑 같은 fret이라면 굳이 삽입 안해도 됨
        if (FretStack[line].isEmpty() || FretStack[line].peek() != fret) {
          FretStack[line].push(fret);
          result ++;
        }
      }
    }

    System.out.println(result);
  }
}

1. 기타줄이 6개니, 6+1 크기를 가지는 Stack배열 fretStack을 만들고 초기화함 (인덱스 0은 사용 안함)
2. 멜로디의 기타줄 번호와 fret번호를 받는다
3. 기타줄 번호 인덱스의 스택을 확인
   • 스택이 비었으면 해당 스택에 삽입 후 result를 1 증가
   • 스택이 비어있지 않다면 스택 peek()을 확인
     • 스택이 비거나 
     • peek()이 내 fret번호보다 작거나 같을 때까지 스택에서 pop()해주면서 result를 증가시킨다
   • 만약 스택의 peek()이 내 fret과 같으면 움직일 필요가 없다
   • 만약 스택이 비어있거나, peek()이 내 fret과 다르다면 스택에 내 fret번호를 삽입하고 result를 증가
4. 마지막 result를 출력한다

 

 

 

4889 안정적인 문자열 - 실버1

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

4889번: 안정적인 문자열

 

• 괄호 => 딱 봐도 스택문제다!
• 맞물리는 괄호를 다 삭제해준 후, 남는 애들을 반대로 돌려주면 될 것 같다
  •  { { { {  이렇게 되어있을 경우 마지막  { 를  }  로 변경 후 그 앞의  {  를 pop
  •  } } } }  이렇게 되어있을 경우 마지막  }  는 두고 그 앞의  }  를  {  로 바꿔주는 식으로 구현
  •  }  {   이렇게 되어있을 경우 둘 다 바꿔야함

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int cnt = 1;
    while (true) {
      String brackets = br.readLine();
      if (brackets.charAt(0) == '-')
        break;

      Stack<Character> stack = new Stack<>();

      for (int i =0; i<brackets.length(); i++) {
        char c = brackets.charAt(i);

        if (stack.isEmpty()) {
          stack.push(c);
          continue;
        }

        if (stack.peek() == '{' && c == '}')
          stack.pop();
        else
          stack.push(c);
      }

      int result = 0;
      while (!stack.isEmpty()) {
        char c1 = stack.pop();
        char c2 = stack.pop();
         if (c1 == '{' && c2 == '}')
           result += 2;
         else
           result ++;
      }

      sb.append(cnt).append(". ").append(result).append("\n");
      cnt++;
    }

    System.out.println(sb);
  }
}

• 입력으로 -로 시작하는 문자열이 들어올 때까지 while문 진행
• 스택에 일단 넣음
  • 지금 넣어야하는 값이 } 이고, 스택 peek()가 { 일 경우 pop()
  • 아닐 경우 무조건 넣음
• for문이 끝나고 stack이 비어있지 않을 경우 stack에서 2개를 뺌
  •  }  {   이렇게 되어있을 경우 둘 다 바꿔야하므로 result를 2 증가시킴
  •  { {  나  } }  이렇게 되어있을 경우 둘 중 하나만 바꾸면 되므로 result를 1 증가시킴
• result를 출력

 

 

 

13335 트럭 - 실버1

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

13335번: 트럭

 

• 다리의 길이만큼의 크기를 가지는 큐에 트럭을 하나씩 넣고 빼면서 무게를 계산하고, 시간을 재면 될 것 같다
• 만약 트럭이 올라갈 수 없다면 0무게의 쓰레기값을 넣어주면 될 듯
• 모든 트럭이 올라타면 while문을 종료하고 마지막 트럭이 건너는 시간을 더하면 될 것 같다

 

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 truckCnt = Integer.parseInt(st.nextToken());
    int bridgeSize = Integer.parseInt(st.nextToken());
    int maxWeight = Integer.parseInt(st.nextToken());

    Queue<Integer> queue = new LinkedList<>();
    for (int i =0; i<bridgeSize; i++)
      queue.add(0);

    int totalWeight = 0;
    int time = 0;

    st = new StringTokenizer(br.readLine());
    for (int i =0; i<truckCnt; i++) {
      int weight = Integer.parseInt(st.nextToken());
      totalWeight -= queue.poll();

      while (totalWeight + weight > maxWeight) {
        queue.add(0);
        totalWeight -= queue.poll();
        time++;
      }

      queue.add(weight);
      totalWeight += weight;
      time++;
    }

    System.out.println(time + queue.size());
  }
}

1. 다리에 올라간 트럭 총 무게를 계산하기 위한 totalWeight를 만듦
2. 다리길이만큼 큐에 0값을 넣음
3. 큐에서 값을 하나 빼면서 totalWeight 무게도 뺌
4. totalWeight에 현재 트럭 무게를 더한 값이 다리 최대하중을 넘지 않는다면 큐에 삽입 (+totalWeight에도 추가)
   • 최대하중을 넘는다면 넘지않을 때까지 큐에서 값을 빼고 0을 삽입하는 과정을 반복함
5. 트럭을 모두 큐에 삽입 후 for문이 끝남
6. 마지막 트럭이 건너는 시간인 (다리길이)를 결과에 더하여 출력

 

 

 

15903 카드 합체 놀이 - 실버1

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

15903번: 카드 합체 놀이

 

• PriorityQueue에 값을 다 넣고 작은 수 2개를 빼서 더한 값을 2번 넣는 걸 반복해주면 될듯

 

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 cardCnt = Integer.parseInt(st.nextToken());
    int mergeCnt = Integer.parseInt(st.nextToken());

    PriorityQueue<Long> minHeap = new PriorityQueue<>();

    st = new StringTokenizer(br.readLine());
    for (int i =0; i<cardCnt; i++)
      minHeap.add(Long.parseLong(st.nextToken()));

    for (int i =0; i<mergeCnt; i++) {
      long sum = minHeap.poll() + minHeap.poll();
      minHeap.add(sum);
      minHeap.add(sum);
    }

    long sum =0;
    while (!minHeap.isEmpty())
      sum += minHeap.poll();

    System.out.println(sum);
  }
}

1. 우선순위 큐에 카드숫자를 다 넣음
2. 최솟값을 2개씩 빼서 합을 구하고, 합을 큐에 2번 넣음
3. 합체 횟수가 넘을 때까지 계속 반복
4. 마지막에는 heap에 있는 숫자를 모두 더하기

 

교훈: 자료형 잘 보기 자료형 잘 보기 자료형 잘 보기... long 써야하는지 잘 보기....... 

 

 

 

 

 

 

 

자료구조 문제는 실버도 어렵지 않은 것 같다. 다음은 골드 문제를 풀어봐야겠다!