Homile

https://www.acmicpc.net/problem/1244

8
0 1 0 1 0 0 0 1
2
1 3
2 3

1 0 0 0 1 1 0 1

문제풀이(1)

4번째 부터 들어오는 입력 값은 학생성별, 학생이 받은수가 주어진다.
이때, 학생의 성별이 남성이라면 받은 수의 배수의 스위치의 상태를 바꾼다.
자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서,
그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.
위의 조건대로 풀어나가면 된다.
남학생의 경우는 자신이 주어진 번호의 배수에만 스위치를 변경하면 되지만
여학생의 경우 자신이 주어진 번호 + 주변번호까지 변경하는 로직을 구현하면 문제는 해결된다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, switchs, studentsNum, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const switchsArr = switchs.split(" ").map(Number);
const studentTypeAndNumber = arr.map((student) => student.split(" ").map(Number));

// 학생의 스위치 조작 함수
const action = (type, number, switchsArr) => {
  // 남학생 스위치 조작
  if (type === 1) {
    for (let i = 0; i < switchsArr.length; i++) {
      if ((i + 1) % number === 0) {
        switchsArr[i] = switchsArr[i] === 0 ? 1 : 0;
      }
    }
  }

  // 여학생 스위치 조작
  if (type === 2) {
    // 주어진 번호 스위치 변경
    switchsArr[number - 1] = switchsArr[number - 1] === 0 ? 1 : 0;

    for (let i = 1; i < switchsArr.length; i++) {
      // 좌우가 비대칭일 경우 정지
      if (switchsArr[number - 1 - i] !== switchsArr[number - 1 + i]) {
        break;
      } else {
        let ChangeSwitchState = switchsArr[number - 1 - i] === 0 ? 1 : 0;
        switchsArr[number - 1 - i] = ChangeSwitchState;
        switchsArr[number - 1 + i] = ChangeSwitchState;
      }
    }
  }
};

studentTypeAndNumber.forEach((value) => {
  const [type, number] = value;
  action(type, number, switchsArr);
});

const answer = [];

while (switchsArr.length > 0) {
  answer.push(switchsArr.splice(0, 20).join(" "));
}

console.log(answer.join("\n"));

문제풀이(2) - 리팩토링

1. 재사용성을 올리기 위해 남학생과 여학생의 스위치 조작 함수 분리 및 스위치 상태 변경 함수 추가
2. 변수명 직관적으로 변경

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, switchs, studentsNum, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const switchStateArray = switchs.split(" ").map(Number);
const studentTypeAndNumber = arr.map((student) => student.split(" ").map(Number));

// 스위치 변경 함수
const flipSwitch = (index, switchStateArray) => {
  switchStateArray[index] = switchStateArray[index] === 0 ? 1 : 0;
};

// 남학생 스우치 변경
const maleStudentAction = (number, switchStateArray) => {
  for (let i = 0; i < switchStateArray.length; i++) {
    if ((i + 1) % number === 0) {
      flipSwitch(i, switchStateArray);
    }
  }
};

// 여학생 스위치 변경
const femaleStudentAction = (number, switchStateArray) => {
  flipSwitch(number - 1, switchStateArray);

  for (let i = 1; i < switchStateArray.length; i++) {
    if (switchStateArray[number - 1 - i] !== switchStateArray[number - 1 + i]) {
      break;
    } else {
      flipSwitch(number - 1 - i, switchStateArray);
      flipSwitch(number - 1 + i, switchStateArray);
    }
  }
};

studentTypeAndNumber.forEach((value) => {
  const [type, number] = value;
  type === 1 ? maleStudentAction(number, switchStateArray) : femaleStudentAction(number, switchStateArray);
});

const answer = [];

while (switchStateArray.length > 0) {
  answer.push(switchStateArray.splice(0, 20).join(" "));
}

console.log(answer.join("\n"));

https://www.acmicpc.net/problem/1302

5
top
top
top
top
kimtop

top

문제풀이(1)

많이 팔린 책의 이름을 찾는 문제이다.
map객체를 사용해서 책들의 개수를 카운트 한다음 많이 나온 책을 출력하면 될 것 같다.
우선 팔린수가 같은 책이 여러개 일 경우 사전순으로 나타내야 하기 때문에 먼저 정렬을 실행한다.
많이 팔린 책의 수를 찾고 map을 순회하면서 가장 많이 팔린 책을 출력하면된다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const map = new Map();

let maxCount = 0;
let answer = "";

// 사전순으로 정렬
arr.sort();

arr.forEach((book) => {
  if (map.has(book)) {
    map.set(book, map.get(book) + 1);
  } else {
    map.set(book, 1);
  }

  let bookCount = map.get(book);
  if (bookCount > maxCount) {
    maxCount = bookCount;
  }
});

for (const [key, value] of map.entries()) {
  if (value === maxCount) {
    answer = key;
    break;
  }
}

console.log(answer);

문제풀이(2)

1. map 객체 대신 일반 객체를 사용하여 메소드 사용을 최소화 한다.
2. 반복문을 줄일 수 있도록 팔린 책의 수를 카운트 하면서 제일 많이 팔린 책을 동시에 찾는다.
메모리 - 9344kb -> 9348kb
실행시간 - 120ms -> 116ms

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

let answer = "";

// 사전순으로 정렬
arr.sort();

const obj = {};

arr.forEach((book) => {
  obj[book] = (obj[book] || 0) + 1;

  if (!answer || obj[book] > obj[answer]) {
    answer = book;
  }
});

