각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
예제 입력 1
8 9 10
예제 출력 1
1 2 8 9 10
접근 방법
이 문제는 처음 문제를 보고 뜻을 잘 이해해야한다.
[한 물통이 비거나, 다른 한 물통이 가득 찰 때까지] 물을 옮길 수 있다고 하였다.
이 문장의 뜻은 A물통에서 B물통으로 물을 옮긴다고 하였을 때,
B물통이 다 차지 않고 A물통에도 물이 남아 있는데 -> 물을 옮기는 것을 멈출 수 없다는 뜻이다.
이렇게 되면 물을 쏟아 부을 때 총 두가지 케이스로 나뉘게 된다.
1) A -> B 일 때, B가 넘치는 경우
2) A -> B 일 때, B가 넘치지 않는 경우
그리고 물통은 총 A,B,C이므로 from 물통과 to물통의 경우는 아래와 같이 총 6가지로 나뉘게 된다.
A->B
B->A
B->A
B->C
C->A
C->B
위 6가지 각각의 경우에 대해 bfs를 활용하여 "A물통이 비었을 때 C물통에 있는 물의 양" 모든 케이스를 조사해보자.
이때, 조사 완료된 케이스를 어떻게 체크할까?
A,B,C 물통의 물의 양 상태를 배열의 인덱스로 활용하면 된다. 즉, 물통에 1,2,3씩 물이 담겨 있는 상태고 이 상태에서 A,C물통의 조건을 조사했다면 visited[1][2][3] = true로 저장하면 된다. 코드는 아래와 같다.
import java.util.*;
public class BOJ_2251_물통옮기기 {
public static class Water{
int a, b, c;
public Water(int a, int b, int c){
this.a = a;
this.b = b;
this.c = c;
}
}
static ArrayList<Integer> ansList;
static int capaA, capaB, capaC;
static boolean[][][] visited = new boolean[201][201][201];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
ansList = new ArrayList<>();
capaA = sc.nextInt();
capaB = sc.nextInt();
capaC = sc.nextInt();
bfs();
Collections.sort(ansList);
for(int i = 0; i<ansList.size(); i++){
System.out.print(ansList.get(i) + " ");
}System.out.println();
}
public static void bfs(){
Queue<Water> que = new LinkedList<Water>();
que.add(new Water(0,0,capaC)); //초기 값 셋팅 (처음엔 C만 차 있음)
//visited[0][0][capaC] = true;
while(!que.isEmpty()){
//검사한 케이스면 패스
Water water = que.poll();
int a= water.a;
int b = water.b;
int c = water.c;
// System.out.println(a + " " + b + " " + c +" ");
if(visited[a][b][c] == true) continue;
//검사 안 했으면 체크하고
visited[a][b][c] = true;
//A 물통 비었으면 그 케이스 카운트
if(a==0) ansList.add(c);
// 물 옮기기. 물이 넘칠 때와 넘치지 않을 때 각각 나눠서
//A -> B
if(a + b >= capaB){ que.add(new Water(a-(capaB-b), capaB, c));} //옮기면 넘치는 경우
else { que.add(new Water(0, a+b, c)); }
//A -> C
if(a + c >= capaC) { que.add(new Water(a-(capaC-c), b, capaC));}
else { que.add(new Water(0, b, a+c)); }
//B -> A
if(b + a >= capaA){ que.add(new Water(capaA, b-(capaA-a), c)); }
else { que.add(new Water(b+a, 0, c)); }
//B -> C
if(b + c >= capaC){ que.add(new Water(a, b-(capaC-c), capaC)); }
else { que.add(new Water(a, 0, b+c)); }
//C -> A
if(c + a >= capaA) { que.add(new Water(capaA, b, c-(capaA-a)));}
else{ que.add(new Water(a+c, b, 0)); }
//C -> B
if(c + b >= capaB) { que.add(new Water(a, capaB, c-(capaB-b)));}
else{ que.add(new Water(a, b+c, 0)); }
}
}
}
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
접근 방법
먼저 같은 조에 속한 원생들은 서로 인접해야 하는 것에 주의하자.
하기의 입력 예시로 생각해보자.
5 3
1 3 5 6 10
여기서 3개의 조로 원생들을 나누어야 하는데, 같은 조 원생들은 서로 인접해야 하기 때문에
주어진 1 3 5 6 10 에서 2개의 막대기를 원생들 사이에 두면 조건을 만족하면서 조를 나눌 수 있다. 예시는 아래와 같다.
1 | 3 5 | 6 10 => 비용 : 2 + 4 = 6
1 3 | 5 | 6 10 => 비용 : 2 + 4 = 6
1 3 | 5 6 | 10 => 비용 : 2 + 1 = 3 (최저 비용)
그렇다면 막대기 K-1개는 어디에 두어야할까? 바로 인접한 원생과의 키차이가 가장 크게 나는 곳에 두어야 한다. 키차이가 가장 크게 나는 곳에 막대기를 두게 되면, 그 키차이(비용)은 제외되어 버리기 때문이다.
위 예시에서 생각해보면
1 3 5 6 10 일 때, 원생들과의 키차이는
2 2 1 4 이기 때문에
키차이가 2와 4인 곳에 막대기를 두어야 하는 것이다. 그럼 비용에서 2, 4는 제외되고 2, 1만 남는다. (2+1이 최소 비용)
일반화를 해보면 다음과 같다.
1) 인접한 원생들 사이의 키차이를 구한다.
2) 키차이를 내림차순으로 정렬한다. (위 예시에서는 4 2 2 1)
3) 막대기 K-1개로 조를 나눈다. 즉 내림차순으로 정렬된 수열에서 K-1개를 제외한다.
4) 제외하고 남은 키차이들을 다 더하면 그 합이 티셔츠의 최소 비용이 된다.
import java.io.IOException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class BOJ_13164_행복유치원 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int answer = 0;
ArrayList<Integer> tall = new ArrayList<>();
ArrayList<Integer> subTall = new ArrayList<>();
//키 입력받기
for(int i = 0; i<N; i++){
tall.add(sc.nextInt());
}
//키 차이 구하기
for(int i = 0; i < N-1; i++){
subTall.add(tall.get(i+1) - tall.get(i));
}
//키 차이 오름차순 정렬
Collections.sort(subTall);
//가장 큰 키차이를 K-1개 제외하고 나머지들 더함
for(int i = 0; i < N-K; i++){
answer += subTall.get(i);
}
System.out.println(answer);
}
}
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.
그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.
현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.
출력
첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.
접근 방법
이 문제는 규칙을 잘 찾아야하는 문제이다. 문제에서 주어진 조건을 봐보면 키를 1cm 차이가 나게 조절을 해야하는데, 이 때 첫째 날과 마지막 날은 무조건 1cm가 되어야 한다. 이 점을 유의깊게 봐보자.
우리는 최소의 일수를 구해야 하기 때문에 첫째 날 키 조절 양을 1cm 로 시작을 해서 2, 3, 4,,, 로 키를 키워나가야 하지만
마지막 날의 키 조절 양도 1cm로 끝나야하기 때문에
어느 정도 고점 x에 도달한 뒤에는 x-1, x-2, x-3,,, 1 과 같이 키의 양을 줄여나갸야 하는 것이다.
그렇다면 그 고점을 어떻게 찾아야할까?
규칙이 보이지 않을 때에는 먼저 나열을 쭉 해보고 그 안에서 규칙을 찾아보는것도 좋은 방법이다.
키 차이 (Y-X) 를 sub이라고 하자. 멍멍이와 원숭이의 키가 같아지기 위한 최소 일수를 찾아보자.
* 괄호 안의 수는 각 날에 조절한 키의 양이다.)
sub = 1 일 때 : 1일 (1)
sub = 2일 때 : 2일 (1, 1)
sub = 3일 때 : 3일 (1, 1, 1)
sub = 4일 때 : 3일 (1, 2, 1)
sub = 5일 때 : 4일 (1, 2, 1, 1)
sub = 6일 때 : 4일(1, 2, 2, 1)
sub = 7일 때 : 5일(1, 2, 2, 1, 1)
sub = 8일 때 : 5일 (1, 2, 2, 2, 1)
sub = 9일 때 : 5일 (1, 2, 3, 2, 1)
sub = 10일 때 : 6일 (1, 2, 3, 2, 1, 1)
sub = 11일 때 : 6일 (1, 2, 3, 2, 2, 1)
sub = 12일 때 : 6일 (1, 2, 3, 3, 2, 1)
sub = 13일 때 : 7일 (1, 2, 3, 3, 2, 1, 1)
sub = 14일 때 : 7일 (1, 2, 3, 3, 2, 2, 1)
sub = 15일 때 : 7일 (1, 2, 3, 3, 3, 2, 1)
sub = 16일 때 : 7일 (1, 2, 3, 4, 3, 2, 1)
sub = 17일 때 : 8일 (1, 2, 3, 4, 3, 2, 1, 1)
제곱수를 보면 sub = N^2 라고 했을 때 고점이 N 인것을 확인할 수 있고, 필요한 최소 일수는 N^2 - 1 인 것을 확인할 수 있다. 그렇다면 제곱수가 아닌 수는 어떤 규칙이 있을까?
예를 들어 sub = 13일 때를 보자. 13보다 작은 제곱수인 9(1, 2, 3, 2, 1) 을 제외하면 (1, 2, 3, 3, 2, 1, 1) 중 (3, 1)이 남는데
이는 루트 9보다 작은 수 중 적당히 끼워 넣은 것이다.
즉,
1) 키 차이보다 작은 최대 제곱수 N^2 를 찾고
2) 키 차이에서 최대 제곱수를 뺀 나머지를 구한 다음
3) 나머지가 N이하의 수들로 어떻게 구성되어있는지 찾으면 되는 것이다. (문제에서 최소 일수를 찾는 것이 목표이기 때문에 이때 가장 큰 수인 N부터 검사하도록 한다. )
이를 코드로 나타내면 아래와 같다.
*주의 ) N과 ans를 long형으로 선언해야한다. (오버플로우 방지 (?) )
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int sub = y - x;
if(sub == 0){ // 예외처리 : 처음부터 키가 같을 때
System.out.println(0);
return;
}
long N = 1; //long 형으로 선언해야한다.
long ans = 0;
while(N*N <= sub){ //키차이보다 작은 최대 제곱수를 찾는다.
N++;
}
N-=1; //N++된 상태로 while문을 빠져나오기 때문에 -1 해준다.
ans = 2*N - 1; //answer 초기 값 설정
sub -= N*N; //제곱수만큼 빼고 남은 키로 while 문을 돈다.
while(sub > 0){
for(long i = N; 1<=i; i--){ //N부터 시작해서
if(i<=sub){ //i가 sub보다 작으면
ans+=1;
sub -= i; //sub에서 i를 뺀다.
break;
}
else continue;
}
}
System.out.println(ans);
}
}
압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.
입력
첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.
출력
첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.
접근 방법
[처음 코드]
입력 문자열을 stack 에 push 한 뒤, 단순하게 문자열 끝(stack의 top)부터 탐색을 진행했다. 탐색을 진행할 때는 세가지 케이스를 나눴다. 먼저 그냥 숫자이면 len을 하나씩 증가시키고, ')'이면 pop 하고, '('이면 '('의 앞 숫자(k)를 len에 곱했다.
그러나 아래 코드는 문제에서 주어진 예제는 맞췄으나, 또 다른 반례를 생각하지 못했다.
반레 : () 안에 압축 문자열이 여러개가 포함이 될 때 -> ex. 45(12)53(52(1111)42(222))
import java.util.*;
public class Main {
public static void main(String[] args) {
String input;
Scanner sc = new Scanner(System.in);
input = sc.next();
int inputLen = input.length();
char[] arr = input.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i < inputLen; i++){
stack.push(arr[i]);
}
int len = 0;
while(!stack.empty()){
char topChar = stack.peek();
if(topChar == ')') {
stack.pop();
}
else if(topChar == '('){
stack.pop();
int k = (int)stack.pop() - '0';
len = len*k;
}
else{
len++;
stack.pop();
}
}
System.out.println(len);
}
}
[정답 코드]
입력 문자열을 끝이 아닌 처음부터 stack에 push 해가면서 탐색을 진행한다. 단 ')'를 만나기 전까지 탐색을 진행한다. ')'를 만나면 push 했던 문자열들을 pop 해가면서 압축 문자열을 해제하는 로직을 수행한다. 이 때 while문을 돌면서 '('를 만나기 전까지 stack에서 pop해가면서 길이를 계산한다. K(Q)의 길이를 알아냈다면, 그 길이를 다시 stack에 push하는데, 이는 하나의 괄호 쌍 안에 여러개의 압축 문자열이 있을 때를 위한 것이며, 계산한 압축 문자열의 길이와 기존에 입력 문자열을 구분하기 위해 계산한 압축 문자열의 길이를 push 할 때에는 길이를 push한 뒤에 바로 "+"를 push 해준다.
입력 문자열의 끝까지 push하면서 탐색을 끝냈다면, stack에서 하나씩 Pop 해가면서 최종 길이를 계산한다.
*주의 : Stack Type을 Char형으로 정의 시 형변환 하는 과정에서 오류 -> String Type으로 정의해야한다.
import java.util.*;
import java.io.*;
public class BOJ1662_압축 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arr = br.readLine().split("");
Stack<String> stack = new Stack<String>();
for(int i = 0; i < arr.length; i++){
if(!arr[i].equals(")")) {stack.push(arr[i]);}
else {
int cnt = 0;
while (!stack.peek().equals("(")) {
String topStr = stack.pop();
if (topStr.equals("+")) {
int len = Integer.parseInt(stack.pop());
cnt += len;
} else cnt++;
}
stack.pop(); // ( 제거
int k = Integer.parseInt(stack.pop());
cnt = cnt * k;
stack.push(String.valueOf(cnt));
stack.push("+");
}
}
int answer = 0;
while(!stack.empty()){
if(stack.peek().equals("+")){
stack.pop();
//System.out.println(stack.peek());
answer += Integer.parseInt(stack.pop());
}
else{
stack.pop();
answer++;
}
}
System.out.println(answer);
}
}
(console.log(stream) 을 myFace.srcObject = myStream 으로 변경)
이제 소리와 화면을 on/off 할 수 있도록 버튼을 생성해보자.
home.pug 에 button을 추가해주고
doctype html
html(lang="en")
head
meta(charset="UTF-8")
meta(http-equiv="X-UA-Compatible", content="IE=edge")
meta(name="viewport", content="width=device-width, initial-scale=1.0")
title Noom
link(rel="stylesheet", href="https://unpkg.com/mvp.css")
body
header
h1 Noom
main
video#myFace(autoplay, playsinline, width = "400", height = "400")
button#mute Mute
button#camera Turn Camera Off
script(src="/socket.io/socket.io.js")
script(src="/public/js/app.js")
버튼을 getElementID를 통해 frontend 로 가져온다.
function handleMuteClick() 에서는 음소거 여부를 추적할 수 있는 variable 이 필요하고,
function handleCameraClick()에서는 카메라가 켜져 있거나 꺼져 있는지 추적하는 variable 이 필요하다.
(현 상태를 파악해야 반대 상태로 전환할 수 있기 때문)
이를 위해 변수 두 개를 선언해준다.
letmuted=false;
letcameraOff=false;
const socket = io();
const myFace = document.getElementById("myFace");
const muteBtn = document.getElementById("mute");
const cameraBtn = document.getElementById("camera");
let myStream;
let muted = false;
let cameraOff = false;
async function getMedia(){
try{
myStream = await navigator.mediaDevices.getUserMedia({
audio : true,
video : true,
});
myFace.srcObject = myStream;
//console.log(myStream);
} catch(e){
console.log(e);
}
}
getMedia();
function handleMuteClick() {
if (!muted) {
muteBtn.innerText = "Unmute";
muted = true;
} else {
muteBtn.innerText = "Mute";
muted = false;
}
}
function handleCameraClick() {
if (cameraOff) {
cameraBtn.innerText = "Turn Camera Off";
cameraOff = false;
} else {
cameraBtn.innerText = "Turn Camera On";
cameraOff = true;
}
}
muteBtn.addEventListener("click", handleMuteClick);
cameraBtn.addEventListener("click", handleCameraClick);
버튼을 클릭했을 때의 Event Listener 를 추가해주고 이에 대한 function 도 작성해준다.
doctype html
html(lang="en")
head
meta(charset="UTF-8")
meta(http-equiv="X-UA-Compatible", content="IE=edge")
meta(name="viewport", content="width=device-width, initial-scale=1.0")
title Noom
link(rel="stylesheet", href="https://unpkg.com/mvp.css")
body
header
h1 Noom
main
div#welcome
form
input(placeholder="room name", required, type = "text")
button Enter Room
div#room
h3
ul
form#name
input(placeholder="nickname", required, type = "text")
button Save
form#msg
input(placeholder="message", required, type = "text")
button Send
script(src="/socket.io/socket.io.js")
script(src="/public/js/app.js")
form 을 추가했으니 eventListener 가 필요하다. 이제 app.js를 수정해주자.
123 방에 접속하면 처음 nickname 을 지정하지 않았을 때는 Anon 이 채팅방에 접속했다고 출력되며,
nickname 을 각자 지정하고 메세지를 전송하면 아래와 같이 메세지 앞에 nickname 이 붙어서 출력된다.
그리고 user2 (좌측)가 창을 닫으면 user1 (우측) 창에 user2 left 라는 텍스트가 출력되는 것도 확인할 수 있다.
Challenge
채팅 방에 입장하기 전에 방이름과 닉네임을 먼저 물어보는 코드를 작성해보자.
(결과)
//home.pug
doctype html
html(lang="en")
head
meta(charset="UTF-8")
meta(http-equiv="X-UA-Compatible", content="IE=edge")
meta(name="viewport", content="width=device-width, initial-scale=1.0")
title Noom
link(rel="stylesheet", href="https://unpkg.com/mvp.css")
body
header
h1 Noom
main
div#welcome
form#nickname-and-room-name
input#nickname(placeholder="nickname", required, type = "text")
input#room-name(placeholder="room name", required, type = "text")
button Enter Room
div#room
h3
ul
form#msg
input(placeholder="message", required, type = "text")
button Send
script(src="/socket.io/socket.io.js")
script(src="/public/js/app.js")
