일곱난장이 문제
문제 : 9명의 난장이들이 자신들이 진짜 일곱난장이라 주장한다. 진짜 일곱난장이는 가지고 있는 배지숫자의 합이 100이다. 다른 숫자를 가지고 있는 2명의 가짜를 제외한 진짜 일곱난장이의 숫자를 출력해라.
나는 이 문제를 봤을 때 9명중 7개를 뽑아서 그 합이 100이 되면 출력해라. 이런식으로 코드를 짜려고했다. 하지만 일단 순열, 조합을 아직도 코드로 제대로 짤 줄 모른다..(재귀함수가 어렵다..)
해답을 봤을 때는 조합이 없어도 문제를 풀 수 있어서 충격이었다.
해답 :
function answer(dwarf) {
let result = [];
// 1. 9명(배열 총 합) = 7명(100) + 2명(faker 합)
// 9명 - 7명 = 2명에 대한 합 숫자
let sum = 0;
for (let i = 0; i < dwarf.length; i++) {
sum += dwarf[i];
}
sum -= 100; // -> faker 2명에 대한 배지값
// 2. for 두 요소의 합이 faker 2명에 대한 합 숫자과 같은지 비교 -> i, j
let faker = [];
for (let i = 0; i < dwarf.length; i++) {
for (let j = i + 1; j < dwarf.length; j++) {
if (sum == dwarf[i] + dwarf[j]) {
faker[0] = i;
faker[1] = j;
break;
}
}
if (faker.length != 0) break;
}
// 3. faker 두명을 제외하고 나머지 배지값을 result에 넣어준다
let count = 0;
for (let i = 0; i < dwarf.length; i++) {
if (faker[0] != i && faker[1] != i) {
result[count++] = dwarf[i];
}
}
return result;
}이 글에 있는 모든 해답들은 최대한 메서드를 사용하지 않고 배열의 index를 공부하기 위해 쓰여졌기때문에 조금 길다고 느낄 수 있다. 하지만 2번에 이중 for문을 통해 조합에 대해서 조금 더 알게 되었다.
Two Sum
문제 : 하나의 배열과 숫자를 받아서 배열 내의 숫자 두 개로 input의 숫자를 만들고, 그 숫자 두 개의 index를 반환해라. input의 숫자를 만들 수 있는 두 개의 숫자 조합은 한 개이다. index는 오름차순으로 정렬해서 반환해라.
나의 답변 :
function answer(nums, target) {
let result = [];
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result.push(i, j);
}
}
}
result.sort((a, b) => a - b);
return result;
}
나는 이중 for문을 이용하여 문제를 풀었다. 문제를 풀었음에도 이 문제를 넣은 이유는 해답은 최적화까지 했기때문이다. 나의 답변은 O(N^2)이니까 그리 좋은 최적화는 아니다 ㅜ
해답 :
function answer(nums, target) {
let map = {}; // key, value
for (let i = 0; i < nums.length; i++) {
if (map[target - nums[i]] != undefined) {
return [map[target - nums[i]], i];
}
map[nums[i]] = i;
}
return [];
}
map이라는 object를 이용하여 key,value값을 받고 target - nums[i]가 map안에 있느냐 없느냐로 판단하여 index를 찾는다. 저렇게만 보면 약간 이해가 안가서 하나하나 따라가봤다.
//input으로 들어온 값이 [[5, 2, 7, 9, 4, 12], 6] 일때,
for (let i = 0; i < nums.length; i++) {
if (map[target - nums[i]] != undefined) {
return [map[target - nums[i]], i];
}
map[nums[i]] = i;
}
i = 0 => map = {}이니까 {'5' : 0} 결국 값과 그 값의 index값이 map에 저장되는 것이다.
i = 1 => map = {'5' : 0} undefined 여서 {'2' : 1, '5' : 0}
i = 2 => map = {'2' : 1, '5' : 0} undefined 여서 {'7' : 2, '2' : 1, '5' : 0}
i = 3 => map = {'7' : 2, '2' : 1, '5' : 0} undefined 여서 {'9' : 3, '7' : 2, '2' : 1, '5' : 0}
i = 4 => map = {'9' : 3, '7' : 2, '2' : 1, '5' : 0}, 6(target)-4(nums[4]) = 2 undefined가 아니기 때문에 [1, 4]를 반환한다.
OX문제
문제 : 답을 맞춘경우 1, 답을 틀렸을 경우 0이라고 써놓은 배열을 받아 채점한다. 답을 맞췄을 때는 1점이고, 연속으로 맞췄을 경우 연속된만큼 1점을 더해서 총점을 반환한다. ( 예시 : [1,0,0,1,1,1]경우 1,0,0,1,2,3점으로 계산한다.)
나의 답변 :
function answer(mark) {
let result = 0;
for (let i = 0; i < mark.length; i++) {
if (mark[i] == 1) {
result += 1;
for (let j = i - 1; mark[j] > 0; j--) {
if (mark[j] == 1) result += 1;
}
}
}
return result;
}나는..이중for문으로 문제를 풀었는데..해답은 또 엄청 간단했다.(현타..)
해답 :
function answer(mark) {
let result = 0;
// 1 -> 1점, 연속한 1인 경우 연속한 count 만큼 점수 추가
let score = 0;
for (let i = 0; i < mark.length; i++) {
if (mark[i] == 1) {
result += ++score;
} else {
score = 0;
}
}
/**
* 0 -> 1: result(1), score(1)
* 1 -> 0: result(1), score(0)
* 2 -> 1: result(2), score(1)
* 3 -> 1: result(4), score(2)
* 4 -> 1: result(7), score(3)
* 5 -> 0: result(7), score(0)
* 6 -> 1: result(8), score(1)
* 7 -> 1: result(10), score(2)
*/
return result;
}가산점인 score을 이용하여서 풀면 for문 하나로도 충분히 풀 수 있는 문제였다 ㅜ
달팽이 만들기 문제
문제 : 입력받은 숫자의 크기만큼의 정사각형 배열에 숫자를 달팽이 모양을 넣어서 반환해라.
예시) input이 4일 경우
[[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]
(간격이 안맞지만 정사각형모양 맞다..)
나는 일단 저 달팽이 모양의 패턴을 찾지 못해서 문제를 못 풀었다. 패턴도 패턴이지만 숫자를 넣을 때, 어떻게 방향을 바꿔서 넣어야할지..(push, unshift밖에 모르는데ㅜㅜ) 막막했다.
해답 :
function answer(length) {
let result = [];
// 1. result => 2차원 배열
for (let i = 0; i < length; i++) {
result[i] = [];
}
/** 2. 반복문 패턴 구현
* 1) length 길이만큼 시작해서 숫자를 채워준다.
* 2) length - i, 방향, 2회
* 3) length == 0, 프로그램이 멈춘다.
*/
let direction = 1;
let x, y, num;
x = y = num = 0;
x--;
while (1) {
for (let i = 0; i < length; i++) {
x += direction;
result[y][x] = ++num;
}
length--;
if (length <= 0) break;
for (let j = 0; j < length; j++) {
y += direction;
result[y][x] = ++num;
}
direction *= -1;
}
return result;
}패턴은 방향을 바꿔가며 length - 1만큼 숫자를 채워간다는 것이었다. 방향을 바꾸는 방법은 2차원 배열을 x축 y축으로 생각해서 index를 잡고, 방향을 바꿀때마다 바꾸는 축에다 -를 붙이는 것이었다. while안에다가 for문을 넣는 건 생각 못했는데, while문을 잘 활용할 수 있게 예시를 많이 찾아봐야겠다 ㅜ