console.log(answer);

https://www.acmicpc.net/problem/1748

5

5

15

21

120

252

문제풀이(1)

수의 범위가 1억까지이기 때문에 for로 전체 순회를 할 경우 시간초과가 날것으로 예상된다.
수의 자릿수를 구하는 공식을 작성하여 구해본다.
1~9는 한자리수, 10~99는 두자리수, 100~999는 세자리수이다.
위의 규칙성을 봤을 때 1의 자리수부터 10의 배수로 자리수를 계산할 수 있음을 알 수 있다. (1 -> 10 -> 100 -> 100)
N - (자리수) + 1 = 자리수의 개수이다.
15 -> 15 - 1 + 1 = 15 = 한자리수의 개수
15 -> 15 - 10 + 1 = 6 = 두자리수의 개수
위와 같은 형식으로 규칙성을 가질 수 있다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());

let answer = 0;

for (let i = 1; i <= N; i *= 10) {
  answer += N - i + 1;
}

console.log(answer);

https://www.acmicpc.net/problem/3036

3
8 4 2

2/1
4/1

문제풀이(1)

문제의 풀이가 생각나지 않아서 찾아본 결과 최대공약수를 이용한 문제라는 것을 알게되었다.
2수의 최대공약수를 찾아서 기약분수(?)의 형태로 출력한면 된다고 한다.
첫번째 링이 돌아가면 나머지 링도 돌기 때문에 첫번째 링과 나머지 링의 최대공약수를 찾아 기약분수의 형태로 나타내면 된다.
최대공약수는 유클리드 호제법을 사용해서 구하는 방식을 사용하려고 한다.
8과 4의 최대 공약수 = 4 -> (8/4)/(4/4) -> 2/1
8과 2의 최대 공약수 = 2 -> (8/2)/(2/2) -> 4/1

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const arr = input[0].split(" ").map(Number);
const firstNum = arr[0];

// 유클리드 호제법 최대공약수 구하기
const gcd = (a, b) => {
  if (a % b === 0) {
    return b;
  }
  return gcd(b, a % b);
};

for (let i = 1; i < N; i++) {
  const nowNum = arr[i];
  const resultGCD = gcd(firstNum, nowNum);
  console.log(`${firstNum / resultGCD}/${nowNum / resultGCD}`);
}

https://www.acmicpc.net/problem/9613

3
4 10 20 30 40
3 7 5 12
3 125 15 25

70
3
35

문제풀이(1)

최대공약수(Greatest Common Divisor, GCD)를 구하는 문제이다.
GCD를 구하는 알고리즘에는 유클리드 호제법이 있다.
유클리드 호제법을 구현하여 가능한 모든 쌍의 GCD의 합을 구하면된다.
유클리드 호제법
1. 두 수 중 큰 수를 a, 작은 수를 b로 둡니다.
2. a를 b로 나눈 나머지를 r로 둡니다.
3. a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.
4. b가 0이 될 때까지 2번과 3번의 과정을 반복합니다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [T, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

const arrSort = arr.map((value) => value.split(" ").map(Number));

const gcd = (a, b) => {
  if (a % b === 0) {
    return b;
  }
  return gcd(b, a % b);
};

const answer = [];

arrSort.forEach((numbers) => {
  const [N, ...nums] = numbers;
  let sum = 0;
  for (let i = 0; i < N - 1; i++) {
    for (let j = i + 1; j < N; j++) {
      sum += gcd(nums[i], nums[j]);
    }
  }
  answer.push(sum);
});

console.log(answer.join("\n"));

https://www.acmicpc.net/problem/17219

16 4
noj.am IU
acmicpc.net UAENA
startlink.io THEKINGOD
google.com ZEZE
nate.com VOICEMAIL
naver.com REDQUEEN
daum.net MODERNTIMES
utube.com BLACKOUT
zum.com LASTFANTASY
dreamwiz.com RAINDROP
hanyang.ac.kr SOMEDAY
dhlottery.co.kr BOO
duksoo.hs.kr HAVANA
hanyang-u.ms.kr OBLIVIATE
yd.es.kr LOVEATTACK
mcc.hanyang.ac.kr ADREAMER
startlink.io
acmicpc.net
noj.am
mcc.hanyang.ac.kr

THEKINGOD
UAENA
IU
ADREAMER

문제풀이(1)

주소와 비밀번호가 매칭돠어 있는 N중에서 M에 속한 주소의 비밀번호를 찾아내면 되는 문제이다.
map에 주소와 비밀번호를 매칭해서 저장한다음 M배열에서 찾아내면 될 것이다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);

const addreesAndPassword = input.slice(0, N);
const address = input.slice(N);

const map = new Map();

const answer = [];

for (let i = 0; i < N; i++) {
  const [address, password] = addreesAndPassword[i].split(" ");
  map.set(address, password);
}

for (let i = 0; i < M; i++) {
  answer.push(map.get(address[i]));
}

console.log(answer.join("\n"));

문제풀이(2) - 리팩토링

변수명 수정
비밀번호 찾는 로직 함수로 변경

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);

const addressesAndPassword = input.slice(0, N);
const addresses = input.slice(N);

const map = new Map();

const answer = [];

for (let i = 0; i < N; i++) {
  const [address, password] = addressesAndPassword[i].split(" ");
  map.set(address, password);
}

const getPassword = (address) => {
  return map.get(address);
};

for (const address of addresses) {
  answer.push(getPassword(address));
}

console.log(answer.join("\n"));