3 ≤ k ≤ 9 3 ≤ m ≤ 10 7 ≤ score의 길이 ≤ 1,000,000 1 ≤ score[i] ≤ k 이익이 발생하지 않는 경우에는 0을 return 해주세요
Key Point : score의 길이 10^6, 최대 이익
입력 길이가 10^6이므로 이중 for문은 지양하고, 최대 이익을 구하는 것은 정렬을 하는 게 효율적이라고 생각.
-> Arrays.sort()
import java.util.*;
class Solution {
public int solution(int k, int m, int[] score) {
Arrays.sort(score);
int answer = 0;
int repeat = score.length / m;
int rest = score.length % m;
// m개로 안 나뉘는 경우
if(score.length % m != 0) {
for(int i = 0; i < repeat; i++) {
answer += m*score[(i*m) + rest];
}
}
// m개로 나뉘는 경우
else {
for(int i = 0; i < repeat; i++) {
answer += m*score[i*m];
}
}
return answer;
}
}
+ 여담으로,
k가 만약 최대 점수를 나타내는 문제였다면, score의 인덱스를 나타내주는 i*m을 적절하게 변경하면 풀 수 있다.
응급실은 환자가 도착한 순서대로 진료를 합니다. 하지만 위험도가 높은 환자는 빨리 응급조치를 의사가 해야 합니다.
이런 문제를 보완하기 위해 응급실은 다음과 같은 방법으로 환자의 진료순서를 정합니다.
• 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼냅니다.
• 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.
즉 대기목록에 자기 보다 위험도가 높은 환자가 없을 때 자신이 진료를 받는 구조입니다.
현재 N명의 환자가 대기목록에 있습니다.
N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성하세요.
대기목록상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것입니다.
입력
첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.
두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.
위험도는 값이 높을 수록 더 위험하다는 뜻입니다. 같은 값의 위험도가 존재할 수 있습니다.
출력
M번째 환자의 몇 번째로 진료받는지 출력하세요.
예시 입력 1
5 2
60 50 70 80 90
예시 출력 1
3
예시 입력 2
6 3
70 60 90 60 60 60
예시 출력 2
4
접근방법
Queue를 활용하여 풀 건데, 이전과는 다르게 큐에 값을 하나만 넣는 것이 아니라 두 개를 넣어야 한다는 문제가 있다.
보통, 큐나 스택을 설명하면 아래의 그림처럼 하나의 필드만을 얘기하는데, 두 필드를 활용하려면 어떻게 해야 할까?
바로, 객체를 생성하여 큐에 객체의 주소를 집어넣는 것이다.
이렇게 하면, 주어진 m과 id가 같을 때의 값을 출력하면 된다.
import java.util.*;
class Person{
int id;
int priority;
public Person(int id, int priority) {
this.id = id;
this.priority = priority;
}
}
class Main{
public int solution(int n, int m, int[] arr) {
int answer = 0;
Queue<Person> Q = new LinkedList<>();
for(int i = 0; i < n; i++) {
Q.offer(new Person(i, arr[i]));
}
while(!Q.isEmpty()) {
Person tmp = Q.poll();
for(Person x : Q) {
if(x.priority > tmp.priority) {
Q.offer(tmp);
tmp = null;
break;
}
}
if(tmp!=null) {
answer++;
if(tmp.id == m) return answer;
}
}
return answer;
}
public static void main(String args[]) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
System.out.println(T.solution(n, m, arr));
}
}
getOrDefault는 HashMap의 key가 있으면 그 키의 value를 가져오고, key가 없으면 무엇을 반환할지 사용자가 설정할 수 있다.
HashMap<Character, Integer> map = new HashMap<>();
for(char x : s.toCharArray()) {
map.put(x, map.getOrDefault(x, 0) + 1); //key가 있으면 value를 반환하고, 없으면 0을 반환한다. 그리고 + 1 을 하여 카운팅
}
for(char key : map.keySet()) {
System.out.println(key + " " + map.get(key));
}
// 아래와 같은 값 출력
A 3
B 3
C 5
D 2
E 2
여기서, getOrDefault(x, 0) + 2 를 한다면, value의 값들이 1씩 증가해서 나올 것이다.
또한, getOrDefault(x, 1) + 1 를 한다면, key값이 없을 때 0이 아닌 1을 반환하여 나온다.
keySet() 함수
keySet() 함수는 HashMap에 저장되어 있는 key 값을 출력해준다.
HashMap<Character, Integer> map = new HashMap<>();
map.put('A', 1);
map.put('B', 2);
map.put('C', 3);
map.put('D', 4);
map.put('E', 5);
for(char key : map.keySet()) {
System.out.print(key + " ");
}
// A B C D E 출력
이 글의 문제는 인프런 강의에서, HashMap에 대한 분석은 아래 블로그에서 참고하였습니다.
개발자가 웹 페이지를 만드는 걸 생각해보자. 서로 다른 이름을 가진 사용자 수가 3명일 때, 웹 페이지는 총 3개일...수도 있다. 하지만 만약 9999명이 된다면? 사실 100명만 되도, 개발자는 복사 붙이기(일명 복붙)을 100번 해야 하는 셈이다. 이를 해결하고자 MVC 패턴이라는 것을 만들었고, 홈페이지를 보여주는 뷰(View)와, 사용자의 요청을 서버에서 처리하는 컨트롤러(Controller), 데이터를 관리하는 모델(Model) 방식을 만들기 시작했다.
1. 뷰 템플릿 생성하기
이제, MVC 패턴을 인텔리제이 환경에서 실행해 보자. 우선, 머스태치를 활용하여 뷰 템플릿을 만든다. 여기서 머스테치란, 다양한 언어를 화면에 제공하는 템플릿 엔진이라고 생각하면 된다.
src -> resources -> templates -> 우클릭 new -> file 클릭 -> first.mustache 생성
여기서 확장자에 .mustache를 적었음에도 수염과 같은 아이콘 모양이 나오지 않아도 걱정하지 말자.
인텔리제이의 왼쪽 상단에 file -> settings -> plugin -> mustache를 클릭하여 설치해주면 된다.
자, 빈 화면이 나오지 않았는가?
여기서 doc를 누르고 tab 버튼을 누르면, 다음과 같은 html 코드가 자동으로 생성된다.
head의 <title>태그는 웹 페이지의 제목을 나타낸다. 참고로, 왼쪽에 보이는 네이버의 아이콘은 파비콘이라고 하며, 이것도 설정할 수 있으나 여기서는 생략하겠다! <title> 태그 사이에 내가 원하는 웹 페이지의 제목을 적어보자.
그리고, <body> 태그 안에 <h1> 태그를 달고, 원하는 말을 넣어보자. 필자는 이렇게 했다. 그리고 {{username}}은 변수를 받아오는 형식이다. 이를 통해, 앞서 말했던 '각 사용자 마다 페이지를 만드는 것'을 하지 않고, 원하는 변수만 바꾸어 하나의 페이지에 여러 형식을 보일 수 있다.
뷰 페이지를 설정했으니, 그 화면을 볼 수 있도록 요청을 처리해주는 컨트롤러를 만들어보자.
com.example.practice 우클릭 -> package -> com.example.practice.controller 입력 -> FirstController.class 생성
package com.example.practice.controller;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.GetMapping;
@Controller //이 객체가 컨트롤러임을 알게 해주는 어노테이션
public class FirstController {
@GetMapping("/hi") //URL 요청 접수
public String helloWorld(Model model) {
model.addAttribute("username1", "김철수");
model.addAttribute("username2", "김영희");
return "first"; //first 머스테치 반환
}
}
여기서 @를 사용한 "어노테이션"을 볼 수 있다.
어노테이션이란, 소스 코드에 추가적으로 사용하는 메타 데이터의 일종이다. 코드를 서버에서 어떻게 처리해주어야 하는지 명시해주는 목적으로 사용된다.
@Controller는, 이 객체가 컨트롤러임을 명시한 어노테이션
@GetMapping("/hi")는, Client로 부터 URL을 요청 받았을 때, 아래 메소드가 실행되도록 하는 조회 어노테이션이다.
helloWorld 메서드의 매개변수는 Model로, MVC 패턴의 M을 담당하는 모델이다. 만약 빨간 줄이 뜬다면 alt + enter를 사용하여 import 해주면 된다.
코드를 다 작성하고, 서버를 실행하면 다음과 같은 로그를 볼 수 있는데, Tomcat started on port 8081을 보면 8081 포트에서 서버가 실행된 것을 확인할 수 있다. 그러나 대부분의 사람들은 8080 포트에서 서버가 동작할 것이다. 스프링 부트는 톰캣이라는 것에 담겨서 실행되므로 다음과 같은 로그가 뜬다.
localhost:8081/hi 에 접속하여 내가 원하는 뷰 페이지가 나오는지 확인해보자.
만약 한글이 깨져서 나온다면, src -> main -> resources -> application.properties 파일에서 다음과 같은 코드를 넣어주자.
거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter,$0.25)의 개수, 다임(Dime,$0.10)의 개수, 니켈(Nickel,$0.05)의 개수, 페니(Penny,$0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상$5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어,$1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)
출력
각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.
접근 방법
- 우선 Greedy 문제인 것을 직감적으로 알 수 있다. 입력받은 센트를 쿼터(Quarter,$0.25)로 나눴을 때 몫을 따로 저장하고, 나머지는 다시 피제수(나눠지는 수)가 된다. 그 피제수(나눠지는 수)를 다시 다임(Dime,$0.10)으로 나누고, 몫을 따로 저장하고 나머지는 다시 니켈(Nickel,$0.05)로 나눈다. 마지막으로 페니(Penny,$0.01)로 같은 작업을 반복하여 몫을 LinkedList에 저장하고 출력하면 된다.
정리
1. 쿼터, 다임, 니켈, 페니를 각각 25, 10, 5, 1 센트 단위로 생각하여 num배열을 하나 만든다. 그리고 몇 번 반복할지 T 값을 받는다.
2. 접근 방법에 해당하는 알고리즘을 구현한다.
3. Iterator를 사용하여 LinkedList의 원소를 출력한다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int[] num = {25, 10, 5, 1};
int T = sc.nextInt();
// // 1. LinkedList를 T 크기 만큼 만든다.
LinkedList<Integer> arr = new LinkedList<>();
for (int i = 0; i < T; i++) {
arr.add(sc.nextInt());
}
// 2. for문으로 각 값의 몫과 나머지를 구한다
for (int i = 0; i < arr.size(); i++) {
LinkedList<Integer> li = new LinkedList<>();
for (int j = 0; j < num.length; j++) {
// 몫 추가
li.add(arr.get(i) / num[j]);
// 나머지 처리
arr.add(i, arr.get(i) % num[j]);
arr.remove(i + 1);
}
Iterator<Integer> it = li.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
}
}
}
회고
- 해당 코드에서 핵심은 몫과 나머지를 어떻게 처리하냐의 문제이다. 반복 횟수가 많지는 않은데, ArrayList와 LinkedList 중 어떤 것을 써야 더 효율적일까를 고민해보았고, 물리적으로 비연속적인 LinkedList가 삽입/삭제에 더 유리하기 때문에 LinkedList를 채택했다. 사실 ArrayList를 써도 되지만, 각각의 특징을 공부하고 나니까 간단한 문제에도 이렇게 고민을 하게 되는 것 같다.
그리고, List형태를 출력할 때 for each문 보다 Iterator를 쓰는게 효율적이라는 것을 알게 되었다. for each문은 Map클래스를 출력할 때 용이하다.
