앞만 보는 사람

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

문제

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(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클래스를 출력할 때 용이하다.

자바를 공부하다 보면 헷갈리는 용어가 많은데, 특히 오버로딩(Overloading)과 오버라이딩(Overriding)이 비슷해서 많이 헷갈린다. 그런데, 사실 둘은 아무 관계 없는 내용이다. 둘의 차이점을 알아보자.

1. 오버로딩(Overloading)

• 메서드 이름이 같다.
• 매개 변수, 반환형(return)은 달라도 된다. 
• 같은 클래스 내에 선언 되어야 한다.
• 만약 매개 변수의 개수가 같다면 자료형이 달라야 하고, 자료형이 모두 같다면 매개 변수의 개수를 다르게 해야 한다.

코드 예시를 통해 개념을 익혀보자.

class Hello {
    void overL() {
        System.out.println("오버로딩을 위한 메서드");
    }

    void overL(String str){
        System.out.println("매개 변수 타입이 String 이고, 값은 " + str);
    }

    void overL(int k){
        System.out.println("매개 변수 타입이 int 이고, 값은 " + k);
    }

    int overL(int x, int y){
        System.out.println("반환형이 다른 메서드");
        return x;
    }
}


public class HelloJava {
    public static void main(String[] args) {

        Hello ov = new Hello();

        ov.overL();
        ov.overL("오버로딩 예제");
        int num = ov.overL(5, 6);
        System.out.println(num);

    }
}

2. 오버라이딩(Overriding)

• 메서드 명, 매개 변수, 반환형, 접근 제어자가 모두 같다.
• 상속 받은 부모 클래스의 메서드를 재정의 하는 것이다. 다른 클래스의 메서드를 재정의 하는 것이 아니다!

class Animal {
    public void makeSound() {
        System.out.println("동물이 소리를 내고 있습니다.");
    }
}

class Dog extends Animal {
    @Override
    public void makeSound() {
        System.out.println("강아지가 멍멍 소리를 내고 있습니다.");
    }
}

public class HelloJava {
    public static void main(String[] args) {
        Animal animal = new Animal();
        Dog dog = new Dog();

        animal.makeSound(); // "동물이 소리를 내고 있습니다." 출력
        dog.makeSound();    // "강아지가 멍멍 소리를 내고 있습니다." 출력

    }
}

추상클래스란?

우선 첫 번쨰와 두 번째 정의를 살펴보자.

1. 추상 메소드와 완성된 메소드로 구성되어 있는 클래스.

2. 추상 메소드(Abstract Method)는 선언부만 존재하며, 구현부 {}는 존재하지 않는다.

초록색 네모 안에는 class 앞에 abstract를 사용하여 추상 클래스임을 확인할 수 있다.

빨간색 네모 안에 있는 abstract void move(int x, int y);는 여타 메소드와는 다르게 구현부 {}, 중괄호로 되어 있는 부분이 없다. 이런 메소드를 추상 메소드라고 불리며, 껍데기만 있다고 표현할 수 있다.

검은 네모 안에 있는 메소드는 흔히 볼 수 있는 메소드이다. 선언부에 void stop()이 있고, 구현부에는 값을 출력하는 것을 보이고 있다.

이처럼 추상 클래스는 클래스 내에 추상 메소드, 일반 메소드가 모두 존재할 수 있다. 하지만, 인터페이스는 무조건 추상 메소드만 있어야 한다는 것이 추상 클래스와의 차이점이다.

3. 만약 main 함수에서 추상 클래스 자료형의 객체를 생성하려면, 상속 클래스를 통해 추상 메소드를 구현(구현부를 작성)을 해야 한다.

abstract class Unit {       // 추상 클래스에는 일반 메서드도 포함. 인터페이스는 무조건 추상메서드
    int x, y;
    abstract void move(int x, int y);
    void stop() {/* 현재 위치에 정지 */}
}

class Marine extends Unit {
    void move(int x, int y){
        System.out.println("Marine[ x = " + x + ", y = " + y + "]");
    }
}

class Tank extends Unit {
    void move(int x, int y){
        System.out.println("Tank[ x = " + x + ", y = " + y + "]");
    }
}   

class Dropship extends Unit {
    void move(int x, int y) {
        System.out.println("Dropship[ x = " + x + ", y = " + y + "]");
    }
}

public class Abstract3 {
    public static void main(String args[]){
//      Unit[] group = {new Marine(), new Dropship(), new Tank()}; 아래 세 줄을 한 줄로 줄인 것   // 추상 클래스 객체를 만드는 건 불가능. 왜냐면 추상 클래스에는 추상 메서드가 있을 수 있기 때문. 그래서 상속받은 클래스 형으로 객체를 생성해야 함.
        Unit[] group = new Unit[3];
        group[0] = new Marine();
        group[1] = new Dropship();
        group[2] = new Tank();
    
        group[0].move(100, 200);
        group[1].move(100, 200);
        group[2].move(100, 200);

    }
}

Unit 이라는 추상 클래스를 상속 받은 Marine, Tank, Dropship 클래스들은 추상 메서드인 abstract void move(int x, int y);를 구현(완성)하고 있는 것을 확인할 수 있다. 만약 Unit 추상 클래스를 상속받은 일반 클래스에서, move 메서드를 구현하지 않았다면 컴파일러에서 에러를 발견하여 빨간 줄이 뜨는 걸 볼 수 있다. 이렇게 추상 매서드를 구현해야 main에서 Unit 객체를 생성할 수 있다.

이렇듯, 여러 클래스에 공통적으로 사용될 수 있는 추상 클래스를 바로 작성하거나 기존 클래스의 공통 부분을 뽑아서 추상 클래스를 만들 수 있다.

(참고, Marine, Tank, Dropship 객체를 생성하되 참조변수는 Unit 으로 선언할 수 있다. 왜냐하면 상속 받았기 때문!

ex) Unit[] group = new Unit[3]; 

Unit[] group = new Marine[3];

Unit[] group = new Tank[3];

Unit[] group = new Dropship[3] ;

하지만 Marine 객체를 선언하면 Marine 클래스 내에 있는 메소드와 상속 받은 Unit 클래스 내에 있는 메소드만 사용 가능하다. 나머지도 동일!)

