프로그래머스 : 게임 맵 최단거리 (Java) 문제 문제 확인하기 풀이 (1, 1) 위치에서 출발해서 우측 하단 좌표인 (n, m) 위치까지 몇번의 이동이 걸리는지 구하는 문제이다. BFS를 통해 문제를 해결할 수 있다. BFS에 대한 설명은 아래 링크에서 확인할 수 있다. BFS 확인하기 아래는 자바로 작성한 코드이다. class Solution { // 맵 세로 크기 private static int rowSize; // 맵 가로 크기 private static int colSize; // {x, y} 형식으로 큐에 삽입 private static Queue queue = new LinkedList(); public int solution(int[][] maps) { int answer = 0; ro..

프로그래머스 : 택배상자 (Java) 문제 문제 확인하기 풀이 문제의 핵심만 간단하게 요약해보겠다. 컨테이너 벨트를 통해 1번부터 n번까지 상자가 오름차순으로 전달되며 컨테이너 벨트의 맨 앞에 있는 상자만 내릴 수 있다. 주어진 순서 배열 order에 맞게 k번 상자를 트럭에 실어야 한다. order 배열의 인덱스가 순서이고 값은 상자의 번호이다. 현재 컨테이너 벨트의 맨 앞에있는 상자가 트럭에 실을 순서가 아니면 보조 벨트를 이용한다. 보조 벨트는 입구와 출구가 동일한 Stack 형태이다. 보조 벨트에 적재하거나, 보조 벨트에서 상자를 꺼내 트럭에 싣는다. 보조 벨트를 이용해도 order 순서대로 상자를 싣지 못하면 종료한다. 컨테이너 벨트를 통해 상자가 도착했을 때, 상자가 트럭에 실을 순서와 일치하..

프로그래머스 : 테이블 해시 함수 (Java) 문제 문제 확인하기 풀이 문제의 요구사항에 따라 알고리즘의 흐름을 작성해보자. 테이블(배열)을 정렬한다. col번째 컬럼을 기준으로 오름차순 정렬한다. 같은 값은 첫번째 컬럼인 기본키를 기준으로 내림차순 정렬한다. 각 튜플에 대해 아래 내용을 반복한다. 각 컬럼을 현재 튜플의 순서(i)로 나눈 나머지를 구한다. 나머지들의 합을 S_i로 구한다. 각 튜플의 순서를 i라고 할 때, row_begin

프로그래머스 : 전력망을 둘로 나누기 (Java) 문제 문제 확인하기 풀이 송전탑의 개수 n이 주어지고 송전탑끼리 이어진 전선들의 정보 wires가 주어진다. wires를 통해 이어진 전선들은 하나의 트리 형태를 이룬다고 한다. 따라서 전선들 중 하나를 끊으면 하나로 묶인 트리가 두 묶음으로 나누어진다. 문제에서 요구하는 것은 전선들 중 하나를 끊어 송전탑 묶음을 두 개로 나누었을 때, 양 묶음의 송전탑의 개수 차이가 최소가 되도록 하는 것이다. 먼저, 전선을 끊는다는 것은 전선들의 정보 wires 중 하나를 무시하는 것으로 볼 수 있다. wires를 이용해서 각 송전탑과 연결된 테이블을 만들 때, wires 중 하나를 건너뛰고 만들면 된다. 전선의 개수는 n-1개라고 했다. 여기서 n은 2 이상, 10..

프로그래머스 : 피로도 (Java) 문제 문제 확인하기 풀이 던전의 최대 개수는 8개이다. 던전의 개수가 최대, 즉, 8개일 때, 모든 던전을 탐험하는 경우의 수는 8!으로 40320개이다. 따라서 완전 탐색으로 정답을 찾을 수 있다. 완전 탐색을 위해 DFS를 이용하였다. 모든 경로를 탐색해보기 위해 DFS 메서드 내에서 반복문을 이용했다. 남은 피로도로 현재 던전을 탐험할 수 있다면 해당 던전을 탐험처리하고 다음 던전을 선택하도록 한다. 반복을 통해 가능한 모든 경로를 탐험한다. 문제에서 요구하는 것은 유저가 탐험할 수 있는 최대 던전의 수이다. DFS 메서드는 탐험 가능한 최대 던전의 수를 반환해야 한다. DFS 메서드가 현재 탐험 가능한 던전의 수를 반환하도록 하면, 가장 깊은 곳의 DFS 메서드..

프로그래머스 : 양궁대회 (Java) 문제 문제 확인하기 풀이 과녁은 0 ~ 10점까지 총 11가지의 점수가 있다. 이 11가지의 점수 중 획득할 수 있는 점수들의 조합은 2^11(2048)이므로, 우리는 완전 탐색을 통해 문제를 해결할 수 있다. 여기서 점수를 획득할지 안할지 기록하기 위해 비트마스킹 기법을 활용하였다. 획득 가능한 점수들의 조합을 반복문으로 돌면서 해당 점수를 얻을 때 사용한 화살 개수가 문제에서 주어진 화살 개수 n보다 작거나 같을 때에만 라이언이 획득한 점수와 어피치가 획득한 점수를 계산하도록 하였다. 현재 확인하고있는 점수들의 조합을 얻기 위해 n발의 화살보다 크다면 불가능한 경우의 수이기 때문이다. 현재 확인하고 있는 점수들의 조합이 라이언이 쏠 수 있는 경우의 수라면, 어피치..

프로토타입(Prototype) 패턴 개념 프로토타입 패턴은 생성할 객체들의 타입이 프로토타입(원형)인 인스턴스로부터 결정되도록 하며, 새 객체를 만들기 위해 인스턴스를 복제하는 인스턴스 생성과 관련된 디자인 패턴이다. 아래는 프로토타입 패턴을 클래스 다이어그램으로 표현한 것이다. Client 클래스는 Prototype 타입의 객체를 register() 메서드를 통해 등록해두고, create() 메서드를 통해 등록한 Prototype 타입의 객체를 생성하여 반환하는 역할을 한다. register() 메서드를 통해 등록된 객체는 Prototype 인터페이스의 구현체이다. Prototype 인터페이스에는 createCopy() 메서드가 있는데, 이는 해당 타입의 인스턴스를 복사(copy)하여 반환하는 메서드이..

Optional null은 값이 없음을 나타내는 참조이다. 자바에서 null 참조를 사용하면 다음과 같은 문제들이 발생한다. null 참조에 접근하여 사용하려고 하면 NullPointerException 예외가 발생한다. 자바에서 가장 흔히 발생하는 예외이다. NullPointerException 예외가 발생하지 않도록 인스턴스가 null인지 확인하는 코드를 추가해야 한다. 때문에 return 출구가 여러개 생기거나 중첩된 null 확인 코드가 생겨 가독성이 떨어지게 된다. null은 아무 의미도 표현하지 않기 때문에 값이 없음을 표현하기에는 적절하지 않다. null을 남발하면 어떤 의미로 사용되었는지 알 수 없다. Java 8은 이러한 null 관련 문제들을 해결하기 위해 java.util.Option..

Lambda 람다 표현식은 익명 클래스처럼 이름이 없는 함수이면서 메서드를 인수로 전달할 수 있다. 람다 표현식은 메서드와 달리 특정 클래스에 종속되지 않기 때문에 함수라고 부른다. 람다 표현식은 파라미터, 화살표, 바디로 구성된다. 람다 사용 방법 // 화살표 -> 는 람다의 파라미터 리스트와 바디를 구분한다. 화살표 좌측이 파라미터 리스트, 우측이 바디이다. (Integer i1, Integer i2) -> i1.compareTo(i2); 람다의 표현 방식은 표현식 스타일과 블록 스타일의 두가지로 볼 수 있다. 표현식 스타일에서는 return을 사용하지 않는다. 해당 표현식의 값을 람다의 반환값으로 사용한다. 해당 표현식의 결과가 void이면 람다의 반환 타입은 void가 된다. 블록 스타일을 사용하..

Stream 스트림이란 스트림(Stream)은 자바 8 API에 새로 추가된 기능으로 스트림을 이용하면 선언형으로 컬렉션 데이터를 처리할 수 있다. 선언형으로 처리한다는 말은 데이터를 처리하는 임시 구현 코드 대신 질의로 표현할 수 있다는 것을 말한다. 아래는 스트림의 정의이다. 스트림(Steam)이란 데이터 처리 연산을 지원하도록 소스에서 추출된 연속된 요소로 정의할 수 있다. 스트림은 컬렉션과 같이 특정 요소 형식으로 이루어진 연속된 값 집합의 인터페이스를 제공한다. 컬렉션은 자료구조로 요소의 저장 및 접근 연산이 주를 이루는 반면, 스트림은 표현 계산식이 주를 이룬다. 컬렉션의 주제는 데이터이고, 스트림의 주제는 계산인 것으로 볼 수 있다. 스트림은 컬렉션, 배열, IO 자원 등의 데이터를 제공하는..