Slow but steady wins the race

알고리즘 효율성을 측정하는 가장 기본적인 방법은 시간과 메모리를 측정하는 것이다. 

파이썬에서는 해당 작업이 가능한데,,

수행시간 측정

import time

#측정 시작
start_time = time.time()

# 코드

#측정 종료
end_time = time.time()

#출력
print("time :", end_time-start_time)

예시

from random import randint
import time


array = []
for _ in range(10000):
    array.append(randint(1, 100))

start_time = time.time()
# 기본정렬 라이브러리
array.sort()
end_time = time.time()

print("기본 정렬 라이브러리 성능 측정 :", end_time - start_time)

array = []
for _ in range(10000):
    array.append(randint(1, 100))

start_time = time.time()
# 선택 정렬
for i in range(len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

end_time = time.time()

print("선택 정렬 성능 측정 :", end_time - start_time)

참고 : 이것이 코딩테스트다 - 동빈 나 

메서드란?

메서드란?

코드의 중복을 제거하기 위해서 { 해당 문자들 }을 묶은 것으로, 값을 입력받아 결과를 출력(반환)한다. 

※ 메서드 vs 함수

메서드의 장점?

- 중복 코드 제거

- 관리 용이

- 재사용 가능 

참고로, 하나의 메서드는 하나의 기능만 수행하도록 작성해야 함

메서드 = 선언부 + 구현부

반환타입 메서드이름 (타입 변수명, 타입변수명, ...) // 선언부
{												// 구현부
	//코드			  							// 구현부
}												// 구현부

int add(int x,int y){
	int res = x+y;
    return res;
}

메서드 호출

메서드 이름(값1, 값2, ...);

위의 형식과 같이 메서드를 호출하는데, return type에 따라 작업 결과를 저장해야 할 경우는 주의해야 함!

→ 예시코드

public static void main(String[] args){
	MyMath mm = new MyMath();
    
    //add 메서드 호출
    long res1 = mm.add(5L,3L);
    double res2 = mm.add(5L,3L);
    
    System.out.println("res1 : "+ res1);
    System.out.println("res2 : "+res2);
}

class MyMath{
	long add(long a, long b){
    	long res = a+b;
        return res;
   }
   
   long substract(long a, long b){ return a-b}
   
   //...
}

★ 메서드는 클래스 영역에만 정의를 저장

메서드의 실행 흐름

1. 객체 생성(인스턴스 생성)

2. 메서드 호출- 메서드의 매개변수에 인수가 각각 대입됨

3. 메서드의 모든 문장이 끝나거나 return을 만나면 반환

return문

return문이란? 

실행 중인 메서드를 종료하고 호출한 곳으로 되돌아가도록 한다. 

return;
return a;

반환 타입이 void일 경우 생략 가능, 컴파일러가 자동 추가됨

반환 타입이 void가 아닐 경우, 반드시 return문 필요

참고로, 다음의 경우에 "return문이 없다"는 에러가 발생한다. 

int max(int a,int b){
	if(a>b) return a;
}

Why? 참일경우엔 a를 반환하지만, 거짓일 경우에 어떤 값을 반환해야하는지 없기 때문! 

반환값

말 그대로 return되는 값으로, void type이 아닐 때, return 옆에 쓰는 것

반환 type과 반환값의 type이 일치해야 함

1. 문제

2. 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        HashMap<String,Integer> hm = new HashMap<>();
        String answer = "";
        
        for(String player : participant) 
            hm.put(player,hm.getOrDefault(player,0)+1);
        
        for(String player : completion) 
            hm.put(player,hm.get(player)-1);
        
        for(String key : hm.keySet())
            if(hm.get(key)!=0){
                answer = key;
                System.out.println(answer);
            }
        return answer;
    }
}

코드 긁고 싶은신 분들은 깃허브 참고

https://github.com/bosunKwak/Algorithm/blob/087df76cba0e8df56f8911237cda73c7f107eae0/hash/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0%EC%88%98.java

3. 풀이

자료구조 알고리즘 "해시"를 이용해서 풀면 훨씬 효율적인 코드를 짤 수 있다. 

해시에 관한 개념적인 설명은 다음 링크를 참고하면 된다. -> "작성중ㅎㅎ" 

처음엔 해시가 아니라, 다른 방식으로 구현했었다.

-> Arrays 메소드를 이용하여 participant, completion 각각 오름차순으로 정렬하여 앞 index부터 차례로 비교하고 다르거나 없는 경우에, 해당 participant를 출력하는 방법을 사용하였다. 

But, 이 문제의 본질(?)은 "해시"를 이용해야한다는 것! 

(1) HashMap 생성하기

