마코

https://school.programmers.co.kr/learn/courses/30/lessons/72412

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

접근

• 2중 for문으로 query마다 info를 전부 순회하면 정확성은 통과하지만 O(n^2)으로 효율성 테스트에서 실패한다.
• info를 Map<개발언어 + 직군 + 경력 + 소울푸드, List<점수>>로 저장, 점수를 내림차순 정렬한다.
• 각 query를 key로 infoMap에서 List<점수> 를 조회, 내림차순 되어있기 때문에 query의 점수보다 낮은 첫 번째 인덱스가 합격한 사람의 숫자이다.
  • 각 query에서 -인 경우 모든 경우를 조회해야 하기 때문에 모든 대상을 탐색 대상에 추가한다. ex) if 개발언어 = '-' 인 경우 cpp, java, python을 모두 탐색 대상으로 지정한다.
  • query 점수보다 낮은 첫 번째 인덱스를 순차 탐색하면 효율성 테스트에서 시간 초과가 발생한다. 이를 해결하기 위해 이분 탐색을 이용했다.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/72412.%E2%80%85%EC%88%9C%EC%9C%84%E2%80%85%EA%B2%80%EC%83%89/%EC%88%9C%EC%9C%84%E2%80%85%EA%B2%80%EC%83%89.java

스웨거를 사용하면 다음과 같이 어노테이션만 사용해도 자동으로 api명세를 해줍니다

로컬에서 스웨거에 접속해 명세를 확인한 모습

정상적인 케이스의 응답 형태뿐만 아니라 예외 관련 응답도 명세할 필요가 있었습니다.

스웨거에서는 `@ApiResponse`를 통해 다음과 같이 명세를 생성할 수 있었습니다.

하지만 위와 같은 방식은 2가지 문제가 존재합니다.

1. 실제 비즈니스 로직은 노란색 박스로 매우 적은데도 불구하고 명세와 관련한 코드가 훨씬 많은 비중을 차지합니다.

2. 로그인과 관련한 에러는 여러 api에서 공통으로 쓰일 것입니다. 만약 응답의 형태가 바뀐다면 전부 바꿔주어야 겠죠...?

이러한 문제를 해결하고자 커스텀 어노테이션을 만들어서, 여기에 예외 클래스를 인자로 전달하는 방식을 생각했습니다.

먼저, SwaggerExceptionResponse라는 스웨거의 예외 응답 전용 커스텀 어노테이션을 만들었습니다.

여기에는 예외 클래스의 배열을 인자로 전달받도록 했습니다.

스웨거는 OperationCustomizer 타입의 명세를 커스터마이징 할 수 있는 인터페이스를 제공하고 있습니다.

빈 설정 파일에서 위와 같이 OperationCustomizer를 커스텀해서 응답 정보들을 추가해 빈으로 등록하면 스웨거가 추가한 정보들에 맞게 명세 문서를 생성해 줍니다.

스웨거에서 명세를 하기 위한 객체의 그래프는 다음과 같이 설계되어 있습니다.

Operation -> ApiResponses -> ApiResponse

저희가 원하는 것은 예외 클래스에 있는 응답 정보들을 ApiResponse에 추가하는 것입니다.

setUpApiResponses 메서드에서는 각 예외 클래스마다 응답들로 ApiResponse를 생성해서 ApiResponses에 추가하도록 했습니다.

Exception에 들어있는 정보들을 추출하기 위해서는 Class타입으로 전달받은 예외 객체를 생성해주어야 합니다.

위 코드와 같이 extractExceptionFrom 메서드를 통해서 class로 전달받았던 예외 객체를 리플렉션을 통해 생성했습니다.

아래는 ApiResponse 객체에 응답 정보들을 추가하는 코드입니다.

Content를 생성해서 응답의 형태를 구성했습니다.

저희가 명세하고자 하는 응답의 형태는 message와 code입니다.

Exception에 담겨있는 정보를 꺼내서 다음과 같은 형태로 명세하고자 했습니다

