1주차: 그리디 - 사전 문제 풀이

백준, 프로그래머스 등에서 제공되는 문제의 경우 문제 링크를 첨부하고,
도서에 수록된 문제의 경우 문제 본문을 간략화하여 옮겨적는다.

---

공통문제 1) 1이 될 때까지

(도서 <이것이 코딩테스트다> p.99에 수록)

두 수 N과 K가 주어진다.

2 ≤ N ≤ 100,000

2 ≤ K ≤ 100,000

N이 1이 될 때까지 다음의 두 동작 중 한 가지를 최소 몇 번 수행해야 하는지 구하시오.

• N에서 1을 뺀다.
• N을 K로 나눈다.

 

풀이

N의 값을 업데이트해가며, N의 값이 1이 될 때까지 다음을 반복 수행한다.

• 현재 N의 값이 K의 배수일 경우, N을 K로 나눈다.
• 현재 N의 값이 K의 배수가 아니며 K보다 작을 경우, N이 1이 될 때까지 N에서 1을 뺀다.
• 현재 N의 값이 K의 배수가 아니며 K보다 클 경우, N이 K의 배수가 될 때까지 N에서 1을 뺀다.

 

작성한 정답코드 (입출력 방식)

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

// 현재 N의 값이 K로 나누어떨어질 경우 K로 나누고, 그렇지 않을 경우에는 N의 값이 1이 되거나 K의 배수가 될 때까지 1을 뺀다

public class Solution1{

    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        int answer = 0;
        /*
         * N과 K를 읽어와 변수에 저장
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        /*
         * 알고리즘 수행
         */
        while(n>1) {
            int remainder = n%k;
            // N이 K로 나누어떨어질 경우
            if(remainder == 0) {
                n = n/k;    // N을 K로 나눔
                answer++;    // 한 번 나누었으므로 answer 값 1 증가
                continue;    // 다음 루프로 넘어감
            }

            // N이 K로 나누어떨어지지 않고, N의 값이 K보다 작을 경우
            if(n<k) {
                answer += n-1;    // 뺄셈으로 N을 1로 만든 뒤 풀이를 종료
                break;
            }

            // N이 K로 나누어떨어지지 않고, N의 값이 K보다 클 경우
            // N이 K의 배수가 될 만큼만 뺄셈을 진행한다
            answer += remainder;
            n -= remainder;
        }

        /*
         * 정답 출력
         */
        System.out.print(answer);
    }

}

---

공통문제 2) 무지의 먹방 라이브

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

풀이(정확성 테스트 만점, 효율성 테스트 빵점)

일단, 정확성 테스트 만점부터 맞아보고, 그 후에 효율을 고민해보고 싶어서 다음의 방법으로 코드를 작성해보았다.

 

Queue를 이용한다.

 

Dish라는 자료형을 만든다. 접시 한 개를 나타내는 자료형이다.

이 자료형의 필드는 int num(접시번호)와 int time(다 먹는 데 걸리는 시간)이다.

함수는 생성자, getter 함수 두 개, eat 함수이다.

eat 함수는 time을 1 감소시킨다. 해당 접시의 음식을 한 번 먹었을 때 수행된다.

 

Queue에, 모든 접시의 정보를 Dish 객체로 만들어 순서대로 add()한다.

k번 반복되는 if문을 돌며, 다음을 수행한다.

• 만약 Queue가 비었다면, 모든 음식을 먹은 것이므로 즉시 반복문을 탈출한다.
• Queue의 가장 앞에서 Dish 하나를 꺼내, eat() 한다.
• eat() 이후 해당 Dish의 time 값을 확인한다.
  • time이 0보다 크다면, 그 Dish를 다시 Queue의 맨 뒤에 넣는다.
  • time이 0이라면, 다 먹은 접시이므로 Queue에 넣지 않는다.

 

반복문을 탈출한 뒤에,

Queue가 비어있다면 -1를 리턴한다.

Queue가 비어있지 않다면 Queue의 가장 앞에 있는 Dish의 num 값을 리턴한다.

 

작성한 정답코드 (솔루션 함수 방식)

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        
        Queue<Dish> q = new LinkedList<Dish>();
        
        for(int i=0; i<food_times.length; i++) {
            q.add(new Dish(i+1, food_times[i]));
        }
        
        for(int i=0; i<k; i++) {
            if(q.isEmpty()) break;
            Dish thisDish = q.poll();
            thisDish.eat();
            if(thisDish.getTime() == 0) continue;
            q.add(thisDish);
        }
        
        if(q.isEmpty()) answer = -1;
        else {
            Dish answerDish = q.poll();
            answer = answerDish.getNum();
        }        
        
        return answer;
    }
}

class Dish {
    private int num;
    private int time;
    
    public Dish (int num, int time) {
        this.num = num;
        this.time = time;
    }
    
    public void eat() {
        time--;
    }
    
    public int getNum() {
        return num;
    }
    
    public int getTime() {
        return time;
    }
}

 

이번주 스터디에서 위의 코드를 공유해보고, 스터디원들과 이야기를 나누어본 뒤, 효율성 테스트 만점에 도전하겠다.

 

 

---

개인 문제) 잃어버린 괄호

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

 

풀이

아래의 게시글에 작성하였다.

https://blowupmomo.tistory.com/325

#1541: 잃어버린 괄호