2 ≤ N ≤ 100,000 이기 때문에 O(N²) 시간을 넘지 않는 방식으로 해결해야 한다.
각 도시에서 주유를 할지 말지의 여부를 어떻게 결정할까?
다음 도시의 기름값(cost[i])이 현재 머무르고 있는 도시의 기름값(currCost)보다 크다면 현재 도시에서 다음 도시까지 쓸 기름을 주유한다.
또 그 다음 도시의 기름값을 확인하고, 현재 도시의 기름값과 비교한다. 현재 도시보다 싼 도시가 나올 때까지 누적시킨다. 더 싼 도시를 발견하면 그곳으로 이동해서(currCost = cost[i] 할당) 주유한다. 마지막 도시까지 확인하면 종료한다.
즉, 주유해야 하는 리터 수는 일정하므로 (전체 dist만큼) dist[i]만큼의 기름을 어느 주유소에서 주유할 지를 반복문으로 currCost와 비교하면서 찾으면 된다. (currCost : 역대 방문한 주유소 중 가장 낮았던 주유비를 기록)
코드
import java.io.*;
import java.util.*;
public class Q13305 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[] cost = new long[N];
long[] dist = new long[N - 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");;
for(int i = 0; i < N - 1; i++) {
dist[i] = Long.parseLong(st.nextToken());
}
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++) {
cost[i] = Long.parseLong(st.nextToken());
}
long sum = 0;
long currCost = cost[0];
sum += currCost * dist[0];
for(int i = 1; i < N - 1; i++) {
if(currCost > cost[i]) { //더 싼값에 주유할 수 있다면
currCost = cost[i];
}
sum += currCost * dist[i];
}
System.out.print(sum);
}
}
매 순간마다 최선의 선택을 한다는 그리디 알고리즘인 만큼, 매 순간마다 가장 비용이 작은 주유소를 택하는 발상이 중요한 문제였다. 필요한 비용을 계속 누적시켜야 하는 문제이고, 입력으로 주어지는 가격 또한 큰 편이다. 오버플로우가 일어나지 않도록 무언가를 누적시켜야 하는 변수를 long 타입으로 선언해주었다.
Software Expert Academy 1208번 : Flatten (D3) (문제 링크)
키워드
완전탐색, 그리디
풀이 접근법
입력 tc의 개수는 무조건 10개로 고정이다. 입력 배열의 크기도 항상 100으로 고정이다.
완전 탐색으로 풀이하였다. 그리디한 발상을 이용하기도 하였다.
입력 배열을 정렬하는 것이 핵심이다. 매 순간마다 가장 왼쪽 & 오른쪽 끝 값을 이용하여 덤프 작업을 수행하면 되며, 이렇게 하면 매 반복마다 가장 높이가 높은 곳과 낮은 곳을 일일이 찾을 필요가 없다.
가장 왼쪽의 작은 값을 가리키는 lowerBound와 가장 오른쪽의 큰 값을 가리키는 upperBound 계속 찾아주며 덤프 작업을 수행한다. 같은 값이 여러개 있다면 lowerBound는 같은 값들 중 가장 오른쪽 것을 가리키고, upperBound 또한 가장 오른쪽 것을 가리킨다.
풀이 당시에는 가장 작은 값을 가리키는 인덱스, 가장 큰 값을 가리키는 인덱스라는 의미로 lowerBound와 upperBound라는 이름을 썼으나 이분탐색에서 쓰는 개념과 혼동될 여지가 있다. lowerIndex, upperIndex 등으로 바꾸어 쓰는 게 좋을 듯하다.
코드
import java.io.*;
import java.util.*;
public class SWEA1208 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = 10;
int N = 100;
int[] boxes = new int[N];
StringBuilder sb = new StringBuilder();
for(int test_case = 1; test_case <= T; test_case++) {
int dump = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++) {
boxes[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boxes);
int lowerBound = 0;
int upperBound = N - 1;
for(int i = 0; i < dump; i++) {
//1.dump 작업을 수행한다.
boxes[lowerBound] += 1;
boxes[upperBound] -= 1;
//2.다음 lowerBound를 찾는다.
for(int j = 0; j < N - 1; j++) {
if(boxes[j] < boxes[j + 1]) {
lowerBound = j;
break;
}
}
//3.다음 upperBound를 찾는다.
if(boxes[upperBound] < boxes[upperBound - 1]) {
upperBound = upperBound - 1;
}
else { // upperBound >= upperBound - 1
upperBound = N - 1;
}
}
Arrays.sort(boxes);
int result = boxes[N - 1] - boxes[0];
sb.append("#" + test_case + " ").append(result).append('\n');
}
System.out.print(sb);
}
}
lowerBound와 upperBound를 찾는 방식이 조금 깔끔하지 못하다. 입력의 크기가 더 커진다면 이러한 방식은 사용할 수 없을 것이다. 풀이를 마친 후 다른 분들의 풀이를 참고해보니, 덤프 작업을 수행할 때마다 배열을 정렬하는 방법도 있었다. 그 방식을 사용한다면 코드를 더욱 깔끔하게 줄일 수 있을 듯하다.
Spring, 또는 SpringBoot 둘 중 하나를 택해 웹 서비스를 개발하는 수업의 과제물로 제출한 프로젝트이다.
이전에 기능을 구현할 때에는 과제 마감일에 쫓겨 가독성이 좋지 못한 코드를 작성했었다. 금번 리팩토링에서는 이러한 문제를 해결하고 코드의 품질을 높이는 방법에 대해 팀원들과 함께 공부해보았다. 회의는 특별한 이변이 없는 한 매주 진행하였다. 총 3명의 팀원이 함께하였으며, 로버트 C. 마틴의 저서 <클린 코드(애자일 소프트웨어 장인 정신)>를 읽고 각자 학습한 바를 정리하고 이를 바탕으로 테스트 작성과 리팩토링을 하였다. 여기에 팀장으로서 전반적인 개발 과정을 검토하고, 코드 리뷰와 회의를 주도하였다.
프로그램 구조도를 수정해야 하는지 고민했으나, 리팩토링 과정에 설계와 기능 수정은 포함되지 않는다.
15라인이 넘어가는 함수 분리, 들여쓰기 수정, 불필요한 주석 삭제, 메소드 파라미터의 개수 줄이기 등 코드의 가독성을 높일 수 있는 방안을 검토하였다.
<클린 코드> (로버트 C. 마틴), <리팩토링 1판> (마틴 파울러), <객체지향의 사실과 오해> (조영호) 중에서 언어에 구애받지 않고 여러 코드 리팩토링에 가장 적용하기 쉬운 첫 번째 서적을 선택하였다.
1주차
각 클래스 별로 어느 메소드를 어떻게 수정해야 할지, 리팩토링할 목록을 정리하였다.
2주차
<클린 코드>를 읽고 중요한 내용들을 문서화시켜 정리하였다.
3주차~8주차
각 클래스 별로 테스트 코드를 작성하였다. 본래 TDD 개발방식에 따르면 기능 개발에 앞서 테스트를 미리 작성하는 것이 맞지만, 본 프로젝트 는 스프링 프레임워크를 배우는 강의의 과제물로써 개발한 것이고, 일전에 별도의 테스트 작성법을 학습한 적이 없기에 부득이하게 기능 개발 이후에 테스트를 작성하게 되었다. 코드리뷰는 2~3주에 한 번씩 시행한다.
테스트 작성 과정 중에 맞닥뜨린 오류는 다음 항목에 정리한다.
9주차~15주차
완성된 테스트 내용을 바탕으로 코드를 리팩토링한다. 상기한 내용처럼 길이가 긴 함수를 최대한 분리하고 조건문을 캡슐화하여 가독성을 향상시키고 의미를 파악하기 쉽도록 하였다. 또, 강의 수강 당시 학습용으로 작성해두었던 주석들을 모두 삭제하였다. 마찬가지로 코드리뷰는 2~3주에 한 번씩 시행한다.
Stream을 통해 데이터를 처리할 때 타입 오류를 맞닥뜨리고서 Optional 타입이 무엇인지 알게 되었다.
Optional 타입은 쉽게 말하면 null이 발생할 수 있는 값을 감싸는 Wrapper 클래스이다. 불필요한 null 처리를 줄일 수 있다.
이때, Stream의 findAny()로 발견한 값들도 Optional 타입으로 반환된다.
따라서 Optional<T>.get()으로 안에 들어있는 내용물을 별도로 꺼내주어야 한다.
BindingResult나 HttpSession 객체를 테스트에 활용하는 방법
이러한 객체들은 단순히 인스턴스를 생성하는 방식으로는 사용할 수 없다. 대신 Mockito.mock()으로 Mock 객체(가짜 객체)를 만들어주면 테스트에 활용할 수 있다.
MockHttpSession 객체는 다음과 같은 방식으로 생성한다.
Login userSession;
MockHttpSession session;
@BeforeEach() //다른 테스트 메소드보다 가장 먼저 실행된다.
public void setUp() {
Account account = new Account();
account.setUserId(USER_ID);
userSession = new Login(account);
session = new MockHttpSession();
session.setAttribute("userSession", userSession);
}
학교 과제와 무관하게 진행된 스터디 모임이었다. 그 덕분에 마감일에 쫓기지 않고 공부를 할 수 있었다.
JUnit을 이용해 테스트 함수를 작성해본 것은 이번이 두 번째였다. 그러나 JUnit 테스트를 처음 활용해보았을 때는 MVC 구조의 웹 어플리케이션이 아닌, 일반적인 자바 객체의 유효성을 검증하는 등의 기능만 사용해보았던 탓에 웹 어플리케이션의 테스트 코드는 어떻게 작성해야 하는지 헤메기도 하였다.
다행히도 인터넷에 SpringBoot 기반으로 테스트 코드를 작성하는 방법을 잘 정리해놓은 자료들이 제법 있어 도움이 많이 되었다. 검색의 힘이 가장 컸던 것 같다. 블로그 게시글들을 보면서 차츰 라이브러리 내의 메소드 사용법에 익숙해지도록 하였다.
그 다음에는 given - when - then 패턴을 핵심으로 삼아 테스트코드를 작성하였다. 이러한 뼈대가 있다고 생각하니 테스트 작성에 막연함이 덜한 느낌이었다. (참고한 블로그 링크는 이곳)
위 패턴에 따라 테스트 코드를 작성하고, 작성 중 모호한 부분이 있다면 클린코드 17장: '냄새와 휴리스틱'에 수록된 원칙들을 따랐다. 가능한 클래스 내의 모든 메소드를 테스트해보려 하였다. 주로 참고한 원칙들은 다음과 같다.
T1: 불충분한 테스트는 독이다.
T3: 사소한 테스트도 건너뛰지 마라.
T4: 무시한 테스트는 모호함을 뜻한다.
T5: 경계 조건을 각별히 신경 써서 테스트하라.
T7: 실패 패턴을 살펴라.
다만 `T2: 커버리지 도구를 사용하라` 의 원칙은 고려하지 못한 것이 아쉽다. 테스트 메소드 작성과 리팩토링에 급급해 커버리지를 미처 신경쓰지 못하였다. 회고를 작성한 후에도 시간을 내어 테스트 커버리지를 확인해보고 싶다.
테스트 작성을 마치고, 리팩토링 과정에서는 상기한 내용처럼 코드의 가독성을 높이는 데에 집중했다. 메소드명을 통해서 의미를 드러내고, 메소드가 수행하는 일을 문장으로서 나타내는 것이 참 중요하다고 느꼈다. 팀원의 코드 중 몇몇 부분은 잘 이해하지 못하기도 했었는데, 그 또한 메소드명을 수정하고 몇몇 코드를 캡슐화한 덕분에 그것이 의미하는 바를 쉽게 이해할 수 있게 되었다.
<클린 코드> 내에서도 강조했던 내용이지만, 결과적으로 프로그램의 코드 또한 사람이 읽는 문서의 일종이고, 그만큼 협업하는 사람들이 이해하기 쉽도록 작성하는 것이 중요하다는 것을 다시 느꼈다.
Spring, 또는 SpringBoot 둘 중 하나를 택해 웹 서비스를 개발하는 수업의 과제물로 제출한 프로젝트이다. 총 4명의 팀원이 함께 협업하였으며, 수업에서 배운 모든 분야의 지식을 두루 활용하기 위해 프론트/백의 구분을 두지 않고 전원이 풀스택으로 개발하였다. 여기에 팀장으로서 과제 산출물과 전반적인 개발 과정을 검토하고, 회의를 주도하였다.
Spring을 먼저 학습한 후 SpringBoot를 뒤늦게 배웠는데, 시간이 촉박하더라도 SpringBoot로 개발하는 것을 택했다. JpaRepository 인터페이스를 사용하면 메소드 작명 규칙에 따라 쿼리가 자동으로 생성되고, Lombok 의 어노테이션을 이용하면 Getter와 Setter 까지 자동으로 생성되는 등, Spring보다 다양하고 편리한 기능들이 많이 정의되어 있었기에 한정된 기간 내에 원하는 기능을 모두 개발할 수 있을 거라 판단했다. 겸사겸사 문서를 읽고 라이브러리를 사용하는 요령도 길렀다.
✨기능
주요 기능 3가지 정의
✨수행 과정
2주차
주요 활동 주제 및 개발범위를 선정하고, 개발 업무를 분담하였다.
3주차
요구사항을 분석하고 세부 기능을 정의하였다.
실제로 구현이 어떤 방식으로 이루어지는지 몰랐기 때문에 요구사항을 과도하게 세분화하는 불상사가 발생했다.
결국 최종 보고서 제출 시에 세분화 된 몇몇 기능을 통합해서 도표를 작성하기도 했다.
4주차
UI를 설계하고 Request 처리 흐름도를 간략하게 작성하였다.
요청 흐름 작성은 Spring 기반 웹 프로그램에서 어떤 방식으로 요청이 발생하고 어떤 흐름으로 요청이 전달되는 지 정확하게 알아야만 작성할 수 있는 도표이다. 처음 MVC 구조를 학습할 때에는 쉽사리 구조가 파악되지 않아 교안을 반복해서 확인하기도 했다. 후에는 이 지식을 확실히 내것으로 만들기 위해서 빈 종이 위에 Controller, View, Service 등을 표시하고 그 사이에 오가는 요청을 도표로 그려보기도 하였다. 이 방식이 특히 프로그램의 흐름을 익히기에 적합한 것 같다.
5주차
데이터베이스 스키마(논리적, 물리적)를 설계하고 도메인 클래스를 작성하였다.
DB 스키마는 설계 단계에서부터 신중을 기해야 한다고 생각한다. 일전의 프로젝트에서는 각 테이블 별 연관 관계 특성 상 데이터가 꼬이는 바람에, 요구사항에 맞는 API를 설계하기 위해서 DB를 지우고 다시 설계해야만 하는 불상사가 발생한 적 있다.
이 과정에서 특히나 도움이 되는 것은 요청 흐름과 데이터의 이동을 말로 풀어서 설명하는 것이다. DB 스키마는 현실 세계에 존재하는 문제 상황을 데이터로 모델링한 산출물이라고 생각한다. 이 산출물을 올바르게 내기 위해서는 요청 흐름과 요구사항을 정확하게 파악해야 하며, 데이터가 어디에서 어떻게 전달되어야 하는지를 사람의 언어로 잘 풀어내는 것이 요청 흐름과 프로그램 구조를 이해하는 데에 도움이 된다.
이 때문에 팀원들과 온라인 화상 회의에서 몇 시간동안을 말로 설명하고 이해한 것을 DB 구조로 옮겨 적었던 기억이 난다.
6주차
설계한 데이터베이스 스키마를 토대로 ER 다이어그램을 작성한다.
설계서 제출을 위해 개체관의 관계와 각 컬럼의 의미를 풀어서 설명하였다. 상기한 바와 같이 설계서도 결국 사람이 읽는 것이기 때문에 명료하고 이해하기 쉬운 언어로 내용을 설명하는 것이 중요하다고 생각한다. 팀 내의 어떤 사람이 읽어도 중의적으로 해석되지 않고, 한 가지 의미로만 뚜렷하게 설명되어야 하지 않을까 싶다.
7주차
Controller 클래스, Service 클래스를 정의하고 Request 처리 흐름도를 최종적으로 작성하였다.
요청 처리 흐름은 Use Case별로 구분하여 작성하였다. 마찬가지로 흐름도를 명료하게 작성하기 위해서라면 프로그램의 실행 구조에 대한 이해가 수반되어야 한다.
Controller에서 어떤 handler 메소드를 거쳐야 하는지, 그 메소드에서는 어떤 Service 메소드를 호출하는지, 그 Service 메소드는 또 어떤 DAO 메소드를 호출하고, DAO 메소드는 DB에 접근하여 어떻게 데이터를 처리하고 어떤 데이터(View 또는 Model)를 반환하는지 등등... 수업에서 제공한 예제 프로젝트와 예제의 설계도를 반복적으로 읽으며 분석하였다.
9주차~10주차
중간고사를 마치고 Handler 메소드의 이름을 정의하고, DAO 인터페이스 및 Controller 클래스를 다이어그램으로 정의하였다.
슬슬 산출물이 쌓이는 단계이기도 하고, 설계를 토대로 실질적으로 기능 구현에 들어서는 시기였다. 어떤 클래스를 얼마나 정의하고, 그 안에는 무슨 메소드가 정의되어 있는지를 미리 설계했기 때문에 이를 토대로 개발을 시작하기가 비교적 수월했다.
11주차
전체 기능 중 먼저 구현해야 하는 우선순위를 정하고, 커밋메시지 양식을 통일하였다.
220512 login fix와 같이 yyMMdd + 기능 설명(한글or영어) 으로 통일하였는데, 당시에는 흔히 통용되는 커밋 메시지 양식을 잘 몰라서(feat, fix, style 등등) 이와 같은 형식으로 결정했었다. 조금 더 검색해보고 결정했을걸 하는 아쉬움이 남는다.
12~16주차
본격적으로 기능을 구현해나갔다. 맞닥뜨린 오류와 해결 방법은 아래의 항목에 적는다.
✨문제 해결
스프링부트에서 jsp 파일을 인식할 수 없었던 오류
application.properties 파일에 경로가 올바르게 설정되어 있는지 검토한다. thymeleaf로 정의된 View는 대개 classpath:templates 디렉토리 아래에 배치되지만, jsp 파일은 그렇지 않다. 본 프로젝트에서는 jsp 파일이 WEB-INF/jsp 디렉토리 아래에 위치하기 때문에 적절하게 파일 경로를 나타내는 prefix와 suffix를 수정해주었다.
SQL: 인덱스에서 누락된 IN 또는 OUT 매개변수
질의문과 여기에 매핑되는 Object의 컬럼수가 맞지 않을 때 발생한다. 본 프로젝트에서는 JpaRepository나 springframework 라이브러리에 정의된 @Repository 어노테이션으로 자동 생성되는 쿼리문 외에도 특정 기능 구현을 위해 JdbcTemplate 기반으로 직접 쿼리문을 작성할 필요가 있었다. 요청하는 데이터의 가짓수가 많을 수록 혼동할 확률이 높으니 쿼리문과 Object가 알맞에 매핑되었는지 검토할 필요가 있다.
ORA-00911: 문자가 부적합합니다
SQL문 중간에 세미콜론(;)이 포함되는 등, SQL문 자체에 문제가 있을 때 발생하는 오류이다. 오탈자가 없는지 점검하였다.
class [I cannot be cast to class [Ljava.lang.Object; ([I and [Ljava.lang.Object; are in module java.base of loader 'bootstrap')
ModelAttribute로 int[] 타입 객체를 전송할 때 발생하는 에러이다. ModelAttribute로는 String[] 또는 Object[] 타입만 전송할 수 있다.
ModelAttribute로는 primitive type을 보낼 수 없음에 유의해야 한다.
ORA-02296: 사용으로 설정 불가 - 널 값이 발견되었습니다.
DB에서 null값으로 생성된 컬럼의 디폴트를 not null로 설정할 때 발생하는 오류이다. String의 경우 공백문자 등을 이용해 초기화 시키고 값을 바꿔주어야 한다.
Neither BindingResult nor plain target object for bean name“000”available as request attribute
주어진 조건에 부합하는 노래를 ‘두 곡’만 선정하는데, 만약 조건에 부합하는 것이 오직 한 곡만 존재한다면 한 곡만 수록해야 한다. 조건은 다음과 같다.
속한 노래가 많이 재생된 장르를 먼저 수록
각 노래별로 총 재생수를 집계하고, 해당 장르의 곡 목록을 탐색한다 ⇒ 정렬 필요
장르 내에서 많이 재생된 노래를 먼저 수록
그 장르 내에서 가장 재생수가 높은 노래 탐색 ⇒ 정렬 필요
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
별도의 Comparator를 이용한 정렬 기준이 필요하다.
장르별 재생수를 집계한 다음에 수록은 어떻게 할까?
우선순위 큐에 모든 장르를 넣고, 재생수가 높은 장르를 하나씩 뽑는다. (poll) ⇒ Entry 자료구조 필요
해당 장르의 노래들로 Entry<장르, 재생수> 리스트를 만들어 사전순의 반대로 정렬한다.
앨범 등록을 마친 장르는 자연히 우선순위 큐에서 삭제된 상태이다.
큐에 더 이상 들어있는 것이 없다면 종료한다.
코드
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays) {
int[] answer = {};
HashMap<String, Integer> map = new HashMap<>();
//장르별 총 재생횟수 집계
for(int i = 0; i < genres.length; i++) {
String genre = genres[i];
int play = plays[i];
map.put(genre, map.getOrDefault(genre, 0) + play);
}
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
(o1, o2) -> Integer.compare(o2.getValue(), o1.getValue())); //내림차순
for(Map.Entry<String, Integer> entry : map.entrySet()) {
pq.add(entry);
}
ArrayList<Integer> result = new ArrayList<>();
//pq에서 재생수가 높은 장르 순으로 뽑으며 앨범에 수록한다.
while(!pq.isEmpty()) {
Map.Entry<String, Integer> entry = pq.poll();
String genre = entry.getKey();
//poll()로 뽑은 장르의 노래들만 모은다.
ArrayList<int[]> list = new ArrayList<>();
for(int i = 0; i < genres.length; i++) {
if(genre.equals(genres[i])) {
int[] a = {i, plays[i]};
list.add(a);
}
}
Collections.sort(list, (o1, o2) -> (Integer.compare(o2[1], o1[1])));
int avaliableSize = 0;
if(list.size() >= 2) {
avaliableSize = 2;
}
else if (list.size() == 1) {
avaliableSize = 1;
}
for(int i = 0; i < avaliableSize; i++) {
int num = (list.get(i))[0];
result.add(num);
}
}
answer = new int[result.size()];
for(int i = 0; i < result.size(); i++) {
answer[i] = result.get(i);
}
return answer;
}
}
해시 문제집에 있었지만 해시 그 자체보다는 여러 자료구조를 알아야 풀기 쉬운 문제인 것 같다. 시간을 정해놓고 풀었기 때문에 급하게 마무리했으나, 개인적으로 코드를 더 깔끔하게 짰으면 좋았을 텐데 하는 아쉬움이 있다. Stream을 사용하면 몇몇 코드를 깔끔하게 다듬을 수 있을 듯하다.
입력의 수는 1 ≤ n ≤ 50,000 이므로, 50,000 × 50,000 = 2,500,000,000 으로 10^9 시간을 초과한다. 따라서 O(n²) 시간을 넘지 않는 방식으로 풀이해야 한다.
보트의 무게 제한을 넘기지 않으려면 가능한 가벼운 사람과 무거운 사람을 함께 태워 보내야 한다. ⇒ 주어진 인원의 무게를 오름차순으로 정렬해서 양 끝을 탐색한다.
배열을 정렬하였으므로 왼쪽 포인터와 오른쪽 포인터가 가리키는 사람을 함께 태울 수 있는지의 여부를 체크한다.
만약 두 사람을 함께 태울 수 없다면 맨 오른쪽의 무거운 사람을 먼저 보트 하나에 태워보내고(right += 1) 다음 사람들의 무게를 체크한다.
둘 다 태울 수 있다면 해당 2인을 태우고 양쪽의 인덱스를 모두 증가시킨다. (left += 1 & right += 1)
두 포인터가 만나는 지점까지 탐색하면 종료된다. (같은 사람을 가리키게 되면 종료)
코드
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int left = 0;
int right = people.length - 1;
while(left <= right) {
if(people[left] + people[right] <= limit) {
left += 1;
}
right -= 1;
answer += 1;
}
return answer;
}
}
처음에는 배열을 정렬한 뒤 맨 앞부터 두 명씩 가벼운 사람을 태우는 방식으로 풀었는데 대부분의 테스트 케이스에서 틀렸다. 반례를 찾아보니 인접한 무게의 사람들끼리 태우는 것으로는 해를 구할 수 없어, 투포인터로 바꿔 풀었다.