message: ""

code: ""

ExceptionSituation은 응답의 형태이고

ExceptionMapper에서 Map<Class<? extends Exception>, ExceptionSituation>의 형태로 Class와 그에 해당하는 정보를 매핑하고 있습니다.

이제 커스터마이징이 완료됐습니다.

다음과 같이 어노테이션에 Exception class들을 인자로 전달만 하면 자동으로 예외 명세가 생성됩니다.

스웨거에서 생성된 결과를 확인해 보겠습니다.

자동으로 생성하면서도 훨씬 더 자세하고 깔끔한 모습입니다.

http 상태 코드뿐만 아니라 저희만의 에러 코드도 명세했습니다.

각 빨간색 박스는 코드에서 설정했던 name, description, ObjectSchema입니다.

이렇게 스웨거를 커스텀해서 자동으로 예외 응답을 생성하도록 만들어 봤습니다.

자동으로 생성하면서도 더 자세히 명세할 수 있었고, 예외 클래스를 통해 명세하므로 더 편하고 변경에도 영향을 받지 않도록 만들었습니다.

하루스터디 프로젝트를 진행하며 각자 테스트를 작성하고 머지를 하면서 이슈가 발생했다. 이에 대해 정리를 하고자 한다.

엔티티 연관관계

@Getter  
@NoArgsConstructor(access = AccessLevel.PROTECTED)  
@Entity  
public class Participant extends BaseTimeEntity {
	...
	@OneToMany(mappedBy = "participant", cascade = {CascadeType.PERSIST, CascadeType.REMOVE})  
	private List<Content> contents = new ArrayList<>();
}

@Getter  
@NoArgsConstructor(access = AccessLevel.PROTECTED)  
@Entity  
public class Content extends BaseTimeEntity {
	...
	@ManyToOne(fetch = FetchType.LAZY)  
	@JoinColumn(name = "participant_id")  
	private Participant participant;
}

간략하게 문제가 되는 부분의 엔티티 관계를 보면 위와 같다.

Participant와 Content가 1:N 관계이고, cascade가 걸려있다.

연관관계의 주인은 외래키를 가지고 있는 Content 쪽임을 명심하자.

테스트 코드

기존에 작성됐던 테스트에서는 다음과 같은 상황에서 문제가 발생하지 않았다.

Content content;

@BeforeEach
void setUp() {
	Participant participant = new Participant(study, member, "nickname");
	content = new Content(participant, 1);
	
	entityManager.persist(participant);
	entityManager.persist(content);
}

@Test
void test() {
	content.changePlan(Map.of("content", "written"));

	entityManager.flush();
	entityManager.clear();
	...
}

그런데 머지를 하면서 테스트가 깨지는 현상이 발생했다.

바로 Participant를 생성을 정적 팩터리 메서드로 변경하고 정적 팩터리 메서드 내에서 Content를 생성해서 영속성 전이를 통해 Content를 영속해주도록 변경한 부분 때문이었다.

팩터리 메서드의 로직은 다음과 같다.

public static Participant instantiateParticipantWithContents(Study study, Member member, String nickname) {  
	...
	Participant participant = new Participant(study, member, nickname, study.isEmptyParticipants());  
	participant.generateContents(study.getTotalCycle());  
	...
	return participant;  
}

따라서 다음과 같이 정적 팩터리 메서드로 생성을 하고, new Content(participant, 1); 이렇게 새로 Content를 새로 생성해서 영속화하게 되면 테이블 입장에서 participant를 외래키로 갖는 Content row가 하나 더 추가되게 된다.

Content content1;

@BeforeEach
void setUp() {
	Participant participant = Participant.instantiateParticipantWithContents(study, member, "nickname");
	content = new Content(participant, 1);
	
	entityManager.persist(participant);
	entityManager.persist(content);
}

@Test
void test() {
	content.changePlan(Map.of("content", "written"));

	entityManager.flush();
	entityManager.clear();
	...
}

