고구마의 코딩일기

프로그래머스 Level 3 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164?language=java

[접근방식 (틀림)]

문제에 대한 이해가 부족에 초기 접근이 잘못되었던 것 같다

- 모든 경로를 순회해야하는 문제로 dfs/bfs 를 적용하면 될 것으로 판단

- ArrayList인 graph와 visited 배열에 인덱스 접근을 하기 위해 맵(Map)을 사용해 공항(key) - 값(value)를 할당

- 이후 bfs에서 PriorityQueue를 활용해 공항 중 사전순이 가장 빠른 것을 뽑아 순회

결과

주어진 티켓을 모두 사용해야한다는 조건이 있어 갔던 공항도 다시 가야하는 경우가 발생

원하는 결과값이 나올 수 없었음

또한 쓸데없이 너무 많은 자료구조를 사용한 것 같아 비효율적이었던 것 같다...

더 생각을 해서 접근!

[풀이]

2시간 가량 고민한 결과 다른 사람들의 코드를 참고하기로 결정

- backtracking 방식을 사용하면서 순회
- 아직 사용하지 않은 티켓이고, 현재 공항이 출발지인 티켓인 경우 현재까지 경로(route) + " " + 도착지 형태로 추가

- 순회하면서 모든 티켓이 사용된 경우(cnt == tickets.length) 이 때의 경로(route)를 routes에 저장
- 가능한 모든 경로를 찾은 후 저장되어있던 routes 리스트를 정렬해 사전순으로 가장 빠른 경로를 찾는다

import java.util.*;

class Solution {

    ArrayList<String> routes;
    boolean[] visited;

    public void backtracking(String cur, int cnt, String route, String[][] tickets){
        if(cnt == tickets.length){
            routes.add(route);
            return;
        }
        for(int i=0;i<tickets.length; i++){
            if(visited[i]==false && tickets[i][0].equals(cur)){
                visited[i]=true;
                backtracking(tickets[i][1], cnt+1, route+ " " + tickets[i][1], tickets);
                visited[i]=false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        routes = new ArrayList<>();
        visited = new boolean[tickets.length]; //티켓 사용 여부

        backtracking("ICN",0,"ICN", tickets);
        Collections.sort(routes);
        String[] ret = routes.get(0).split(" ");
        return ret;
    }
}

[배운점]

정렬이 가장 빠른 순서를 찾는 경우 문자열로 계속 담아가면서 마지막에 정렬한번으로 해당 결과들을 정렬한 후

0번 인덱스의 값을 반환하는 방식을 배울 수 있었다.

백트래킹의 기본 원리

- 어떤 노드의 유망성(가능성)을 검증한 후,

  유망한 노드인 경우 해당 노드를 탐색, 유망하지 않은 경우 해당 노드를 배제하고 다른 자손을 탐색

- 유망하지 않은 노드를 배제하기 때문에 풀이 시간이 단축된다.

자바 I/O 패키지

- 자바의 I/O는 "Byte" 단위의 입출력과 "Char" 단위의 입출력이 존재

- Byte 단위의 입출력 클래스 모두 InputStream과 OutputStream 추상 클래스를 상속받아 만들어짐

- Char 단위의 입출력 클래스 모두 Reader와 Writer 추상 클래스를 상속받아 만들어짐

- 자바 I/O 패키지는 "데코레이터 패턴(Decorator pattern)"의 디자인 패턴으로 만들어짐 

※데코레이터 패턴

하나의 클래스를 장식하는 것처럼 생성자에서 감싸서 새로운 기능을 계속 추가할 수 있도록 클래스를 만드는 방식

Byte 입출력

- 운영체제는 1Byte씩 읽어오라는 명령을 하는 경우에도 보통 512Byte씩 읽어와 511Byte를 버리는 방식으로 읽기때문에

  파일을 읽는 경우 512의 배수 크기로 읽는 것이 보다 효율적!!

어노테이션

- JDK 5 버전 이후부터 추가된 기능

- 클래스나 메소드 위에 붙여서 사용 ex) @Override

- 소스코드에 메타데이터(추가정보)를 주는 것

- 사용자 정의 가능

어노테이션을 정의할 때 JVM실행 시 감지하기 위해서는

@Retention(RetentionPolicy.RUNTIME)

을 붙여줘야 한다.

쓰레드(Thread)

- 자바에서 thread를 생성하는 방법