HashMap<String,Integer> hm = new HashMap<>();

HashMap이란, Key-Value를 관리하는 클래스라고 할 수 있는데, <String, Integer>로 지정하면, Key는 String형, Value는 Integer형으로 정의한다는 뜻이다. 

(Key : Participant의 이름, Value : Count)로 사용

(2) HashMap에 Participant 추가 ( == 해싱(Hashing))

for(String player : participant) 
            hm.put(player,hm.getOrDefault(player,0)+1);

HashMap.put(Key,Value)함수는 HashMap에 Key와 Value를 한 쌍으로 입력하는 함수이고

HashMap.getOrDefault('a',0)함수는 'a'라는 Key에 해당하는 value가 존재하면 가져오고, 존재하지 않으면 0을 default로 지정하여 사용하겠다는 뜻의 함수이다. 

(3) HashMap에서 Complement 빼기 

for(String player : completion) 
            hm.put(player,hm.get(player)-1);

추가할 때와 동일하게 HashMap.put함수를 사용한다. 

HashMap에 존재한다면  Value가 1이상으로 표시되어있을 것이고 해당 Value를 1을 빼준다.  

(4) Value가 0이 아닌 Participant 찾아 출력

for(String key : hm.keySet())
            if(hm.get(key)!=0){
                answer = key;
                System.out.println(answer);
            }

HashMap을 돌면서 Value가 0이 아닌 Participant를 찾는다. 

HashMap.keySet()함수는 HashMap의 전체 Key의 배열을 반환하는 함수이고, 

HashMap.get(key)함수는 Key에 해당하는 Value를 반환하는 함수이다. 

4. 링크

https://programmers.co.kr/learn/courses/30/lessons/42576

선언 위치에 따른 변수의 종류

선언 위치에 따라 종류가 3가지로 나뉜다. 

(1) iv  인스턴스 변수 (2) cv 클래스 변수(static, 공유 변수) (3) lv(지역 변수)

코드로 구분해 보면 다음과 같다. 

class Variables{
    int iv;	//인스턴스 변수
    static int cv;	//클래스 변수 
    
    void method(){
    	int lv =0; //지역 변수
    }
}

(1) iv(instance variable)

인스턴스가 생성되었을 때 생성

Time class가 있다고 가정할 때, "int hour; int min; int sec;" 이것들을 iv라 할 수 있음! 

언제 생성됨? 객체를 생성할 때, 만들어짐

객체는 iv를 묶어놓은것! 이라고 이해하면 쉽다. (엄밀히 얘기하면 틀린 말이지만, 일차적인 이해를 위해서는 이렇게 생각하는 것이 좀 더 쉬울 것)

(2) cv(class variable)

클래스가 메모리에 올라갈 때 생성

클래스(설계도가)필요할 때 만들어짐 - 

(3) lv(local variable)

변수 선언문이 수행되었을 때 생성

영역은 크게 클래스 영역, 메소드 영역으로 나뉜다. 

클래스 영역에서 선언된 변수를 iv라 하고, static한 변수의 경우는 cv라 한다.

메소드 영역(클래스 영역 이외의 영역)에서 선언된 변수를 lv라 한다. 

♣ 클래스 영역에서 선언되는 변수는 인스턴스 변수와 클래스 변수가 있는데 이 둘의 차이는 무엇일까?

객체의 속성 중 개별적인 속성을 갖는 변수는 인스턴스 변수!

객체의 속성 중 공통적인 속성을 갖는 변수는 클래스 변수! static을 붙임

카드로 예시들면 조금 쉽다. 

class Card{

	//개별적인 속성
	String kind; //무늬
    int number; //숫자
    
    //공통적인 속성
    static int width = 100; //폭
    static int height = 250; //높이
}

해당 클래스를 사용하려면 다음과 같이 쓸 수 있다. 

Card c = new Card(); //객체 생성
//객체의 사용
c.kind = "HEART";	
c.number = 5;

Card.width =200;
Card.height=300;

클래스 변수를 사용할 때, 참조변수(c.width, c.height)로 써도 되지만, 권장하지 않음 

클래스의 정의

클래스의 정의는 크게 3가지로 나눌 수 있다. 

(1) 설계도 (2) 데이터 +함수 (3) 사용자 정의 타입

(1) 설계도

말그대로 설계도.. "https://bskwak.tistory.com/219" 참고 

)2) 클래스 == 데이터 + 함수

※ 배열 vs 구조체 

구조체에서 좀 더 발전(?)된 형태가 클래스라 할 수 있음

클래스 == 구조체(다양한 type 변수) + 함수(메서드) 

(3) 사용자 정의 타입