Participant의 List<Content>의 size가 1임을 예상했던 것과는 다르게 정적 팩터리 메서드 내에서 생성된 Content들의 개수(현재 상황에서는 1개) + 1개 만큼 생긴 것을 확인할 수 있었다.

content를 출력하여 다음과 같은 결과를 확인할 수 있었다.

content.getPlan() = {}
content.getPlan() = {content=written}

이를 해결하기 위해 new Content(); 로 새로 생성하지 않고 다음과 같이 participant.getContents().get(0)으로 이미 생성된 Content 중 첫 번째 요소를 꺼내와서 사용하도록 수정했다.

@BeforeEach
void setUp() {
	Participant participant = new Participant(study, member, "nickname");
	content = participant.getContents().get(0);
	
	entityManager.persist(participant);
}

@Test
void test() {
	content.changePlan(Map.of("content", "written"));

	entityManager.flush();
	entityManager.clear();
	...
}

content는 participant의 상태이기 때문에 따로 entityManager.persist를 해주지 않아도 변경 감지가 작동한다.

content.changePlan를 호출하고 entityManager.flush()를 했을 때 update 쿼리가 실행되는 것을 확인했다.

Hibernate: 
	update
		content 
	set
		cycle=?,
		last_modified_date=?,
		participant_id=?,
		plan=?,
		retrospect=? 
	where
		id=?

정리하며

급하게 머지를 하면서 정적 팩터리 메서드를 사용하는 것을 채택했다.

다시 코드를 보면서 어떤 문제가 있는지 살펴보았다.

1. participant.getContents().get(0)으로 꺼내서 content.changePlan()을 직접 호출하는 방식은 캡슐화가 깨져 테스트의 복잡도를 높이는 요인이다.participant 객체에 메시지를 보내 cotent가 변경되도록 한다면 복잡도가 내려갈 것 같지만 현재로서는 participant에 책임이 없고 ContentService에서 로직을 수행하고 있기 때문에 불가능하다.
2. 생성과 관련한 로직들을 팩터리 메서드에 모아놨었지만 content까지 생성하는 것은 participant 생성과는 다른 책임이기 때문에 SRP를 위반한다는 생각이 들었고, 해당 로직만 서비스로 빼낸다면 괜찮을 것 같다. 이렇게 했을때 1번의 문제를 다시 Content를 직접 생성하는 방식으로 변경함으로써 해결할 수 있을 것 같다.

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

접근

• 우선순위 큐에 모든 파일의 크기를 넣는다.
• 큐에서 두 요소를 꺼내고 두 개를 더한 값을 큐에 다시 넣고, sum에도 더한다.
• 결과인 sum을 출력

요소는 K는 최대 10^6이고 파일의 최대 크기는 10,000 이므로 int로 계산하면 오버플로우가 발생하니 long으로 계산하자.

코드

https://github.com/aak2075/algorithm-baekjoon/blob/main/%EB%B0%B1%EC%A4%80/Gold/13975.%E2%80%85%ED%8C%8C%EC%9D%BC%E2%80%85%ED%95%A9%EC%B9%98%EA%B8%B0%E2%80%853/%ED%8C%8C%EC%9D%BC%E2%80%85%ED%95%A9%EC%B9%98%EA%B8%B0%E2%80%853.java

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

접근

• 입력에 따른 좌표 평면coordinate를 만든다.
• coordinate를 순회하며 값이 2인(바이러스를 담을 수 있는) 좌표를 담은 canVirus를 만든다.
• 백트래킹으로 coordinate를 순회하며 바이러스를 m개 놓을 수 있는 모든 경우의 수를 담은 cases를 만든다.
  • coordinate를 순회하며 값이 2인 좌표를 cases에 add
  • 백트래킹의 decision spaces는 해당 좌표를 선택하는 경우와 선택하지 않는 경우로 구성한다.