  1. java.lang패키지의 Thread를 상속받는 방법

  2. Runnable 인터페이스를 구현하는 방법

Thread 상속 방식

- java.lang 패키지의 Thread 객체를 상속

- Thread 클래스의 run() 메소드를 오버라이딩하여 쓰레딩하고자하는 동작을 작성한다.

- 쓰레드를 수행시키기 위해서는 run()이 아닌 start()를 사용해 시작

  start()를 통해 쓰레드를 수행할 준비를 하고 준비가 된 후 내부적으로 run()을 수행시킴

Runnable 인터페이스 구현

- Java는 다중상속이 불가하기 때문에 이미 다른 클래스를 상속받은 경우 Thread 상속 방식 사용 불가

  이런 경우, Runnable 인터페이스 방식을 활용해 쓰레딩을 구현할 수 있다.

- Thread 상속 방식과 마찬가지로 run() 을 구현하면 된다

- Runnable로 작성된 쓰레드의 경우 start() 메소드가 없어 수행 시 Thread 객체를 생성해 Runnable 객체를 주입

  후에 start()를 통해 수행시키면 된다!

쓰레드 동기화(Synchronization)

- 공유자원(객체)을 순서대로 작업이 이루어지도록 처리하는 방법

  (과도한 동기화는 전체 프로그램 성능의 저하를 만든다!)

- 프로세스 내 자원을 여러 쓰레드가 공유하면서 작업할 때 문제 발생을 방지

- 가장 먼저 실행된 쓰레드가 끝난 후 다른 쓰레드가 수행되게끔 함 ==> 모니터링 락

동기화 방식

1. 메소드의 반환 타입 앞에 synchronized 를 붙여준다.

  - 메소드 전체에 동기화가 걸려 메소드 전체가 수행되는 것을 기다리기 때문에 비효율이 있음

2. 동기화가 필요한 부분만 sychronized(this){} 블록으로 만든다.

(쓰레드는 한 번 공부한다고 잘 모르겠다... 복습이 필요!!)

람다식

- JDK 8 버전 이후 추가된 기능

- Java에는 메소드를 인자로 넘길 수 없고 반드시 객체로 만들어 넘겨야 하는데 이를 극복하기 위해 등장!

- 다른 말로 "익명 메소드" 라고 함

- (매개변수 목록) -> {실행문} 와 같은 식으로 사용. 타입을 보고 JVM이 예측한다!

- 람다식을 사용하면 더 간결한 코드를 만들 수 있다!

이로써 프로그래머스 자바 입문, 중급 강의를 통해 복습이 끝났다

앞으로의 공부계획은 다음 TIL에 작성하겠습니다

프로그래머스 자바 입문 과정을 어제(2021-07-28)로 복습을 마쳤다

기존에 알고 있던 내용이지만 다시 한번 들음으로 정리해볼 수 있는 좋은 기회였다

오늘부터는 프로그래머스의 자바 중급 과정을 들으며 TIL 작성 시작!

https://programmers.co.kr/learn/courses/9

Object 클래스

- 모든 클래스의 최상위 클래스

자주 사용되는 Object 의 메소드. (사용 시 반드시 오버라이딩 필요!)

- equals() : 객체가 가진 값을 비교할 때 사용. 즉 내용을 비교한다!

               (비교에 대한 기준을 작성하기 위해 오버라이딩 필요)

               객체가 같은 객체를 참조하고 있는 지를 비교하는 것은 "==" 연산자로 가능!

- toString() : 객체가 가진 값을 문자열로 변환

- hashCode() : 객체의 해시코드를 구하는 메소드

