[99클럽] 코딩테스트 스터디, 8일차 TIL - 비기너

1. 문제풀이

1) 문제, 민균이의 비밀번호 (백준, 9933)

창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다.

파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다.

파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다.

그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해 냈다.

민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다.

 

예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다.

알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다.

 

민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

 

입력

- 첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다.

- 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다.

- 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

 

출력

- 첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

 

 

2) 해석

 

- 비밀번호의 길이와 가운데 글자를 출력하는 프로그램 작성

- 단어가 한 줄에 하나씩 적혀 있음 > 이 중 하나가 비밀번호

- 비밀번호 = 비밀번호를 뒤집어 쓴 문자열이 반드시 있어야 함

   > 자신을 뒤집었을 때 같거나, 글 목록 중에 뒤집은 값이 똑같은 게 있어야 함

 

- 첫째 줄 : 단어의 수 N

- N개 줄 : 파일에 적혀있는 단어가 한 줄씩 입력

 

 

이 문제도 해석에서 시간이 조금 걸렸다.

처음엔 뒤집힌 문자열이 있어야 한다길래, 예제 1번만 보고 글 목록 중에서 찾으면 되는 줄 알았다.

 

그러나 예제 2번을 보면, 그런 경우는 없는데 답이 출력된 것을 볼 수 있다.

답을 보면 5글자에 가운데가 s여야 하는데, 글 목록중에서 해당 글자는 "kisik" 밖에 없다.

따라서 자기 자신을 뒤집는 경우도 포함해야 한다.

 

 

3) 풀이

const fs = require("fs");
const input = fs.readFileSync("/div/stdin").toString().trim().split("\n");

const N = Number(input[0]);
const strArr = input.slice(1);

function handleReverse(str) {
  return str.split("").reverse().join("");
}

//자신을 뒤집었을 때,똑같은게 있는지 체크
let result = strArr.filter((str) => str === handleReverse(str))[0] || "";

//글 목록 중에, 똑같은게 있는지 체크
strArr.forEach((str, i) => {
  for (let j = i + 1; j < N; j++) {
    if (strArr[j] === handleReverse(str)) result = str;
  }
});

//길이, 가운데 숫자 리턴
const len = result.length;
console.log(len, result[Math.floor(len / 2)]);

 

비밀번호에 해당되는 조건이 2개이기 때문에, 각 조건을 따로 체크해야겠다고 생각했다. 

그래서 자신을 뒤집었을 때 같은게같은 게 있는지, 글 목록 중에 같은 게 있는지 총 2가지 작성했다.

 

const N = Number(input[0]);
const strArr = input.slice(1);

 

N을 저장해주고, strArr를 생성해 준다.

strArr는 N을 제외한 문자열 배열을 의미한다.

 

 

function handleReverse(str) {
  return str.split("").reverse().join("");
}

 

두 개의 조건 모두 뒤집어진 값과 같은지 확인해야 하기 때문 handleReverse라는 함수를 만들었다.

 

 

//자신을 뒤집었을 때,똑같은게 있는지 체크
let result = strArr.filter((str) => str === handleReverse(str))[0] || "";

 

그 후 filter를 이용해 str과 뒤집은 값이 같은 것을 찾아내 result에 저장해 준다.

만약 값이 없다면, 빈 문자열을 저장해 준다.

 

 

//글 목록 중에, 똑같은게 있는지 체크
strArr.forEach((str, i) => {
  for (let j = i + 1; j < N; j++) {
    if (strArr[j] === handleReverse(str)) result = str;
  }
});

 

그리고 forEach를 이용해 글 목록 중에 똑같은 게 있는지 체크해 준다.

 

안에 for문을 작성해서 i의 다음 인덱스부터 반대로 뒤집었을 때 같은 것이 있는지 체크하고,

만일 있다면 result에 해당 값을 저장해 준다.

 

 

const len = result.length;
console.log(len, result[Math.floor(len / 2)]);

 

마지막으로 길이와 가운데 문자를 리턴해준다.

홀수의 경우, Math.floor(len/2)를 하면 가운데 문자를 리턴할 수 있다. 

 

 

- 걸린 시간

 

한 30-40분 걸린 것 같다ㅎ

중간에 전화 때문에 껐다가 다시 시간 재서,, 제대로 안되어 있다ㅠ

 

 

2. 리팩토링

const fs = require("fs");
const input = fs.readFileSync("./index.txt").toString().trim().split("\n");

const strArr = input.slice(1);
const seen = new Set(strArr);

let result = "";

function handleReverse(str) {
  return str.split("").reverse().join("");
}

// 회문 및 역순 문자열 확인
for (const str of strArr) {
  const reversedStr = handleReverse(str);

  // 회문이거나 역순 문자열이 Set에 있는지 확인
  if (str === reversedStr || seen.has(reversedStr)) {
    result = str;
    break;
  }
}

// 길이와 가운데 글자 출력
const len = result.length;
console.log(len, result[Math.floor(len / 2)]);

 

for (const str of strArr) {
  const reversedStr = handleReverse(str);

  // 회문이거나 역순 문자열이 Set에 있는지 확인
  if (str === reversedStr || seen.has(reversedStr)) {
    result = str;
    break;
  }
}

 

 

filter와 forEach 모두 strArr를 반복해서 돌기 때문에 이를 for of로 합쳐서 작성했다. 

그리고 reversedStr 변수를 만들어, 해당 문자에 반대 값을 저장해 줬다.

 

두 조건 다, 해당 글자와 반대되는 게 있는지 판단하는 것이기 때문에 reversedStr이 있는지 판단하는 조건문을 작성하면 된다.

회문일 경우 str과 reversedStr이 같은지 체크해 주고, 글 목록에 있는 경우는 set을 사용해 줬다.

해당 값이 있을 경우 result에 저장하고 break를 통해 반복문을 나와준다.

 

set은 배열과 비슷하지만, 검색 추가 삭제를 빠르게 할 수 있기 때문에 시간복잡도가 줄어든다.

배열에 뭔가가 있는지 검색할 경우, set을 이용하면 편하다!

 

리팩토링 이전 시간복잡도는 O(N^2 * m)이었는데, 리팩토링 후에는 O(N * m)이다!

이전에는 이중 반복문을 써서 그런 것 같다. 

앞으로 배열에서 값을 검색할 때는 set을 사용해야겠다!

 

 

3. 기타

1) set

set의 경우 배열과 달리 데이터 검색, 삭제, 삽입 모두 O(N)이기 때문에, 이런 경우엔 set을 사용하는 게 좋다.

배열은 끝에 있는 요소를 추가하거나 제거할 때만 O(N)이다.