괴발개발 개발일지

백준알고리즘

- Bronze 2 -

 #4864. Gold Coins by Java and Javascript

사족

지난 2022년 4월, 프로젝트에 투입되었으나 사업장에 자리가 없어 한 달여간을 본사에서 대기하면서 백준 알고리즘을 풀고 블로그에 글을 쓰기 시작했다. 나름 꾸준히 잘 풀다가 평일 중 못 푼 만큼 주말에 풀고 그러다보니 예쁘지도 않고 루틴화가 되지 않는 것에 스트레스를 받아서 8월에 휴가기간에 쉰 뒤 주5일 꾸준히 풀었다. 꾸준히 풀다보니 어느덧 브론즈5와 브론즈4단계를 다 풀고 브론즈3으로 넘어갔다.

2023년 들어서는 새로 생긴 브론즈4와 브론즈3을 포함해 브론즈3까지 총 3문제를 각각 java와 javascript(node.js)로 풀고 있었다가 일이 바빠지면서 4월엔 브론즈 3과 브론즈2만 풀었다. 5월 첫 주 연휴도 있었고, 여러 일로 번아웃이 와서 쉬고, 무리하지 않기 위해 한 문제씩 다시 달리는 중,, 

문제

출처: https://www.acmicpc.net/problem/4864 

번역: https://www.acmicpc.net/board/view/91195

* 갈수록 번역이 없어 문제푸는게 힘들다..

접근 방법

일종의 계차수열이다.

처음 시작 수가 {1, 2, 4, 7, 11 ... } 로, 1, 2, 3, 4... 순으로 커지는 수열이다.

그리고 각 순서마다 코인이 1개(1원), 2개(2원), 3개(3원), 4개의 코인이 더해진다.

따라서 i는 1부터 입력값(=day)까지이고, 증가하는 수를 cnt로 설정해서 i에 더해주면 된다.

1번째: 1

2번째: 2(=1+1) 3

3번째: 4(=2+2) 5 6

4번째: 7(=4+3) 8 9 10

...

자세한건 코드에서 보자.

풀이

▶ Java

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// Code Start
		String line = ""; // 입력을 받을 변수
		String res = ""; // 출력할 변수
		while(!"0".equals(line=br.readLine())){ // 입력값이 0이 아닐때 계속 반복
			res += line + " "; // 입력값(day)에 공백을 더해준 문자열
			int day = Integer.parseInt(line); // 계산을 위해 int로 파싱
			int coin = 0; // 총 코인 값
			int cnt = 1; // 횟수(또는 차수)
			int idx = cnt; // cnt만큼 반복해서 더해주는데, 중간에 끊기는 수 때문에 설정한 변수
			for(int i=1; i<=day;) {
            			// i번째 때 cnt번 반복한 횟수가 총 횟수(day)보다 크면 day-i+1번 반복
                		// 아니면 cnt번 반복하기 위함
				idx = (i + cnt > day) ? day-i+1 : cnt;
                
                		// 횟수만큼 coin을 더해준다.
				for(int j=1; j<=idx; j++) {
					coin += cnt;
				}
				i += cnt; // i 증가
				cnt++; // cnt 증가
			}
			res += coin + "\n"; // 각 회차마다의 코인값 입력
		}
		
		bw.write(res); // 정답 출력
		// Code End
        
		bw.flush();
		bw.close();
		br.close();
	}
}

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v);
var res = '';

for(var i=0; i<input.length-1; i++){
    var day = input[i];
    var coin = 0, cnt = 1, idx = cnt;

    for(var j=1; j<=day;){
        idx = (j + cnt > day) ? day - j + 1 : cnt;

        for(var k=1; k<=idx; k++){
            coin += cnt;
        }
        j += cnt;
        cnt++;
    }

    res += day + ' ' + coin + '\n';
}
console.log(res.trim());

결과

블로그 글도 중요하긴 한데,, 좀처럼 틈이 안나서 일단은 잔디 심는걸로 만족하는 중..

출퇴근에 잔디에 운동에 바쁘다바빠 현대사회..

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #2455. 지능형 기차 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/2455 

접근 방법

간단한 수학 사칙연산 문제이다.

접근 방법이야 여러 가지가 있겠지만, 나는 Arrays.sort()를 이용해서 풀었다.