                   기본적으로 클래스에 정의되어있는 필드값들을 바탕으로 hashCode를 생성

Java.lang

- 오토박싱

Java.lang 패키지에는 기본 타입의 변수를 객체로 변환시키는 wrapper Class가 존재

int -> Integer

boolean -> Boolean 

등.. 객체로 변환을 위한 8개의 wrapper Class가 존재

이 때 wrapper Class인 Integer 에 바로 기본타입의 값을 넣어도 오류가 나지 않는다

Integer i1 = new Integer(5); 

Integer i2 = 5; (가능/ "오토박싱")

이는 기본 타입 데이터를 객체 타입의 데이터로 자동 형변환 시켜주는 "오토박싱" 기능이 있기 때문

(JDK 5 버전 이후부터 가능!!)

- 오토언박싱

오토박싱과 반대로 wrapper Class의 참조타입을 기본타입의 값으로 변환하는 경우 발생

Integer i1 = 5;

int i2 = i1.intValue();

int i3 = i1; (가능/ "오토언박싱")

StringBuffer 클래스

- 자기자신의 값을 계속 변경시키며 자신(this)을 계속 반환한다. => "메소드 체이닝"

StringBuffer sb1 = new StringBuffer();

StringBuffer sb2 = sb1.append("hello");

sb1 과 sb2는 같은 객체.

String일 경우 내용이 변경되면 새로운 객체를 생성해 변경된 내용을 저장하지만

StringBuffer의 경우 자기자신을 변경시키기 때문에 append를 수행해도 sb1이 변경!

※ 메소드 체이닝

  자기 자신을 리턴하여 계속해서 자신의 메소드를 호출하는 방식

따라서, 문자열의 내용 변경이 자주 발생하는 경우

String보다는 StringBuffer를 사용하는 것이 더 효율적인 코드를 작성할 수 있다.

==> String의 경우 내용변경이 발생하면 String 객체를 새로 생성해 비효율적!

Date 클래스

- java.util 패키지에 정의되어 있다

- JDK 1.0 버젼부터 정의된 클래스

- 지역화에 대한 고려를 하지 않은 클래스

  이런 단점을 극복하기 위해 생긴 클래스가 Calendar 클래스

- java.text 패키지의 SimpleDateFormat 클래스로 날짜 형식을 원하는 형식으로 변경할 수 있다.

  SimpleDateFormat ft = new SimpleDateFormat("yyyy.MM.dd hh:mm:ss");

  ft.format(Date);

Calendar 클래스

- java.util 패키지에 정의되어 있다

- JDK 1.1 버전 이후부터 사용 가능

- Date 클래스와 다르게 지역화가 고려되어 설계된 클래스

- Calendar.getInstance()로 Calendar 객체를 얻을 수 있음

String 클래스

- String 클래스는 한 번 만든 객체를 바꾸지 않는다 ==> "불변 클래스" 라고 함

String str = "hello";

String str2 = "hello";

현재 str과 str2는 같은 hello 객체를 참조하고 있다

str.concat(" world"); 를 하면 str2도 같은 객체를 참조하고 있어 문제가 발생!

이런 이유로 Java의 String 클래스는 한 번 만든 객체를 바꾸지 않도록 했다

따라서 str.concat(" world");를 수행하면 기존에 존재하던 "hello"는 그대로 두고 "hello wolrd"객체가 새로 생성

str의 참조값을 "hello world"로 하고 싶은 경우 str = str.concat(" world");로 해주어야 함

String.substring() - 문자열을 원하는 위치에서 원하는 크기만큼 자를 수 있음

substring(startIndex) - startIndex의 위치부터 끝까지 내용을 자름

substring(startIndex, endIndex) - startIndex의 위치부터 endIndex의 위치까지 내용을 자름

클래스 내에서의 static

- static 이 붙은 메소드와 필드(변수)는 클래스를 인스턴스화하지 않아도 사용 가능

- static 메소드 내에서는 static 필드(변수)와 static 메소드만 사용 가능

- 일반 메소드 내에서는 static 메소드와 필드(변수) 모두 사용 가능

static이 붙은 필드(변수)와 메소드는 클래스가 메모리에 올라갈 때 한 번 할당되어

프로그램이 종료될 때 해제되는 것으로, 메모리에 한 번 할당되어 여러 객체가 해당 메모리를 공유

열거형(enum)

열거형 내에 포함된 값 이외의 경우에 에러를 발생시킬 수 있어 유용

- 선언 

enum Gender{

    MALE, FEMALE;

}

- 사용  ==> Gender에 해당하는 값이 아니면 컴파일 시 에러 발생

Gender gender;

gender = Gender.MALE;

gender = Gender.FEMALE;

패키지(Package)

- 파일을 관리하기 위한 폴더

- package 이름은 대부분 도메인 이름을 거꾸로 적은 후 프로젝트 이름을 붙여 사용