4. 추상 클래스를 상속받은 클래스는 추상 클래스에 있는 추상 메소드를 구현해줘야한다. 단, 상속 받은 클래스가 추상 클래스일 경우에는 모든 추상 메소드를 구현하지 않아도 된다.

이게 무슨 뜻인지 아래 코드를 보며 이해해보자.

추상 클래스 Unit에는 세 가지의 메서드가 있다.

abstact void move, abstract void fly, void stop.

<만약 main 함수에서 추상 클래스 자료형의 객체를 생성하려면, 상속 클래스를 통해 추상 메소드를 구현(구현부를 작성)을 해야 한다>라는 3번의 정의에 따르면,  현재 Marine 클래스에는 move 메서드는 구현했지만 fly 메서드는 구현하지 않았다. 그래서 빨간 줄이 나오는 것을 볼 수 있다. 

하지만, 여기서 Marine 클래스를 추상 클래스로 선언한다면, 굳이 모든 추상 메서드를 구현할 필요가 없어진다.

프로그래머스에서 문제를 풀다가 오름차순으로 정렬할 알고리즘이 있었다.

2중 for문에 익숙한 나는, 2중 for문으로만 하려고 했는데 알고리즘을 공부하기 위해선 다양한 방법을 시도해야 했다.

그래서 Arrays.sort() 메쏘드를 사용했다.

1. 2중 for문을 사용한 오름차순 정렬

import java.util.*;