각 줄에 내린 사람 수, 탄 사람 수가 정해지므로 빼주고 더해주면 그 역을 지난 후의 남아있는 사람 수를 구할 수 있다.

풀이

▶ Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int result = 0;
    	int[] arr = new int[4];
    	for(int i=0; i<4; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		result -= Integer.parseInt(st.nextToken());
    		result += Integer.parseInt(st.nextToken());
    		arr[i] = result;
    	}
    	Arrays.sort(arr);
    	System.out.println(arr[3]);
    }
}

평소 Scanner를 쓰다가 메모리문제나 속도 문제로 틀린 경우가 있어서 BufferedReader와 StringTokenizer 사용법을 익혔다. + StringBuilder도 사용해봄(브론즈3. 별찍기문제들)

다른 분들의 BufferedReader나 StringTokenizer 사용법을 정리한 글들이 많으니 찾아서 공부하는 것을 추천.

이해한 바를 간단히 얘기하자면, BufferedReader(+InputStreamReader)는 Scanner의 역할을 한다고 볼 수 있고(대신 모든 값들을 String으로 가져온다.) StringTokenizer는 구분자를 사용해서 쪼갠다고 보면 된다.(node.js의 split()과 유사)

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var arr = [];
var result = 0;

for(var i=0; i<input.length; i++){
	result = person(input[i], result);
	arr[i] = result;
}

arr.sort((a,b) => a-b);

console.log(arr[3]);

function person(input, result){
	var [outPerson, inPerson] = input.toString().trim().split(' ').map(v => +v);
	result -= outPerson;
	result += inPerson;
	return result;
}

결과

여담:

요즘 "출퇴근 + 운동 또는 집안일 + 백준 한 문제 풀기 + 게임 일일퀘스트"로 루틴이 정해지다보니 글 쓸 체력까진 남지 않았다. (그리고 최근 문제라고는 별찍기정도라서..) 루틴에 문제풀이 정리하는 것도 추가하려했는데,, 조금 힘든듯

그래도 잔디가 하나하나 쌓이고 있는걸 보니 뿌듯하기도 하고 조금씩이라도 생각하는 시간?을 갖다보니 리프레시도 되는 기분..

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1703. 생장점 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1703

접근 방법

문제가 번역투라 이해하는데 시간이 조금 걸렸다.

입력되는 값의 한 줄을 봤을 때 맨 앞 숫자는 최종적인 나무의 나이이고,

이어서 나열되는 숫자들을 2개씩 잘라서 봤을 때 각 생장점 당 자라나는 나무줄기의 수와 잘라낸 가지의 수이다.

입력 예시 중 세 번째에 있는 "3 3 0 2 0 2 0"를 보면, "3 / 3 0 / 2 0 / 2 0" 으로 쪼개서 볼 수 있고, 이는 즉 3년된 나무이고, 첫 해에 3개의 가지가 돋아났으며 잘라낸 가지는 없음. 다음 해엔 각 가지마다 2개씩 돋아나고 잘라낸 가지는 0개, 마지막해에도 각 가지당 2개씩 돋아나고 잘라낸 가지는 0개 라는 말이다.

따라서 마지막 가지의 수를 a, 다음 해의 자라나는 가지의 수(생장점 당)를 b, 잘라내는 가지의 수를 c 라고 하면

다음 해의 가지의 수는 a * b - c가 된다.

처음 0년째의 가지의 수는 1이므로 곱셈에도 문제가 없다.

풀이

▶ Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int a = 0; // 나무의 나이
    	int b = 1; // 각 해에 남은 가지 수(0년차에는 1)
    	
    	while(true) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		a = Integer.parseInt(st.nextToken());
    		
    		if(a == 0) break;
    		
    		for(int i=0; i<a; i++) {
    			b *= Integer.parseInt(st.nextToken()); // 각 생장점마다 자라난 가지의 수를 곱해줌
    			b -= Integer.parseInt(st.nextToken()); // 잘라낸 가지의 수를 빼줌
    		}
    		System.out.println(b);
    		
    		// 초기화
    		a = 0; 
    		b = 1;
    	}
    	
    	br.close();
    }
}

▶ Javascript (node.js)