 도메인: company.com -> 패키지 이름: com.company

- package가 있는 클래스를 사용할 경우 import 사용

상속

class childClass extends parentClass{

}

childClass가 parentClass를 상속받는다

접근제한자

public - 모든 접근을 허용

private - 자기 자신만 접근 가능

protected - 같은 패키지인 경우 접근 가능. 다른 패키지인 경우 상속 관계인 경우 접근 가능

default - 접근제한자를 아무 것도 붙이지 않은 경우.

            자기 자신과 같은 패키지 내에서 접근 허용

인터페이스(Interface)

- 클래스를 위한 명세서 개념

- Java8 버젼부터 추상클래스 뿐만 아니라 default와 static 메소드 구현 가능

  (default 메소드 구현 시 default 키워드를 붙여줘야 함!)

  (static 메소드의 경우 반드시 "인터페이스명.메소드명()" 로 사용해야 함!)

예외처리 - throw, thorws

- throws

자체적으로 예외를 처리하지 않고 호출하는 곳에 해당 예외를 넘겨주는 키워드

public void method() throws Exception1, Exception2 ...{

} 

- throw

예외를 강제적으로 발생시키는 키워드

(발생시키고자 하는 곳에서)

throw new Exception1("메시지 내용");

사용자 정의 Exception

public class 클래스이름 extends Exception {

       ...

}

클래스의 이름만으로 어떤 오류가 발생했는지 알려주어 코드의 직관성을 높이기 위해

사용자 정의 Exception을 사용한다

이 때 상속받는 예외가 Exception 이냐 RuntimeException 이냐에 따라 달라질 수 있다.

- Exception

반드시 오류를 처리해야 하며 예외처리를 하지 않을 시 컴파일 오류를 발생시키는 Checked Execption

-RuntimeException

예외처리를 하지 않아도 컴파일 시 오류 발생 X 인 Unchecked Exception

프로그래머스 데브코스 백엔드 과정에 탈락 ... ㅠㅠ

부족하다고 느껴 신청한 교육에서 부족하다고 탈락한 기분이다

하지만 좌절할 수 없으니 오늘부터라도 배운 것을 매일 작성하는 TIL 시작하면서 꾸준함으로 부족함을 메꿔야겠다

Java 언어에 대해 기초부터 복습하고자하는 의미에서 프로그래머스의 자바 입문 강의부터 가볍게 쌓아갈 예정이다

https://programmers.co.kr/learn/courses/5

JAVA의 특징

- 포인터와 다중 상속이 없어 "C와 C++에 비해" 쉽다

- 컴파일된 자바 코드(.class)가 JVM 위에서 동작해 플랫폼에 자유롭다

- 가비지 컬렉션(Garbage Collection)에 의해 메모리가 관리되어 불필요한 메모리 사용이 줄어든다

주석의 종류
(문서화 주석의 존재를 알게 되어 다시 한 번 정리해본다)

// - 한줄 주석

/*

 주석내용

*/  - 블록 주석

/*

* 주석내용

*/ - 문서화 주석

Java의 변수와 상수

변수 - 선언 후에도 내용 변경 가능

- int, String, double ....

변수 선언 시 변수명을 카멜케이스(CamelCase)로 작성하는 것이 관례

int a

int intValue  -> 카멜케이스

double d

String str

상수 - 선언 후 내용 변경이 불가한 변수. 선언 후 변경되면 안되는 것을 상수로 선언하면 좋음

기본 변수 선언에 final을 붙임.

상수 선언 시에는 상수명을 대문자로만 작성하는 것이 관례

final int A

final double D

final String STR

논리연산자

A && B - A와 B 가 같은 경우 True

A || B - A와 B 중 1개만 True여도 True, 둘다 False 일 때 False

!A - A의 부정. A가 True 면 False, False면 True

A ^ B (XOR) - A와 B의 결과가 달라야 True, 같으면 False

Scanner 클래스

어디론가부터 값을 입력받고 싶을 때 사용하는 클래스 

java.util 에 이미 정의되어 있는 클래스

Scanner sc = new Scanner(System.in); - System.in(키보드 입력)을 입력받는 scanner

자바의 변수 타입

- 기본형 타입

논리형 : boolean

문자형 : char

정수형 : byte, short, int, long

실수형 : float, double

- 참조형 타입

기본형 타입을 제외한 모든 타입(배열, 클래스 등)

String str = new String("hello");  ==> str은 "hello" String 객체를 참조한다

String str1 = "hello";

String str2 = "hello";  ==> str1과 str2는 같은 "hello" 문자열 상수를 참조한다

String str1 = new String("hello");

String str2 = new String("hello"); ==> new를 사용해서 생성하면
                                                  heap 영역에 "hello"가 들어간 문자열 객체를 각각 만든다

두 객체가 같은 객체인지를 알아볼 때는 "=="를 사용해 비교

두 객체의 내용이 같은 내용인지를 알아볼 때는 equals()메소드를 사용

List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트

- 일반적인 배열과 같이 순차리스트이며 인덱스로 내부의 객체를 관리한다는 점이 유사

- 크기가 선언 시 고정되는 배열과 달리 ArrayList 는 객체들이 추가되어 용량을 초과하면 자동으로 부족한 크기만큼
  저장 용량이 늘어난다

- 인덱스만 알고 있다면 시간복잡도 O(1)로 해당 원소에 접근 가능

- 원소를 삽입/삭제할 경우 해당 원소 뒤의 원소들의 이동이 발생해 시간복잡도 O(n)이 걸린다

ArrayList의 선언

ArrayList<Object> list = new ArrayList<>();

ArrayList 값 추가

- add(value) : value값을 ArrayList 제일 끝에 추가

ex)