public class HelloJava {
    public static void main(String args[]) {
        
        int[] a = new int[]{1,5,4,3,2};
        int k;

        for(int i = 0; i < a.length - 1; i++){
            for(int j = i + 1; j < a.length; j++){
                if(a[i] > a[j]){
                    k = a[i];
                    a[i] = a[j];
                    a[j] = k;       
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

2. Arrays.sort()를 사용하여 오름차순 정렬

import java.util.*;

public class HelloJava {
    public static void main(String args[]) {
        
        int[] a = new int[]{1,5,4,3,2};
        
       	Arrays.sort(a);
        
        System.out.println(Arrays.toString(a));
    }
}

여기서 만약에

System.out.println(a);

로 값을 출력한다면 [I@24d46ca6 와 같은 배열 a의 주소값이 나올 것이다.

배열은 참조변수이므로, 배열의 원소값을 나타내기 위해서는 toString 메소드를 사용한다면 파라미터를 통해 원소 값을 문자열로 변환 후, 원소를 출력할 수 있다.

적용 알고리즘 : 1~6 사이의 수 중에서 나올 수를 예측하고, 실제로 나온 수와 비교하는 것이다.

간단하게 해결!!

//주사위 값 예측하기

import java.util.*;

class DiceGame {    // DiceGame 클래스를 생성
    
    int diceFace;
    int userGuess;

    private void RollDice() {
        diceFace = (int)(Math.random() * 6) + 1;
    }

    private int getUserInput(String prompt) {
        System.out.println(prompt);
        Scanner s = new Scanner(System.in);
        return s.nextInt();
    }

    private void checkUserGuess() {
        if (diceFace == userGuess){
            
            System.out.println("주사위 값은 " + diceFace + "이고,");
            System.out.println("내가 예측한 값은 " + userGuess + "이다.");
            System.out.println("예측 값이 맞았다!!");
        }
        else{
            System.out.println("주사위 값은 " + diceFace + "이고,");
            System.out.println("내가 예측한 값은 " + userGuess + "이다.");
            System.out.println("예측 값이 틀렸다!!");
        }
    }

    public void startPlaying() {
        userGuess = getUserInput("예상값을 입력하시오.");       //getUserInput
        RollDice();     //RollDice 메써드 실행
        checkUserGuess();       //checkUserGuess 메써드 실행
    }
}

public class DiceGameTest {
    public static void main(String[] args) {
        DiceGame game = new DiceGame();     //DiceGame 객체 생성
        game.startPlaying();
    }
}

# for문

for문은 C, Java, javascript 등등 절차지향, 객체지향, 스크립트 언어 모든 곳에서 자주 쓰인다. 오늘은 html, css, javascript를 이용해서 간단하게 구구단을 화면에 출력해보자.

<HTML, javascript>

<!DOCTYPE html>
<html lang="ko">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>구구단 - for문</title>
	<link rel="stylesheet" href="css/gugudan-table.css">  <!-- 아래 css파일이 위치한 경로를 지정-->
<body>
	<h1>구구단</h1>
	<script>
		var i, j;

		for (i = 1; i <= 9; i++) {
			document.write("<table>");
			document.write("<tr><th>" + i + "단</th></tr>");
			for (j = 1; j <= 9; j++) {
				document.write("<tr><td>" + i +" X " + j + " = " + i*j + "</td></tr>");
			}
			document.write("</table>");
		}
	</script>
</body>
</html>

구구단 알고리즘은 이중for문을 사용하여 간단하게 구현할 수 있다. 그리고 나머지는, 입맛에 맞게 꾸미면 된다!

<CSS>

div{
    display: inline-block;
    padding: 0 20px 30px 20px;
    margin: 15px;
    border: 1px solid #ccc;
    line-height: 2;
}

div h3 {
    text-align: center;
    font-weight: bold;
}

위 코드는, Do it html/css, javascript의 책을 인용했습니다!

Javascript뿐만 아니라, if와 switch 제어문은 다른 언어를 공부할 때도 항상 배우는 요소이다. 각 제어문은 기능은 비슷하나, 장단점을 지니고 있다. switch는 case를 나눠서 하기 때문에 '정확하고, case가 적은 경우'에 효율적이다. if문은 '좀 더 큰 범위의 case(?)'에 장점을 지닌다. 

운영체제 측면에서 if와 switch를 비교하면, switch문을 사용했을 때 cpu가 명령을 수행하기 위해 메모리에 접근하는 횟수가 현저히 적다. 왜냐하면, if문을 사용했을 때는 if문을 만날 때마다 cpu가 메모리에 접근하지만, switch는 한번만 접근하면 여러 case에 값을 비교할 수 있기 때문이다.

#switch문

switch문은 하나 이상의 case와 break, default로 이루어져있다. 코드 예시를 보면 쉽게 이해가 될 것이다.

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title>Javascript 배우기</title>
    </head>
    <body>
        <h1>Javascript</h1>
        <script>
            var session = prompt("숫자를 선택하세요");

            switch(session) {
                case "1" : 
                document.write("숫자 1을 입력했습니다.");
                alert("1");
                break;

                case "2" : 
                document.write("숫자 2를 입력했습니다.")
                alert("2");
                break;

                case 3 : 
                document.write("숫자 3을 입력했습니다.")
                alert(3);
                break;

                default : alert("숫자를 잘못 입력하셨습니다.");
            }

        </script>
    </body>
</html>

중요한 것은 switch문의 case에는 항상 break가 있어야 한다는 것..!

# if문

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">

    <title>Document</title>
</head>
<body>
    <h1>Javascript 연습하기</h1>
    <script>
        var memNum = prompt("입장하는 관객의 수를 입력하세요.");
        var colNum = prompt("한 줄에 몇 명씩 앉을지 입력하세요.");
        var rowNum;

        if(memNum % colNum === 0){
            rowNum = memNum / colNum;
            document.write("총 " + colNum + "명씩 "+ rowNum + "줄로 앉으면 됩니다.");
        }

        else{
            rowNum = (memNum % colNum) + 1;
            document.write("총 " + colNum + "명씩 "+ rowNum + "줄로 앉으면 됩니다.");
        }
    </script>
</body>
</html>

# prompt와 parseInt, parsedouble 등등..

프롬프트(prompt)란 사용자에게 창을 띄워서 데이터를 받아올 수 있는 함수이다. 

위 switch문 예제를 실행하면 이렇게 나올텐데, 이것이 바로 prompt이다. alert과 비슷하게 생겼지만, alert은 사용자에게 말 그대로 값을 보여주는 주의와 같은 개념이기에 데이터를 받아오지는 못한다.

prompt는 데이터를 받으면 자동으로 문자열로 변환한다.

그렇기 때문에, parseInt()로 감싸주면, 프롬프트창으로 받은 데이터가 정수형으로 저장된다.

마찬가지로, parsedouble(), parsefloat()으로 감싸주면 실수형으로 데이터가 저장된다.

위의 switch예제에서 숫자 3을 입력한다면, 어떤 뜻인지 이해가 빠를 것이다.

--<백준 2562번 :: 최댓값 - JAVA>--

이문제도 굉장히 쉬운 문제이다. 배열과 배열의 인덱스만 이해한다면 1분조차 안걸려서 풀 수 있다.

그러나... 처음 알고리즘을 공부하거나 배열에 익숙하지 않는다면 조금 힘들 수 있다!! 

괜찮다. 지금부터 배우면 되니까.

나도 완벽하지 않은데 누굴 가르치겠냐만은... 같이 공부하는 느낌으로 해보는 거다!

1. 배열을 사용하면 쉽게 해결!

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        
        Scanner input = new Scanner(System.in);

        int[] array = new int[9];
        int max = 0;
        int index = 0;;

        for(int i = 0; i < array.length; i++){
            array[i] = input.nextInt();
            if(array[i] > max){
                max = array[i];
                index = i;
            }    
        }

        System.out.println(max);
        System.out.println(index + 1);
    }
}

여기서 마지막에 index + 1을 출력한 이유는, 배열의 번호는 0번부터 시작하기 때문이다.

문제의 출력 값을 보면 8번째의 수는 '8'번째의 위치에 있다고 했다. 만약 index를 그대로 출력했다면 7이 나왔을 것이다.

알고리즘 공부하는 모두들 화이팅!

--<백준 1157번 :: 단어 공부 - JAVA>--

알고리즘 공부를 조금씩 하다 보니 생긴 요령이 있습니다. 영어를 앞으로 밀거나, 비교하거나, 바꾸는 경우 항상 '아스키코드'를 사용하는 것이 편리하다는 것이죠! 이번 문제도 아스키코드를 사용하여 간단하게 풀어보았습니다. 

어려운 부분은 없으니 천천히 따라오시면 됩니다!

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int[] arr = new int[26];
		String s = input.next();
		
		for(int i = 0; i < s.length(); i++) {
			
			if(65 <= s.charAt(i) && s.charAt(i) <= 90) { // 대문자인 경우
				arr[s.charAt(i)-65]++;
			}
			else { // 소문자
				arr[s.charAt(i)-97]++;
			}
		}
		
		int max = -1;
		char ch = '?';
		
		for(int j = 0; j < 26; j++) {
			if(max < arr[j]) {
				max = arr[j];
				ch = (char)(j + 65);
			}
			else if(max == arr[j]) {
				ch = '?';
			}
		}
		
		System.out.print(ch);
	}
}

아스키코드를 참고해서 만들었습니다. 그런데 만들고보니, 다른 분과 완전 똑같게 했더라구요...

마 쉬운 문제라서 겹치는 답이지 않을까 싶습니다!!

알고리즘 공부하시는 분들 모두 화이팅~~

--<백준 1152번 :: 단어의 개수 - JAVA>--

총 두 가지 방법으로 풀었습니다.

1. StringTokenizer를 사용하는 방법

2. charAt을 사용하는 방법

다른 블로그를 보니까 대부분 StringTokenizer를 사용하셨더라고요! 당연히 StringTokenizer 클래스가 간단하죠. 그러나 알고리즘에 대해 아직까지는 노가다가 더 편한 저는... charAt으로도 해봤습니다. 막상 풀어보니 메모리와 시간은 비슷하더라고요! 위에가 charAt, 아래가 StringToknizer 입니다!

천천히 파헤쳐보겠습니다~

1. StringTokenizer를 활용한 자바 코드

import java.util.StringTokenizer;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner str = new Scanner(System.in);
		
		String s = str.nextLine();
		str.close();
		
		StringTokenizer st = new StringTokenizer(s, " ");
		
		System.out.println(st.countTokens());
	}
}