var fs = require('fs');

var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
 
for(var i=0; i<input.length - 1; i++){
	main(input[i]); // \n으로 나눠서 br.readLine()의 역할을 해줌
}
 
function main(input){
	var tree = input.toString().trim().split(' ').map(Number); // st.nextToken()의 역할
	var year = parseInt(tree[0]);
	var bridge = 1;
 
	for(var i=1; i<=year*2; i+=2){ // 각 해마다 두 번의 계산이 필요하므로 year*2만큼 반복해야함
        // i는 두 개씩 커짐
		bridge *= tree[i];
		bridge -= tree[i+1];
	}
 
	console.log(bridge);
}

결과

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1598. 꼬리를 무는 숫자 나열 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1598 

접근 방법

행(가로)을 기준으로 보면, 맨 위부터 차례대로 4로 나눈 나머지가 1, 2, 3, 0이다.

또한 index를 보면(각 행의 숫자들의 위치 index) 4로 나눈 몫을 생각하면 된다.

예시의 11과 3을 보자.

11은 몫이 2이고 나머지가 3이므로 (2, 3)이라고 보고, 33은 몫이 8이고 나머지가 1이므로 (8,1)이라고 생각하면

11과 33 사이의 직각거리는 (8-2) + (3-1) = 6+2 = 8이 나오는 것을 확인할 수 있다.

즉, (몫의 차 절대값) + (나머지의 차 절대값)을 구하면되므로 Math.abs()를 이용하자.

(아니면 결과값이 음수면 *(-1)처리를 해주게끔 알고리즘을 짜면 된다.)

주의할 점은 4로 나눈 나머지가 0일 때 , 즉 4의 배수일 때에만 주의해주면 된다.

11과 12를 예로 들면 둘의 직각 거리는 1이지만 위의 식대로 처리하면 4가 나온다.

따라서 4의 배수일 때에는 (몫-1)과 (나머지=4)로 처리해주는 것을 잊지 말자.

풀이

▶ Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine()); // 원숭이가 생각한 숫자
        int a = Integer.parseInt(st.nextToken()); // 첫 번째 숫자
        int b = Integer.parseInt(st.nextToken()); // 두 번째 숫자
        
        int shareA = (a % 4 == 0 ? (a / 4) - 1 : a / 4);
        int shareB = (b % 4 == 0 ? (b / 4) - 1 : b / 4); // a와 b를 각각 4로 나눈 몫
        int remaindA = (a % 4 == 0 ? 4 : a % 4);
        int remaindB = (b % 4 == 0 ? 4 : b % 4); // a와 b를 각각 4로 나눈 나머지
        
        int result = Math.abs(shareA - shareB) + Math.abs(remaindA - remaindB);
        System.out.println(result);
        br.close();
    }
}

▶ Javascript (node.js)

var fs = require('fs');
var [a, b] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(v => +v);

var share_a = (a % 4 == 0 ? parseInt(a/4)-1 : parseInt(a/4));
var share_b = (b % 4 == 0 ? parseInt(b/4)-1 : parseInt(b/4));
var rem_a = (a % 4 == 0 ? 4 : a%4);
var rem_b = (b % 4 == 0 ? 4 : b%4);

var result = Math.abs(share_a - share_b) + Math.abs(rem_a - rem_b);
console.log(result);

Javascript의 경우, 몫을 자동 정수화 하지 않기 때문에 parseInt() 처리를 잊지 말자.

결과

확실히 브론즈 3단계로 오니까 생각할 것이 조금이라도 생겨서 문제 푸는 재미가 있네

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1547. 공 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1547 

접근 방법

일단 공의 시작 위치가 1이므로 1에 고정해놓고, 입력받은 값 중에 공과 같은 번호가 있으면 다른 번호의 값을 공의 위치에 저장해주면 된다.

말로는 쉬운데 이걸 코드화하는데에 생각할 시간이 좀 필요하다.

아래 코드의 주석을 보면서 이해해보자.

풀이

