짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S =baabaa라면
baabaa →bbaa →aa→
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
2. 제한 사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.
3. 입출력 예제
s
result
baabaa
1
cdcd
0
4. 나의 접근 방식
처음에는 split으로 모든 문자를 나누어 보았다.
이후, 가장 처음 문자를 보고 두번째 문자와 비교해서 같으면 shift 두 번으로 빼버리려고 했다. 완전히 실패.
실패한 코드
function solution(s) {
let splitStr = s.split('');
for(let i = 0; i < splitStr.length; i++) {
let first = splitStr[i];
if(first === splitStr[i + 1]) {
splitStr.shift();
splitStr.shift();
}
else {
// 맞지 않으면 다시 뒤로 넣어준다.
splitStr.push(first);
}
}
// 한번 이상 검사할 수 없기 때문에 무조건 0이 나온다.
if(splitStr.length === 0) return 1;
else return 0;
}
그런대 잘 생각해 보니 앞에서부터 할 필요가 없이, 스택처럼 쌓아서 뒤부터 보고 연속으로 같은 문자가 들어오면 뒤를 빼버리면 될 것이라고 생각했다.
4. 결과
function solution(s) {
// 스텍으로 쓸 빈 배열을 만든다.
let arr = [];
for(let i = 0; i < s.length; i++) {
// 각 요소들을 넣어주면서
arr.push(s[i]);
// 뒤부터 들어온 스텍에 똑같은 문자가 연속해서 들어 온다면,
if(arr[arr.length - 1] === arr[arr.length - 2]) {
// 두개를 빼 버린다.
arr.pop();
arr.pop();
}
}
// 반복문을 다 돌고 나서, 스텍이 비어 있다면 전부 제거가 된 것이다.
if(arr.length === 0) return 1;
// 만약, 겹치지 않았다면 스텍에는 요소가 남아 있을 것이므로, 0을 반환한다.
else return 0;
}
5. 개선점이 있다면?
위의 방법으로도 왠지 풀 수 있을 것 같다...! (물론, 쉽지도 않고 효율도 떨어질 것이다)
다양한 방식의 문제를 접하고, 어떻게 풀어야 할 지 더 다양한 방법으로 생각하는 것이 중요할 것 같다.
조금 실수가 있었었다. 위의 문제는 split을 쓰면 올바르게 답을 작성해도 시간 초과가 나와서 테스트를 실패한다. 굳이, split을 쓰지 않고, 문자열 상태 그대로 반복문으로 해결할 수 있는 부분인데, pop과 같은 배열에서 사용할 수 있는 함수를 사용하려고 바꿨던 것이다. 이런 식으로 필요 없는 함수의 사용을 줄여 효율성을 생각하는 것도 중요한 부분이 될 것이다.
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
2. 제한 사항
무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
3. 입출력 예제
people
limit
return
[70, 50, 80, 50]
100
3
[70, 80, 50]
100
3
4. 나의 접근 방식
limit를 넘기지 않는 가장 큰 수 중에 2개는 people에서 가장 큰 수와 가장 작은 수를 더 하면 된다고 생각했다.
정답은 나온다. 하지만 효율성 실패
실패한 코드
function solution(people, limit, count = 0) {
// 가장 큰 수와 가장 작은 수를 구한다.
let max = Math.max(...people);
let min = Math.min(...people);
// 제귀함수의 탈출 조건이다.
if(people.length === 0) return count;
// 둘을 더 했을때 limit보다 작으면 같이 제거한다.
if(max + min <= limit) {
count++;
people.splice(people.indexOf(max), 1)
people.splice(people.indexOf(min), 1)
}
// 보다 크다면 가장 큰 수만 제거해 준다.
if(max + min > limit) {
count++;
people.splice(people.indexOf(max), 1)
}
return solution(people, limit, count)
}
대부분의 프로그래머스 문제들의 효율성 문제는 '정렬'이 안 된 상태로 계산해서 틀리는 경우가 많았다.
그래서 일단 sort를 이용해 정렬을 해 놓고 생각해 보았다.
로직은 맞는 것 같아서 이 방식대로 정렬한 후의 index를 이용해서 문제를 해결할 수 있었다.
4. 결과
function solution(people, limit) {
let result = 0;
// 정렬해 준다.
people.sort((a,b) => b - a);
// 각각의 index를 구해준다.
// 당연히, 가장 앞이 가장 작은수, 가장 끝이 가장 큰 수가 된다.
let minIndex = 0;
let maxIndex = people.length - 1;
// 가장 작은 수의 index가 가장 큰 수의 index를 넘길때 까지 반복하며,
while(minIndex < maxIndex) {
// 둘을 더 한 수를 limit와 비교한다.
// 더 한 수가 limit보다 크면 minIndex만 늘려주고,
let sum = people[minIndex] + people[maxIndex];
if(sum > limit) minIndex++;
// 넘지 않는 다면 가장 작은수와 가장 큰 수 둘다 보트에 탈 수 있으므로,
// 같이 조절 해 준다.
else {
minIndex++;
maxIndex--;
}
// 보트가 움직인 횟수를 더 해 준다.
result++;
}
if(minIndex === maxIndex) result++;
return result;
}
