gurwhddl
코알못 공부블로그
gurwhddl
전체 방문자
오늘
어제
  • 분류 전체보기
    • CSS
    • JS
    • node.JS
    • REACT
    • 코딩테스트 연습

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
gurwhddl

코알못 공부블로그

코딩테스트 연습

백준 1411 - 비슷한 단어 JS

2023. 6. 16. 16:55

문제

만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.

예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.
단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.

접근법

일단 문제가 너무 이해하기 힘들게 해놨음..

  •  a -> z : 그 다음에 나오는 a는 무조건 z로 바꿔야 하고, a를 제외한 다른 알파벳들은 z로 바꿀 수 없음
  •  b -> b : 자기 자신으로 바꾸는건 가능하기 때문에 b를 제외한 다른 알파벳들은 b로 바꿀 수 없음

ex) zbxz / opor

  • z는 처음 등장했고, o도 쓴 적이 없기 때문에 z -> o로 바꿀 수 있음
  • b는 처음 등장했고, p도 쓴 적이 없기 때문에 b -> p로 바꿀 수 있음
  • x는 처음 등장했지만, o는 이미 썼기 때문에 바꿀 수 없음
  • z는 z -> o로 바꾼 전적이 있기 때문에 무조건 o로만 바꿀 수 있기 때문에 r로 바꿀 수 없으니 끝

풀이

let result = 0;
//a를 a로 바꿨다고 할 수 있음
//한번 바꾼 알파벳은 뒤에서는 못 씀
//똑같은 알파벳이 있으면 그건 전부 똑같은 걸로만 or 자기 자신으로만 바꿀 수 있음
for (let i = 1; i < input.length; i++) {
  let first = input[i];
  for (let j = i + 1; j < input.length; j++) {
    let second = input[j];
    let isUsed = [];
    let map = new Map();
    let isMatch = true;
    for (let z = 0; z < first.length; z++) {
      let [a, b] = [first[z], second[z]];
      //기존에 변경한 값이 있으면 - 그 값과 b가 같다면 넘어가기 - 틀리면 끝
      //기존에 변경한 값이 없으면 - b가 isUsed에 들어있지 않으면 세팅하고 넘어가기
      //들어있으면 - 끝
      if (map.get(a) && map.get(a) !== b) {
        isMatch = false;
        break;
      }
      if (!map.get(a) && isUsed.includes(b)) {
        isMatch = false;
        break;
      } else if (!map.get(a) && !isUsed.includes(b)) {
        map.set(a, b);
        isUsed.push(b);
      }
    }
    result += isMatch ? 1 : 0;
  }
}

console.log(result);

a가 기존알파벳 , b가 바꾼알파벳으로 놓고
map에는 알파벳을 어떤 알파벳으로 바꾸었는지를 저장하고
isUsed에는 사용한 알파벳을 저장해놓음

저작자표시 (새창열림)

'코딩테스트 연습' 카테고리의 다른 글

프로그래머스 - 입국심사 JS  (0) 2023.07.16
프로그래머스 - 부대복귀 JS  (0) 2023.06.26
백준 2309 - 일곱 난쟁이 JS  (0) 2023.06.16
프로그래머스 Lev 2 - 숫자 변환하기  (0) 2023.06.11
프로그래머스 - 문자열 나누기  (0) 2023.06.05
    '코딩테스트 연습' 카테고리의 다른 글
    • 프로그래머스 - 입국심사 JS
    • 프로그래머스 - 부대복귀 JS
    • 백준 2309 - 일곱 난쟁이 JS
    • 프로그래머스 Lev 2 - 숫자 변환하기
    gurwhddl
    gurwhddl

    티스토리툴바