▶ Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int m = Integer.parseInt(br.readLine()); // 시도 횟수
		int ball = 1; // 공의 위치
		int a = 0, b = 0; // 입력받은 숫자를 저장할 변수
		
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()); // 바꾸는 컵의 번호
			a = Integer.parseInt(st.nextToken()); // 첫 번째 컵 번호
			b = Integer.parseInt(st.nextToken()); // 두 번째 컵 번호
			
			if(a == ball) // a가 ball이 있는 위치의 번호이면 b와 교체될 예정이므로
				ball = b; // ball을 덮고 있는 컵의 번호를 b로 바꾼다.
			else if(b == ball) // 반대로 b가 ball이 있는 위치의 번호이면 a와 교체될 예정이므로
				ball = a; // ball을 덮고 있는 컵의 번호를 a로 바꾼다.
			// 그 외에는 if - else문을 타지 않을 것이므로 저장된 ball의 값을 가지고 반복문을 진행한다.
		}
		
		System.out.println(ball); // 마지막에 저장된 ball의 값만 출력하면 된다.
	}
}

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var result = 1; // 공을 덮고 있는 컵의 번호(시작 = 1)

// input[0] = m인데 여기서는 필요가 없다.
// var m = parseInt(input[0]); 으로 선언해준 뒤 하단 반복문에서 i<=m으로 사용해도 되긴 한다.

for(var i=1; i<input.length; i++){
    // (1) \n으로 자른 값들에 첫 번째, 두 번째 컵의 번호가 담겨 있으므로 input[i]값과 ball의 값을 함수에 전달
    result = changeBall(input[i], result); //  (3) result값에 반복문을 진행하면서 반환되는 result값을 저장 
}

console.log(result); // (4) 최종 저장된 result값을 출력

function changeBall(input, result){
    // (2) 교환하는 컵의 번호를 input에서 공백(' ')으로 쪼갠 후 숫자로 변환하여 저장.
    var [a, b] = input.toString().trim().split(' ').map(Number);
    
    if(a == result){ // 첫 번째 컵의 번호가 공을 덮고 있는 컵의 번호와 같으면
        result = b; // 두 번째 컵의 번호로 바꿔준다.
    } else if(b == result){ // 두 번째 컵의 번호가 공을 덮고 있는 컵의 번호와 같으면
        result = a; // 첫 번째 컵의 번호로 바꿔준다.
    }

    return result; // 공을 덮고있는 컵의 번호를 반환해준다.
}

javascript의 경우 함수를 생성해서 반환되는 값을 저장해주는 형식이므로, 괄호 안 숫자 순서대로 진행된다.

흐름을 파악하기 위해 번호를 붙여서 주석을 달았다.

결과

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1284. 집 주소 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1284 

접근 방법

입력받은 숫자를 .split('')을 이용해 하나하나 쪼개서 경우에 따라 값을 늘려주면 된다.(0은 4, 1은 2, 나머지는 3씩 늘려주기)

풀이

▶ Java

import java.io.*;

public class Main {

	public static int size(String num) {
		
		String[] str = num.split(""); // 받아온 숫자를 쪼개기
		int result = 2 + (str.length - 1); // 양옆 기본 2cm, 숫자의 개수 -1 만큼 1cm 발생
		
		for(int i=0; i<str.length; i++) {
			switch(str[i]) {
				case "0" :
					result += 4;
					break;
				case "1" :
					result += 2;
					break;
				default:
					result += 3;
					break;
			}
		}
		
		return result;
	}
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result = 0;
        for(;;) {
        	String num = br.readLine();
        	
        	if("0".equals(num))
        		break;
        	
        	result = size(num);
        	
        	System.out.println(result);
        }
    }
}

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 마지막은 0이므로 굳이 반복문에 넣지 않음
for(var i=0; i<input.length-1; i++){
    split(input[i]);
}

function split(num){
    var str = num.toString().split('');
    var result = 2 + (str.length - 1);
    
    for(var i=0; i<str.length; i++){
        switch(str[i]){
            case "0":
                result += 4;
                break;
            case "1":
                result += 2;
                break;
            default:
                result += 3;
                break;
        }
    }
    
    console.log(result);
}

결과

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1267. 핸드폰요금 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1267 

접근 방법

주의할 점. 총 통화요금에 대해서 요금이 부가되는 것이 아니고, 각 통화시간마다 부과되는 것임을 명심하자.

그 외에는 문제를 식으로 옮기면 끝.