완전 간단하죠~? StringTokenizer가 띄어쓰기를 기준으로 단어를 분류하고, 그 분류된 단어들을 토큰이라고 합니다.

그 토큰의 개수만 출력해주면 바로 해결!

이번엔 charAt을 사용한 방법을 보여드리겠습니다.

2. charAt을 사용한 방법

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        
        Scanner input = new Scanner(System.in);
        String str;
        int cnt = 0;

        str = input.nextLine();

        for(int j = 0; j < str.length(); j ++){	//우선 공백의 개수를 먼저 세아린다
            if(str.charAt(j) == ' '){
                cnt++;
            }
        }

        if(str.charAt(0) != ' ' && str.charAt(str.length()-1) != ' '){ //첫 번째와 마지막이 공백이 아닌 경우
            cnt = cnt + 1; 
        }
        if(str.charAt(0) == ' ' && str.charAt(str.length()-1) == ' '){ //첫 번째와 마지막이 공백인 경우
            cnt = cnt - 1;
        }
        System.out.println(cnt);
        
    }
}

어떤 알고리즘인지 감이 오시나요??

아래 그림처럼 이해하면 쉽습니다!

우선 for문을 사용하여 공백의 개수를 cnt에 입력합니다.

그리고 

case1. 가장 첫 번째와 마지막이 공백이 아닌 경우 -> cnt = cnt + 1

case2. 가장 첫 번째와 마지막 중에서 하나만 공백인 경우 -> cnt 변화 없음

case3. 가장 첫 번째와 마지막이 모두 공백인 경우 -> cnt = cnt - 1

이렇게 예를 들어서 하면 쉽게 이해가 됩니다!

아직은 어려운 알고리즘은 아니어서 이렇게 노가다로 풀지만.... 코딩테스트나 프로그래머스에 나오는 문제들은 노가다로는 절대 안 풀리더라고요.. 하하  

코딩러들 다들 화이팅~!