오늘은 이 패스트캠퍼스 네카라쿠배 과정을 시작한 뒤로 처음으로 오프라인으로 모여서 수업을 진행하였다. 오전 10시까지 성수에 있는 패스트캠퍼스에 도착을 하여 강의실에 들어가서 오프라인 OT 교육을 받았다.
OT에서는 오프라인 수업과 관련한 지침에 대해서 설명하였고, 출석과 관련한 시프티 앱을 다운받고 사용하는 방법 등등에 대한 교육을 받았다.
OT교육을 받고나서 점심먹기 전인 1시까지 개인시간이어서 여기에서 나누어준 알고리즘 문제를 풀고 1시가 되어 점심을 먹고 2시부터 자료구조/알고리즘 수업을 진행하였다.
아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
문자열과 해싱
숫자 통일
문제
0과 1로 구성된 문자열이 주어졌을 때 연속되는 구간을 0또는 1로 바꾸어 0으로만 이루어진, 1로만 이루어진 문자열을 만들 때 바꾸는 최소 횟수는?
📌 내가 푼 방법
function solution(s) {
let answer;
let zeroToOne = 0;
let OneTozero = 0;
let cnt = 0;
for(let i = 0; i < s.length; i++)
{
if(cnt > 0)
{
if(s[i] === '0') {
} else {
zeroToOne++;
cnt = 0;
}
}
else {
if(s[i] === '0') {
cnt++;
}
}
if((i === s.length-1) && (s[i] === '0')) {
zeroToOne++;
}
}
cnt = 0;
for(let i = 0; i < s.length; i++)
{
if(cnt > 0)
{
if(s[i] === '1') {
} else {
OneTozero++;
cnt = 0;
}
}
else {
if(s[i] === '1') {
cnt++;
}
}
if(i === s.length-1 && s[i] === '1') {
OneTozero++;
}
}
answer = Math.min(zeroToOne, OneTozero);
return answer;
}
console.log(solution("100001111"))나는 문제를 풀 때, 변수를 0에서 1로 바꾸는 것 하나와 1에서 0으로 바꾸는 것 하나 이렇게 총 2개를 선언하여 바꾸는 원소가 연속되어있는 지 체크를 하여 연속되어 있는 것을 구분하여 zeroToOne과 OneTozero의 값들을 증가시켜 최소 값을 찾아서 문제를 해결하였다. 하지만 코드가 너무 지저분한 것 같다.
📌 강사님 방법
function solution(s) {
let answer;
let zero = 0;
let one = 0;
if (s[0] === "1") one++;
else zero++;
for (let i = 1; i < s.length; i++) {
if (s[i - 1] !== s[i]) {
if (s[i] === "1") one++;
else zero++;
}
}
answer = Math.min(one, zero);
return answer;
}
console.log(solution("10010111100"));강사님의 코드를 보면 처음 문자열의 원소를 파악하여 0이면 zero 변수의 값을 증가시키고, 1이면 one 변수의 값을 증가시키고 시작한다.
그 뒤로 s[i-1]와 s[i]를 비교하여 두 원소가 다른 경우 그 다른 원소의 변수의 값을 증가 시킨다.
이렇게 푸는 것이 조금 더 깔끔한것 같다.
상태 변화
문제
0과 1로 구성된 문자열이 주어지면
1. 0 또는 1의 위치 바꾸기
2. 0을 1로 바꾸거나 1을 0으로 바꾸기
초기상태가 11000111문자열이 주어지고, 목표상태가 11100110인 문자열이 주어지면 초기상태의 문자열에서 목표상태로 변화시키기 위한 최소 횟수는?
📌 내가 푼 방법
function solution(s1, s2) {
let answer = 0;
let s1Arr = [];
let s2Arr = [];
let s1zeroCount = 0;
let s2zeroCount = 0;
let difference = 0;
for (let i = 0; i < s1.length; i++)
{
if(s1[i] !== s2[i]) {
s1Arr.push(s1[i]);
s2Arr.push(s2[i]);
if(s1[i] === '0') {
s1zeroCount++;
}
if(s2[i] === '0') {
s2zeroCount++;
}
}
}
difference = Math.abs(s1zeroCount - s2zeroCount);
answer += difference;
if(difference !== 0) {
if(s1zeroCount < s2zeroCount) {
let i = 0;
while(difference !== 0) {
if(s1[i] === '1') {
s1[i] = '0';
difference--;
i++;
}
}
} else {
let i =0;
while(difference !== 0) {
if(s2[i] === '1') {
s2[i] = '0';
difference--;
i++;
}
}
}
for (let i = 0; i < s1Arr.length; i++)
{
if(s1[i] === s2[i]) {
s1Arr.splice(i, 1);
s2Arr.splice(i, 1);
}
}
}
answer += s1Arr.length / 2;
return answer;
}
console.log(solution("11000111", "11100110"));풀 때 굉장히 생각을 많이 했던 문제였다. 우선 문제를 보기 쉽게하기 위해 s1과 s2의 같은 인덱스의 같은 원소는 제외하고 다른 원소를 다른 배열에 넣었다.
그 후에 s1과 s2의 0과 1의 개수가 똑같아야지 문자열을 원하는 형태로 만들 수 있으므로 0과 1의 개수를 맞추기 위해 그 카운트 만큼은 문자열에서 임의로 0에서 1이나 1에서 0으로 바꿔야 하므로 answer에 더해준다.
마지막으로 [1, 0] , [0, 1]과 같이 위치가 다른경우 대충 계산을 해보니 배열의 길이가 2의 배수일 때마다 1개 씩 늘어난다, 즉 배열의 길이가 2인경우 1번 위치를 옮겨주어야하고 3인경우도 1, 4인 경우 2, 5인 경우 2, 6인경우 3 이렇게 증가하기때문에 s1Arr.length / 2만큼 answer에 더해준다.
📌 강사님 방법
function solution(s1, s2) {
let zero = 0, one = 0;
for (let i = 0; i < s1.length; i++) {
if(s1[i] !== s2[i]) {
if(s1[i] === '0') zero++;
else one++;
}
}
return Math.abs(zero - one) + Math.min(zero, one);
}둘이 다른 개수를 세어서(zero, one) 그것만큼 뺀값을 더해주고 다른 원소들만큼 최소 위치를 바꾸어주어야 해서 Math.min(zero, one)을 더해 준다
이게 더 쉬운 방법인것 같다.
핵심풀이 --> 다른거 세주고 바꿔야할거 Math.min(zero, one) 더해주기
접미사 정렬
문자열 s가 주어지면 s문자열의 모든 접미사를 구하고 사전순으로 출력하라.
📌 내가 푼 방법
function solution(s) {
let answer = [];
let sArr = s.split("");
for (let i = 0 ; i<s.length; i++)
{
answer.push(sArr.join(""));
sArr.splice(0, 1);
}
return answer.sort();
}
console.log(solution("kseaedu"));우선 받은 문자열을 배열화 시킨후에 그 값을 answer배열에 푸시를 하고 앞에서 한 개의 원소를 잘라서 다시 푸시를 하여 answer배열을 만든다.
그 이후에 answer배열을 sort하여 출력한다.
📌 강사님 방법
function solution(s) {
let answer = [];
for(let i = 0; i<s.length; i++)
{
answer.push(s.substring(i,s.length))
}
return answer.sort();
}
console.log(solution("kseaedu"));substring함수를 이용하여 문자열을 answer배열에 넣고 마찬가지로 sort!
공통문자가 없는 단어
N개의 문자열이 주어지면 서로 공통문자가 없는 두 문자열을 선택해 두 문자열의 길이를 곱했을 때 최댓값을 출력하라.
📌 내가 푼 방법
function solution(arr)
{
let answer = 0;
let currentValue;
let compareArr;
let compareLength;
let compareValue = 0;
for (let i = 0; i<arr.length; i++)
{
currentValue = arr[i].split("");
for(let j = i+1; j<arr.length; j++)
{
compareArr = arr[j].split("");
compareLength = currentValue.filter(x => compareArr.includes(x));
if(compareLength.length === 0)
{
compareValue = currentValue.length * compareArr.length;
}
answer = Math.max(answer, compareValue);
}
}
return answer;
}
const arr = ["kk", "k", "kkk", "kkkkk", "kkkk"];
console.log(solution(arr));서로 공통된 원소가 있는 지, 찾기 위해 filter와 includes를 활용하여 compareLength에 공통된 원소가 있으면 넣고, 없으면 그 두개의 배열을 곱해주는 방법으로 최대값을 찾아 비교하여 answer에 넣어서 풀었다.
📌 강사님 방법
function isUnique(short, long) {
for (let x of short) {
if (long.indexOf(x) !== -1) {
return false;
} else {
return true;
}
}
}
function solution(words) {
let answer = 0;
let len = words.length;
words.sort((a, b) => a.length - b.length);
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
if (isUnique(words[i], words[j])) {
let tmp = words[i].length * words[j].length;
answer = Math.max(answer, tmp);
}
}
}
console.log(words);
return answer;
}
const arr = ["skudy", "kstue", "time", "back", "good"];
console.log(solution(arr));isUnique라는 함수를 만들어 배열의 원소가 다른 배열의 원소에 있는 지 확인을 해주어 없으면 true를 반환하여 최대값을 찾는 방법으로 풀음.
회문문자열2
문자열 s가 주어지면 s가 최대 문자 1개까지 지워서 회문문자열이 되면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하라
📌 내가 푼 방법
function solution(s)
{
let answer;
let leftValue;
let rightValue;
let compareValue = 0;
let sArr = s.split("");
let arrLength;
for (let i = 0; i < parseInt(s.length / 2, 10); i++)
{
leftValue = sArr.shift();
rightValue = sArr.pop();
if(leftValue === rightValue) {
answer = "YES";
continue;
} else {
answer = "NO";
break;
}
}
if (answer == "YES") {
return answer;
}
for (let i = 0; i < s.length; i++)
{
sArr = s.split("");
arrLength = sArr.length;
sArr.splice(i, 1);
for(let j = 0; j<parseInt((arrLength-1) /2, 10); j++) {
leftValue = sArr.shift();
rightValue = sArr.pop();
if(leftValue === rightValue) {
compareValue++;
if(sArr.length === 1) {
compareValue++;
break;
}
} else {
answer = "NO";
break;
}
}
if (compareValue >= parseInt(((arrLength-1) / 2))) {
answer = "YES";
break;
}
compareValue = 0;
}
return answer;
}
const s = "abcacbakcba";
console.log(solution(s))회문 문자열인지 판단히기 위해 처음엔 길이의 반만큼 왼쪽값과 오른쪽 값을 비교하면서 확인한 뒤 없으면 문자열 원소를 하나하나 잘라가면서 그 제외된 문자열이 회문문자열인지 판단하여 compareValue를 세어 배열의 길이와 비교하였다.
너무 복잡하게 문제를 푼 것 같다.
📌 강사님 방법
function solution(s) {
let answer = "YES";
let lt = 0,
rt = s.length - 1;
while (lt < rt) {
if (s[lt] !== s[rt]) {
let s1 = s.substring(lt, rt);
let s2 = s.substring(lt + 1, rt + 1);
if (s1.split("").reverse().join("") !== s1 && s2.split("").reverse().join("") !== s2) {
answer = "NO";
}
break;
} else {
lt++;
rt--;
}
}
return answer;
}
console.log(solution("aebccba"));최대 문자 1개까지 지워서 회문 문자열이 되면 YES라고 하였으므로 s[lt]와 s[rt]가 서로 다른 값이라고 할 때, lt와 rt중 회문 문자열이 어느 것이 아닌 지 체크를 하기 위해 if문을 다음과 같이 작성해준 후 1개 지우는 것만으로 안될 때는 answer="NO"를 하고 while문을 종료한다.
학급 회장
학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 하였다.
투표후 문자열이 다음과 같이 제공 되며("BACBACCACCBDEDE") 가장 많은 득표수를 받은 후보를 출력해라.
📌 내가 푼 방법
function solution() {
let answer;
let sArr = s.split("");
let index = 0;
let maxVote = 0;
const sObject = sArr.reduce((acc, cur) => {
if(acc[cur]) {
acc[cur]++;
} else {
acc[cur] = 1;
}
return acc;
}, {})
for(let i = 0; i<Object.values(sObject).length; i++)
{
if(Object.values(sObject)[i] > maxVote)
{
maxVote = Object.values(sObject)[i];
index = i;
}
}
answer= Object.keys(sObject)[index];
return answer;
}
const s = "BACBACCACCBDEDE"
console.log(solution(s));reduce함수를 이용하여 각 후보를 키로, 받은 투표수를 value로하여 객체를 생성한다음, 객체의 값들을 조회하여 가장 큰 값의 index를 가져와 그 index에 있는 key를 출력하였다.
📌 강사님 방법
function solution(s) {
let answer;
let sh = new Map();
for (let x of s) {
sh.set(x, sh.get(x) + 1 || 1);
}
let max = 0;
for (let [key, val] of sh) {
if (val > max) {
max = val;
answer = key;
}
}
return answer;
}
console.log(solution("BACBACCACCBDEDE"));map이라는 함수를 처음보는데 map은 키가 있는 데이터를 저장한다는 점에서 객체와 유사하지만 map은 키에 다양한 자료형을 허용한다는 점에서 차이가 있다.
map은 다음과 같은 함수를 사용할 수 있다.
map을 사용하여 reduce에서 값이 없으면 키와 value를 생성한것 같이 js의 단축 평가 논리 계산법을 통해 sh에 x라는 원소가 없으면 1로, 있으면 sh.get(x)(x키의 값을 가져와 1을 더해줌) + 1로 계산을 해준다.
그 이후로 [key, val]접근을 통해 값이 max일때의 key를 저장 후 반환한다.
// let sh = new Map();
// sh.set(b, 1) --> b를 키로 1을 값으로
// get(b) -- > 키로 값가져오는거
// delete(b) --> 키를 없앰
// sh.has('B') --> B라는 키가 존재하냐?
// sh.size() -- >키의 개수
// map접근시 for (let [key,val] of sh)와 같이
아나그램
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 아나그램인지 아닌지 "YES" OR "NO"로 출력하여라.
알파벳과 그 개수가 모두 일치하는 것 --> 아나그램
(문자열의 길이가 다르면 아나그램이 아님! --> 필수 조건)
📌 내가 푼 방법
function solution(s1, s2) {
let answer = "YES";
let s1Arr = s1.split("");
let s2Arr = s2.split("");
s1Arr.sort();
s2Arr.sort();
for(let i = 0; i<s1Arr.length; i++)
{
if(s1Arr[i] !== s2Arr[i]){
answer = "NO";
break;
}
}
return answer;
}
const s1 = "abaCC";
const s2 = "Caaab";
console.log(solution(s1, s2));두 문자열을 배열화 시킨 후 sort를 하여 배열을 탐색을 하면서 같은 값이 한번이라도 안나오면 NO를 반환시키고 그렇지 않을 경우 YES를 반환시킨다.
📌 강사님 방법
function solution(s1, s2) {
let answer = "YES";
let sh = new Map();
for (let x of s1) {
sh.set(x, sh.get(x) + 1 || 1);
}
for (let x of s2) {
if (!sh.has(x) || sh.get(x) === 0) {
return "NO";
} else {
sh.set(x, sh.get(x) - 1);
}
}
return answer;
}
const s1 = "abaCC";
const s2 = "Caaab";
console.log(solution(s1, s2));map을 이용하여 s1의 정보를 담고 있는 객체를 만들고 그 이후 s2를 돌면서 s1의 정보가 담긴 객체에서 키에 따른 value를 제거해 나가면서 value가 맞지 않거나 키가 없는 경우 NO를 반환시키고 그렇지 않을경우 값에서만 -1을 해준다.
문자열 구분하기
N개의 문자열이 주어지면 모든 문자열을 구분할 수 있는 최소길이 접두어를 찾아라.
"abcdef", "abdfer", "abowls" 와 같은 문자열이 배열안에 존재할 시 "ab"로는 문자열을 구분할 수 없고, 3번째 문자열부터 구분할 수 있어서 3을 반환하면 됨.
📌 내가 푼 방법
function solution(words)
{
let answer = 100;
let minCount = 0;
let arr = new Array(words.length);
for(let i = 0; i < words.length; i++)
{
arr[i] = words[i].split("");
}
for(let i = 0; i < words.length-1; i++)
{
for(let j = 0; j<words[i].length; j++)
{
if (arr[i][j] === arr[i+1][j]) {
minCount++;
} else {
break;
}
}
answer = Math.min(answer, minCount);
minCount = 0;
}
return answer+1;
}
const words = ["longlong", "longtong", "longbig"];
console.log(solution(words));words배열을 2차원 배열로 만들어 모든 요소 하나하나에 접근할 수 있도록 만든 후에 배열의 원소를 하나하나 비교해 가면서 원소가 같은 경우 minCount를 센 후 다른 값이 나오면 바로 종료시키고 answer와 minCount의 최소값을 비교하여 저장 한후 마지막에 +1을 해주어 그 인덱스에서부터 문자열을 구분할 수 있게 만들었다.
📌 강사님 방법
function solution(words) {
let answer, i;
let sH = new Map();
for (i = 0; i < words[0].length; i++) {
let flag = true;
for (let j = 0; j < words.length; j++) {
let x = words[j].substring(0, i + 1);
if (sH.has(x)) {
flag = false;
break;
}
sH.set(x, 1);
}
if (flag) break;
}
answer = i + 1;
return answer;
}
const words = ["seeasue", "sesseysu", "semeas"];
console.log(solution(words));map을 사용하여 words안의 원소들을 0부터 비교해가면서 원소가 안에 있으면 flag를 false로 한뒤 break로 바로 다음 for문(i를 조건으로 하는)을 실행시키고 한번이라도 구분할 문자가 나오지 않는 경우 flag가 true이기 때문에 자동으로 break가 되어 그 문자열 길이만큼의 i가 나오고 거기에 +1을 해준다.
