모든 사람들을 몸무게 순으로 정렬했을 때, 가장 몸무게가 가벼운 사람 + 가장 몸무게가 무거운 사람이 무게 제한보다 크다면 가장 몸무게가 무거운 사람은 아무와도 구명보트를 같이 탈 수 없다.
따라서, 그 경우에는 구명보트의 카운트를 1 증가 시켜주고 가장 몸무게가 가벼운 사람 + 2번째로 가장 몸무게가 무거운 사람과 무게제한을 비교하는 식으로 계속 반복해나가면 답을 얻을 수 있다.
간단한 코드라, 코드 블럭 단위의 설명은 생략.
3. 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
sort(people.begin(), people.end()); // people 정렬
int lo = 0; // 가장 몸무게가 가벼운 사람의 index
int hi = people.size() - 1; // 가장 몸무게가 무거운 사람의 index
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) { // 가장 몸무게가 가벼운 사람과 가장 무거운 사람이 같이 구명보트를 탈 수 있으므로
lo++;
hi--;
}
else { // 그 외에는 가장 무거운 사람 혼자 구명보트를 타야 함
hi--;
}
answer++;
}
return answer;
}
처음에는 굉장히 단순하게 오른쪽으로 이동하는 것보다 왼쪽으로 이동하는 게 적은 경우는 _A______형태로 name[1] == 'A' 일 때 뿐이라고 생각했다.
그래서 호다닥 풀어서 냈으나, 결과는 당연히 실패....
정확하게 풀기 위해서는 다음과 같은 반례를 고려해야 한다.
name = "BBBAAAB" / answer = 9 name = "ABABAAAAABA" / answer = 11
요점은 쭉 오른쪽으로 가다가 어느 순간 왼쪽으로 되돌아갈 때가 최적인 경우도 있다는 것!
결국 최적의 경우를 항상 선택해야하므로 Greedy 다.
(1) 초기화 및 설정
answer = 0;
int N = name.length(); // name 길이
int a_num = 'A' - '0'; // 'A'의 ASCII
string compare(N, 'A'); // 바꾸고자 하는 문자열
a_num : 알파벳을 바꿀 때 위, 아래 버튼을 몇 번 눌러야하는지를 간편히 계산하기 위해 ASCII 코드를 이용.
ex ) 'A' = 48, 'B' = 49 이므로 ASCII 코드의 차를 이용해 버튼을 몇 번 눌러야하는지 계산할 수 있음.
compare : 'A'를 N만큼 가지고 있는 문자열. 나중에 While 종료조건(compare == name)을 위해 사용.
ex ) name = 'JAZ'. 'compare' = 'AAA
(2) 최적 방향 찾기
int check_move(int N, int i, string name, string compare) {
int left = 0; int right = 0; int index = 0;
for (int j = i + 1; j < i + N; j++) { // 오른쪽으로 이동하는 경우
if (name[j % N] != compare[j % N]) { // name과 compare가 달라질 때까지 이동
right = j - i; // 오른쪽으로 몇 번 이동했는지
index = j % N; // 그때의 인덱스
break;
}
}
for (int j = i - 1; j > i - N; j--) { // 왼쪽으로 이동하는 경우
if (name[(N + j) % N] != compare[(N + j) % N]) {
left = i - j;
if(left < right) index = (N + j) % N; // 왼쪽으로 이동하는 경우가 더 최적이면, 해당 위치로 인덱스 갱신
break;
}
}
answer += min(left, right); // 왼쪽 이동과 오른쪽 이동 중에 더 작은 값 더하기
return index; // 그 때의 인덱스 반환
}
왼쪽으로 이동하는 것과 오른쪽으로 이동하는 것 중 어느 방향으로 이동하는 것이 더 최적인지를 계산하기 위한 함수.
맨 끝 문자에서 +1 을 하면 맨 처음으로, 맨 처음 문자에서 -1을 하면 맨 끝으로 이동해야하기 때문에 모듈러 연산 사용.
ex ) N = 7, j = 8 이라면, name[j % N] = name[8 % 7] = name[1]
최적의 이동 수만큼 answer에 더해주고, 그 때 도착한 인덱스 반환
(3) 원하는 문자열이 될 때까지 갱신하며 반복
int i = 0;
while (name != compare) {
if(name[i] == compare[i]) i = check_move(N, i, name, compare); // 현재 인덱스의 name과 compare가 같으면 이동
if (name[i] != 'A') {
int move = (name[i] - '0') - a_num; // 얼마나 위 버튼을 눌러야 하는지
if (move > 13) move = 26 - move; // 중간값인 13보다 크다면 아래 버튼을 누르는 게 이득
answer += move;
compare[i] = name[i]; // compare 갱신
}
}
return answer;
3. 전체 코드
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int answer;
int check_move(int N, int i, string name, string compare) {
int left = 0; int right = 0; int index = 0;
for (int j = i + 1; j < i + N; j++) {
if (name[j % N] != compare[j % N]) {
right = j - i;
index = j % N;
break;
}
}
for (int j = i - 1; j > i - N; j--) {
if (name[(N + j) % N] != compare[(N + j) % N]) {
left = i - j;
if(left < right) index = (N + j) % N;
break;
}
}
answer += min(left, right);
return index;
}
int solution(string name) {
answer = 0;
int N = name.length();
int a_num = 'A' - '0';
string compare(N, 'A');
int i = 0;
while (name != compare) {
if(name[i] == compare[i]) i = check_move(N, i, name, compare);
if (name[i] != 'A') {
int move = (name[i] - '0') - a_num;
if (move > 13) move = 26 - move;
answer += move;
compare[i] = name[i];
}
}
return answer;
}