원하는 타입을 새로 만듦 - 예를 들면 시간 같은거? 

/*1*/
int hour;
int min;
int sec;

/*2*/
int hour1, hour2, hour3;
int min1, min2, min3;
int sec1, sec2, sec3;

/*3*/
int[] hour = new int[3]; 
int[] min = new int[3];
int[] sec = new int[3];

class 로 시간에 대한 "hour, minute, second"를 하나로 묶어서 코드를 써보면 다음과 같다. 

class Time{
	int hour;
    int minute;
    int second;
}

/*1*/
Time t = new Time();

/*2*/
Time t1 = new Time();
Time t2 = new Time();
Time t3 = new Time();

/*3*/
Time[] t = new Time[3];
t[0] = new Time();
t[1] = new Time();
t[2] = new Time();

코드가 훨~씬 간결해지고 시분초가 하나로 묶이기 때문에 이전 코드처럼 따로 분리되는 현상이 사라짐 

이전 코드 : 비 객체 지향 코드 

이후 코드 : 객체 지향적 코드 (관련된 값들을 묶을 수 있고 간결해짐)

하는 일의 차이는 없지만, JAVA와 같은 객체 지향 언어에서는 이후 코드가 적합

객체의 생성과 사용

1. 클래스 작성

설계도 작성이라 생각하면 쉽다. 

class Tv{
	//3개의 변수
	String color;
	boolean power;
    int channel;
    
    //3개의 매서드
    void power(){
    	power = !power;
    }
    void channelUp(){
    	channel++;
   	}
    void channelDown(){
    	channel--;
    }
}

위의 클래스는 변수 3개, 매서드 3개로, 총 6개의 멤버를 가지고 있다.

2. 객체의 생성

클래스명 변수명;  : 클래스의 객체를 참조하기 위한 참조 변수 선언
변수명 = new 클래스명(); : 클래스의 객체를 생성 후, 객체의 주소를 참조변수에 저장

Tv t; //Tv 클래스 타입의 참조변수 t 선언 
t = new Tv(); //Tv 인스턴스 생성 후, 생성된 Tv인스턴스의 주소를 t에 저장

다음과 같이 한줄로 줄일 수 있다. 

Tv t = new Tv();

3. 객체의 사용

객체가 가지고 있는 변수와 메소드를 사용한다는 뜻

t.channel = 7;	//변수 사용
t.channelDown(); //메서드 사용

4. main에서 사용 방법 

class Tvexample{
	public static void main(String[] args){
    		Tv t = new Tv();
        	t.channel = 7;
        	t.channelDown();
       	 	System.out.println("현재 채널은 "+ t.channel+" 입니다.");
    	}
}

5. 객체 배열

객체배열 == 참조변수 배열

아래 코드와 같이 객체 배열 생성과 각각 객체 생성하는 것은 다르다는 것 주의 

Tv[] tvArr = new Tv[3]; //객체 배열 생성

//객체 생성
tvArr[0] = new Tv();
tvArr[1] = new Tv();
tvArr[2] = new Tv();

1. 문제

문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다.

2. 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			
			for(int i=0;i<n;i++) {

				int num = sc.nextInt();
				String str = sc.next();

				for(int j=0;j<str.length();j++) {
					for(int k=0;k<num;k++) {
						System.out.print(str.charAt(j));
					}
				}
				System.out.println();			
			}		
			sc.close();		
	}

}

3. 풀이

처음엔 엄청 복잡하게 생각했었는데, 자바 메소드를 이용하면 별거 아닌 문제였다. 내 고민은 크게 두가지였다.

(1) "3 ABC" 와 같이 반복할 횟수와 문자열을 어떻게 입력받고 분리할지? 

(2) "ABC" 문자열의 각 원소"A","B","C"를 어떻게 뽑아낼까,, split을 이용해서 분리를 해야되나..?

이것 저것 방법을 찾아보니 해결방법은 별거 아니었다

(1) 각각 따로 입력받으면 된다. 한 줄씩 입력받지 않고 scanner.nextInt()와 scanner.next()를 이용해서 따로 입력받으면 된다. 한 줄! 이라는 생각을 버리면 된다.

대신 유의할 점은 nextLine()으로 입력받으면 안된다! 입력과정에서 엔터값을 입력받을 때까지 공백을 포함해서 한줄을 읽어버린다.

처음에 생각한 방식은 nextLine()을 이용해서 split(" ")을 통해 나눌 생각이었지만, 더 편한 방법이 있기에 취소

(2) charAt을 이용해서 문자 뽑기

String변수.charAt(index)를 이용하면 index에 해당하는 문자를 뽑을 수 있다

4. 링크

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