1966번(큐), 1010번(조합), 1789번

1966번

 

큐는 먼저 들어간 자료가 가장 먼저 나오는 구조

 

Enque: 큐 맨 뒤에 데이터가 추가되는 것

Deque: 큐 맨 앞쪽의 데이터를 삭제하는 것

 

큐는 연결 리스트를 활용하여 생성

 

<메서드>

 

poll() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거, 큐 비어있으면 false 반환

remove() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거, 큐가 비어 있으면 예외 발생

peek() - 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환, 없으면 null 반환

offer() - 해당 큐의 맨 뒤에 전달된 요소를 삽입, 만약 삽입에 실패하면 false 반환

add() - 해당 큐의 맨 뒤에 전달된 요소를 삽입, 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 예외 발생

 

 

까다로운 문제였다

 

나름대로 코드를 맞게 짰다고 생각했지만 어딘가에서 미스가 났는지 계속 틀렸다고 나와 곤란했다

틀린 이유는 queue 내의 데이터들을 넣고 빼는 과정에서 중요도가 담긴 list는 신경쓰지 않았기 때문이다

중요도와 queue 내의 숫자 데이터는 함께 짝 지어서 생각해줘야 한다. 따라서 queue 내의 숫자 데이터가 움직일 때 queue 의 숫자 데이터가 가진 중요도도 함께 움직여야 한다

 

자세한 설명은 코드 주석에 달아놨다

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

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for(int i = 0; i<num; i++) {
            Queue<Integer> queue = new LinkedList<>();
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine()," ");
            List <Integer> list = new ArrayList<>();
            int count = 0;
            for(int j = 0; j<n; j++){
                list.add(Integer.parseInt(st.nextToken()));
                queue.offer(j);
            }
            while(!queue.isEmpty() && !list.isEmpty()) {
                int index = list.indexOf(Collections.max(list)); // 가장 큰 값의 인덱스를 구함 (list 의 최댓값은 while 문 루프 돌때마다 삭제되므로 인덱스는 계속 초기화됨
                list.remove(index); // 가장 큰 값을 list 에서 삭제 > while 문의 한 루프가 끝나고 그 다음 list 의 최댓값을 사용하기 위해 없애주는 것
                for(int j = 0; j<index; j++) { // 가장 큰 값의 인덱스 전까지의 숫자들을 queue 에서 빼낸 후 다시 뒤로 넣음
                    int tmp = queue.poll();
                    queue.offer(tmp);
                    list.add(list.get(0)); // queue 의 앞부분을 빼내서 뒤로 넣어줬으므로 list 도 동일하게 맨 앞의 값을 list 의 뒤로 추가하고 앞의 값은 빼준다
                    list.remove(0);
                }
                // while 문이 돌 때마다 count 가 한 개씩 늘어남 > 어처피 queue 의 값이 m과 동일해진 시점에도 while 문 종료 전이라 count 하나 더 늘어남
                // 따라서 굳이 queue 의 맨 윗값을 poll 해줄 필요까진 없음
                count++;
                if (queue.peek() == m) { // queue 의 맨 위의 값이 m과 동일해지면 while 문 탈출
                    break;
                }
                queue.poll(); // 맨 위에 있는 queue 값 (중요도 점수가 가장 높은 queue 값)부터 하나씩 빼줌
            }
            System.out.println(count);
        }
    }
}

 

1010번 (조합 - 경우의 수 구하기)

 

조합을 구하는 공식 = mCn = mPn / n! > for문을 통해 구할 수 있다

 

숫자 범위에 주의하자!

처음엔 int 사용했다가 틀렸다

 

BigInteger 클래스는 문자열 형태로 이루어져 있어 숫자의 범위가 무한하다

문자열이므로 연산자를 통한 계산이 불가능하며 BigIntger 내부의 숫자를 계산하기 위해서는 별도의 연산 메서드를 사용

intValue(), longValue() 등을 통해 기본 타입으로 형 변환도 가능하다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for(int i = 0; i<num; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine()," ");
            BigInteger r = new BigInteger(st.nextToken());
            BigInteger n = new BigInteger(st.nextToken());
            BigInteger presult = new BigInteger("1");
            BigInteger rresult = new BigInteger("1");
            for(int j = n.intValue(); j>= n.intValue()-r.intValue()+1; j--) {
                presult = presult.multiply(BigInteger.valueOf(j));
            }
            for(int j = r.intValue(); j>=1; j--) {
                rresult = rresult.multiply(BigInteger.valueOf(j));
            }
            System.out.println(presult.divide(rresult));
        }
    }
}

 

2839번

 

if - else if - else를 이용하는 문제

일일히 확인해 보면서 규칙을 찾아봤다

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

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int bag = 0;
        if (num == 4 || num == 7) {
            bag = -1;
        } else if (num % 5 == 0) {
            bag = num / 5;
        } else if (num%3 + num%5 == 0) {
            bag = num / 5 + 1;
        } else if (num % 5 == 1 || num % 5 == 3) {
            bag = num / 5 + 1;
        } else if (num % 5 == 2 || num % 5 == 4) {
            bag = num / 5 + 2;
        } else if (num % 3 == 0) {
            bag = num / 3;
        }  else {
            bag = -1;
        }
        System.out.println(bag);
    }
}

그냥 노가다하는 문제였다...... 난 내가 이상하게 푼 줄 알았는데 그건 아닌가 봄