• cases마다 bfs 탐색으로 탐색의 성공하는 depth를 계산하여 이 중 가장 작은 depth를 계산하면 끝
  • cases 중에서 선택된 case라면 bfs큐에 삽입
  • 선택되지 않은 case라면 빈 칸으로 변경하기 위해 copyCoordinate의 해당 좌표를 0으로 변경한다

코드

https://github.com/aak2075/algorithm-baekjoon/tree/main/%EB%B0%B1%EC%A4%80/Gold/17141.%E2%80%85%EC%97%B0%EA%B5%AC%EC%86%8C%E2%80%852

[https://school.programmers.co.kr/learn/courses/30/lessons/42862#]

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

접근

• 0부터 n+1까지 clothes 리스트를 1로 초기화 한다.
  • lost나 reserve는 첫 번째 학생을 0번이 아닌 1번으로 입력하기 때문에 주의
• 정렬되었다는 언급이 없기 때문에 reserve를 오름차순 정렬한다.
• reserve[i] 번째 clothes의 원소를 2로 변경한다.
• lost[i] 번째 clothes의 원소에서 1을 뺀다.
  • 여분이 있는 학생도 체육복을 도난당할 수 있고 이 경우 2개 -> 1개가 되므로 0으로 초기화 하는 실수를 하면 안된다.
• reserve를 순회하면서 여분이 있는 학생은 앞이 체육복이 없으면 앞에 빌려주고 뒤가 체육복이 없으면 뒤에 빌려준다
  • 순회시 reserve[i] 번째가 도난당해서 1이면 빌려줄 수 없기 때문에 2인지 검사한다.
  • 인덱스 초과 주의

해결 방법론 - 현재 상황에서 최적의 해를 구하는 그리디 알고리즘을 사용하여 해결.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv1/42862.%E2%80%85%EC%B2%B4%EC%9C%A1%EB%B3%B5/%EC%B2%B4%EC%9C%A1%EB%B3%B5.java

우아한테크코스의 MVC미션을 진행하던 중 다음과 같은 리뷰를 받았다.

스트림의 forEach를 이용해서 로직을 수행하게 되면 가독성도 떨어지고 동시성을 보장할 수 없다.

또한, Stream은 부수 효과가 없는 함수형 프로그래밍을 위해 만들어진 것이므로 Stream의 의도와도 맞지 않다.

이펙티브 자바 아이템 46에서도 부작용 없는 순수 함수를 사용하라고 이야기하고 있다.

1. 기존 코드

문제의 코드를 보고 개선해보자.

private final Map<HandlerKey, HandlerExecution> handlerExecutions;

public void initialize() {
    ...
    final var methods = clazz.getMethods();
    Arrays.stream(methods)
            .forEach(method -> putHandlerExecutions(handler, method));
}

private void putHandlerExecutions(final Object handler, final Method method) {
    final var annotation = method.getDeclaredAnnotation(RequestMapping.class);
    final var handlerExecution = new HandlerExecution(handler, method);

    Arrays.stream(annotation.method())
            .map(requestMethod -> new HandlerKey(annotation.value(), requestMethod))
            .forEach(handlerKey -> handlerExecutions.put(handlerKey, handlerExecution));
}

putHandlerExecutions에서는 annotation.method() 배열의 원소 만큼

handler와 method로 Map<HandlerKey, HandlerExecution>의 Entry를 생성해서

인스턴스 변수인 handlerExecutions에 put을 하고 있다.

2. 개선된 코드

먼저 완성될 결과를 보자.

private final Map<HandlerKey, HandlerExecution> handlerExecutions;

public void initialize() {
            final var methods = clazz.getMethods();
            final var executionMap = createHandlerExecutionMap(handler, methods);
            handlerExecutions.putAll(executionMap);
}

Map<HandlerKey, HandlerExecution>을 생성하는 createHandlerExecutionMap으로 메서드로 추출하여 해당 메서드에서 Map을 완성한다.

이를 handlerExecutions.putAll로 맵의 모든 엔트리를 삽입해주었다.

핵심인 createHandlerExecutionMap을 살펴보자.

private Map<HandlerKey, HandlerExecution> createHandlerExecutionMap(final Object handler,
        final Method[] methods) {
    return Arrays.stream(methods)
            .map(method -> toHandlerExecutions(handler, method))
            .flatMap(map -> map.entrySet().stream())
            .collect(Collectors.toMap(Entry::getKey, Entry::getValue));
}

요소인 method마다 toHandlerExecutions(handler, method)를 통해 Map<HandlerKey, HandlerExecution>으로 만들어준다.

해당 Map이 여러개이기 때문에 flatMap으로 평탄화 하고 모든 Entry에 대한 스트림을 다시 만들어 준다.

결과의 key와 value를 다시 Map으로 collect 한다.

toHandlerExeutions는 다음과 같이 단순하게 파라미터를 통해 HandlerKey와 HandlerExecution을 만들어서 Map으로 맵핑해준다.

private Map<HandlerKey, HandlerExecution> toHandlerExecutions(
        final Object handler, final Method method) {
    final var annotation = method.getDeclaredAnnotation(RequestMapping.class);
    final var handlerExecution = new HandlerExecution(handler, method);

    return Arrays.stream(annotation.method())
            .map(requestMethod -> new HandlerKey(annotation.value(), requestMethod))
            .collect(Collectors.toMap(Function.identity(), handlerKey -> handlerExecution));
}

결론

스트림으로 만들기 어렵다고 무작정 forEach로 해결하거나 for-loop로 해결하기 보다 고민을 조금 해보면 충분히 해결할 수 있다. 위 방법은 여러개의 Map을 만들고 이를 합치는 과정을 통해 해결했다.

이 방식 이외에 method 원소 마다 createHandlerExecutionMap에서 Map을 생성하여 합치는 방식이 아닌 createHandlerExecutionMap에서 Stream<AbstractMap.SimpleEntry<HandlerKey, HandlerExecution>> 즉, 엔트리의 스트림을 반환하여 스트림의 중간 연산으로 활용할 수도 있다.

하지만 이러한 방법은 복잡도가 증가하고 Map의 key에 대한 중복 처리가 어떻게 될지 예상이 되지 않는다.

Map을 생성하여 합치는 방식보다 메모리가 효율적이기는 하나 그 정도까지 고려할 필요는 없다고 생각한다.

참고

• https://tecoble.techcourse.co.kr/post/2020-05-14-foreach-vs-forloop/

[https://school.programmers.co.kr/learn/courses/30/lessons/87694]

문제

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
itemX, itemY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

접근

• 모든 좌표를 x 2 한다
  • 경로가 이어져 있지 않더라도 거리가 1이면 갈 수 있게 되기 때문에 이를 방지하기 위해 x2를 함.
• 0부터 100까지의 좌표 전부를 false 처리한다.
• 각 rectangle x 2 좌표를 전부 true 처리한다.
• 각 rectangle의 안쪽을 false 처리한다
  • 왼쪽 끝의  x +1 부터 오른쪽 끝의 x -1 까지
  • 아래 끝의 y + 1부터 위 끝의 y - 1까지
• 좌표에서 true인 부분을 따라서 bfs 탐색을 수행한다
  • 방문 처리를 통해 재방문을 방지한다
  • 좌표의 범위를 벗어난 위치는 방문하지 않는다
  • 좌표마다 depth를 기록, 다음 위치에서는 이전 좌표의 depth + 1로 계산한다
• 처음에 좌표에 x2를 해주었기 때문에 결과로 나온 depth를 다시 2로 나누어주면 끝.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/87694.%E2%80%85%EC%95%84%EC%9D%B4%ED%85%9C%E2%80%85%EC%A4%8D%EA%B8%B0/%EC%95%84%EC%9D%B4%ED%85%9C%E2%80%85%EC%A4%8D%EA%B8%B0.java