영식: 30초마다 10원씩 부과 >> 10원 * ((통화시간 / 30) + 1)

민식: 60초마다 15원씩 부과 >> 15원 * ((통화시간 / 60) + 1)

통화시간에 기준시간을 나눠준 뒤 1을 더하는 이유는, 0초 ~ 기준시간 미만 범위가 포함되기 때문이다.

0초 ~ 기준시간 미만 : 1번째

기준시간 * 1 ~ 기준시간 * 2 미만 : 2번째

기준시간 * 2 ~ 기준시간 * 3 미만 : 3번째

...

수열을 안다면 이해하기 쉬울 것으로 생각된다.

풀이

▶ Java

import java.io.*;
import java.util.*;

public class Main {
	
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 통화횟수
        
        StringTokenizer st = new StringTokenizer(br.readLine()); // 통화 시간을 쪼개서 입력받기
        int sec = 0; // 통화시간을 받을 변수
        int y = 0; // 영식요금제
        int m = 0; // 민식요금제
        
        for(int i=0; i<n; i++) {
        	sec = Integer.parseInt(st.nextToken());
        	y += 10 * ((sec / 30) + 1);
        	m += 15 * ((sec / 60) + 1);
        }
        
        String result = ((y < m) ? "Y " + y
        		: ((y > m) ? "M " + m : "Y M " + y));
        System.out.println(result);
        
    }
}

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var n = parseInt(input[0]);
var sec = input[1].toString().trim().split(' ').map(Number);
var y = 0, m = 0;

for(var i=0; i<sec.length; i++){
    y += (parseInt(sec[i] / 30) + 1) * 10;
    m += (parseInt(sec[i] / 60) + 1) * 15;
}

var result = ((y < m) ? "Y " + y
        	: ((y > m) ? "M " + m : "Y M " + y));
console.log(result);

결과

End.

heisely's 괴발개발 개발일지

백준알고리즘

- Bronze 3 -

 #1247. 부호 by Java and Javascript

문제

출처: https://www.acmicpc.net/problem/1247 

접근 방법

1. 주어지는 정수의 절댓값이 int의 범위를 넘어섬 >> BigInteger 사용

2. BigInteger들을 더해야하므로 x.add(bigInt) 사용

3. BigInteger를 사용하기 때문에 Java에서는 compareTo() 이용

풀이

▶ Java

import java.io.*;
import java.math.*;

public class Main {
	
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = 0;
        BigInteger zero = new BigInteger("0"); // 부호판별시 사용할 BigInt 0
        
        for(int i=0; i<3; i++) { // 총 3문제가 나온다고 했으므로 3번 반복
        	n = Integer.parseInt(br.readLine());
			BigInteger s = new BigInteger("0"); // n개의 수를 더해줄 BigInt 변수 선언
			
        	for(int j=0; j<n; j++) {
    			BigInteger bi = new BigInteger(br.readLine());
    			s = s.add(bi); // 변수 s에 BigInt bi를 더해준 값을 저장
    		}
        	
                // A.compareTo(B) : A와 B를 비교하여 0, 1, -1 반환(A=B / A>B / A<B)
        	if(s.compareTo(zero) == 0) {
        		System.out.println(0);
        	} else if (s.compareTo(zero) == -1) {
        		System.out.println("-");
        	} else {
        		System.out.println("+");
        	}
        }
        
    }
}

▶ Javascript (node.js)

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(BigInt);
var zero = BigInt("0");

for(var i=0; i<input.length;){
	var n = Number(input[i]);
	var s = BigInt("0");
	
	for(var j=1; j<=n; j++){
		s += input[i+j];
	}
	
	var result = s.toString(); // BigInt를 숫자화
	
	if(result == 0){
		console.log(0);
	} else if (result > 0){
		console.log("+");
	} else  {
		console.log("-");
	}
	
	i += (n+1);
}

Javascript로 푸는 경우 이미 입력값들을 배열에 저장한 뒤 사용하기 때문에, 반복문을 돌릴 때 주의해야 한다.

또한 Java와 달리 BigInt의 값은 "1n"의 형식으로 n이 붙어서 나오기 때문에, toString()을 이용해서 숫자화 해준 뒤 비교해줘야 한다.

결과

End.

heisely's 괴발개발 개발일지