list.add(3);

list.add(null); // null값도 가능

list.add(1,10); // 1번 인덱스 뒤에 10 삽입

* 중간에 값을 추가하는 경우 해당 인덱스부터 마지막 인덱스까지 모두 1씩 뒤로 밀려나간다

  이 경우 데이터가 늘어날수록 성능에 악영향을 미치기에 중간에 데이터를 insert하는 경우가 많다면

  ArrayList보다는 LinkedList를 사용하는 것도 좋은 방법

ArrayList 값 삭제

- remove(index) : 해당 index의 값 제거

- clear() : ArrayList의 모든 값 제거

ArrayList 크기 구하기

- size() : ArrayList의 크기를 반환

ArrayList 값 얻기

- get(index) : 해당 index의 값 반환

- Iterator를 사용한 ArrayList 조회

  Iterator의 선언 

  (Iterator는 인터페이스이다)

  Iterator iter = list.iterator();

  - hasNext() : 현재 Iterator에서 다음 값이 있는지 체크

  - next() : iterator의 다음 값을 조회 

ArrayList 값 검색

- contains(value) : 해당 value가 있는지 검색. 있으면 true, 없으면 false

- indexOf(value) : 해당 value의 인덱스값 반환. 있으면 인덱스 반환, 없으면 -1

시간복잡도

  삽입(put)과 검색(get) 모두 O(1)의 시간복잡도를 갖는다

HashMap의 선언

  HashMap<Key(Object), Value(Object)> hm = new HashMap<>();

HashMap의 데이터 삽입

(null값의 삽입이 허용)

  hm.put(key, value);

  ex)

  hm.put( "apple", 1 );

  hm.put( null, 10 );

  ...

HashMap의 데이터 검색

  (key값을 사용해 그에 따른 값을 찾아온다.)

  (HashMap안에 일치하는 Key값이 없으면 Null 반환)

  hm.get(key)

  ex)

  hm.get("apple") ==> 1

  keySet(), values()

  - keySet()

  HashMap 내의 모든 Key를 Set 객체 형태로 반환

  - values()

  HashMap 내의 모든 value를 Collection 객체 형태로 반환

 containsKey(), containsValue()

  - containsKey(key(object))

    HashMap 내에 해당 키가 존재하는지 확인, 존재하면 True, 없으면 False

  - containsValue(value)

    HashMap 내에 해당 값이 존재하는지 확인, 존재하면 True, 없으면 False

HashMap의 데이터 삭제

  hm.remove(key)

  삭제가 되면 value 리턴. 일치하는 Key값이 없으면 Null 반환

  hm.clear()

  HashMap 내의 모든 데이터 삭제

HashMap의 데이터 존재여부 확인

  hm.isEmpty()

  HashMap 가 비어있지 않다면 False, 비어있다면 True 반환

1. length

 - arrays(int[], double[], String[])

 - length는 배열의 길이를 알고자 할때 사용된다.

2. length()

 - String related Object(String, StringBuilder etc)

 - length()는 문자열(String)의 길이를 알고자 할때 사용된다.

3. size()

 - Collection Object(ArrayList, Set etc)

 - size()는 컬렉션프레임워크 타입의 길이를 알고자 할때 사용된다.