[JS][백준]16719_ZOAC

문제 번호

16719번: ZOAC

 

 

 

알고리즘 분류

• 구현
• 문자열
• 재귀

 

문제 풀이

 구현 문제다. 

주어진 문자열에서 아직 등장하지 않은 알파벳들을 behind라는 배열에 넣어두었다. 그리고 1개씩 꺼내서 새로운 문자열을 만들어서 dic라는 배열에 넣고 어느 알파벳을 추가했을 때의 단어가 사전 순으로 가장 앞에 오는지 비교했다. => 브루트포스 알고리즘을 사용했다.

 

 우선 원본 문자열(이하 S)를 살펴보아서 어느 알파벳이 어느 자리에 있는지 파악했다. 예를 들어 START라는 문자열이 있으면 알파벳 'S'는 0번 인덱스에 들어갈 수 있고 알파벳'T'는 1과 4번 인덱스에 들어갈 수 있다. 

  // 스트링을 구성하는 알파벳들이 몇번째 자리에 있는지 파악한다.
  let alphabetLocation = new Array(26).fill(null).map(_ => []);
  for (let i = 0; i < s.length; i++) {
    let location = s.charCodeAt(i) - 65;
    alphabetLocation[location].push(i);  // i번째에 해당 알파벳이 있습니다. 0번 부터 A 입니다.
  }

 

 이제 beind라는 아직 등장하지 않은 알파벳들을 저장할 배열을 만들었다. sort()는 하지 않아도 된다. 처음에 문제를 잘못읽어서 했는데 지우지 않아도 별 이상이 없어서 내버려 두었다.

  s = s.split('')
  let behind = [...s.sort()];  // 깊은 복사로 만들어야함!!!!!!!!!!!!!

 

이제 word라는 배열을 사용하여 단어를 한 글자 씩 만들어보자. word라는 배열은 최종적으로 S와 똑같야 져야 하므로 크기는 S와 동일하다.

  let word = new Array(s.length).fill(null); // 완성되어갈 단어.

 

이제 등장하지 않은 알파벳들을 하나씩 word에 붙여서 새로운 단어를 만들고, 그 새로운 단어들 중에서 어느 단어가 사전상 가장 앞쪽에 위치하는지 살펴보자. 처음에 저장해 두었던 알파벳별 위치를 사용해야 한다. 알파벳별로 들어갈 수 있는 위치가 제한되어있음을 잊지 말자.

 past는 새로운 단어를 만들기 위한 배열이다. 지금까지 완성된 단어(word)에 아직 등장하지 않은 알파벳(behind)들 중 하나를 past에 추가해서 새로운 단어 newWord를 만드는 것이다. 만들어진 newWord들을 dic 배열에 넣어서 사전 순으로 어느 newWord가 가장 앞서는지 확인한다.

for (let i = 0; i < s.length; i++) {

    let dic = [];
    let past, idx, location;
    for (let j = 0; j < behind.length; j++) {
      // word에 behind의 알파벳을 하나씩 추가해본다.
      past = word.slice(0);
      idx = behind[j].charCodeAt(0) - 65; // 이 알파벳이 어디에 있는지 알기위한 인덱스.
      location = alphabetLocation[idx][alphabetLocation[idx].length - 1]; // j번 behind는 위치가 어디니?
      past[location] = String.fromCharCode(idx + 65); // 위치를 알았으니 해당 위치를 해당 알파벳으로 바꾼다.

      let newWord = '';
      for(let k=0; k<past.length; k++) {
        if(past[k] !== null) {
          newWord += past[k];
        }
      }

      dic.push({
        no: j,
        word: newWord,
      })
    }
    // 그렇게 만들어진 단어들의 사전순을 조사한다.
    dic.sort((a, b) => {
      a = a.word;
      b = b.word;
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    })

 

새로 만든 단어 중 어느 단어가 사전 순으로 가장 앞서는지 확인했다면 word를 업데이트시켜줘야 한다. 이때도 마찬가지로 알파벳별로 들어갈 수 있는 위치가 다르므로 이에 주의해서 word를 업데이트시켜줘야 한다. 업데이트 이후에는 behind 배열 또한 업데이트시켜줌으로써 사용된 알파벳은 등장하지 않은 알파벳에서 제거시켜준다.

// 가장 앞에 있는 단어로 word를 업데이트 한다.
    let TId = alphabetLocation[behind[dic[0].no].charCodeAt(0) - 65].pop() // 새로 추가한 알파벳의 자리를 찾아야한다.
    word[TId] = behind[dic[0].no];    
    answer += word.join('') + '\n'
    behind.splice(dic[0].no, 1); // 추가한 알파벳을 behind에서 제거시켜준다.

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
let s = input[0];  // 최대 100.

function sol() {
  let answer = '';

  // 스트링을 구성하는 알파벳들이 몇번째 자리에 있는지 파악한다.
  let alphabetLocation = new Array(26).fill(null).map(_ => []);
  for (let i = 0; i < s.length; i++) {
    let location = s.charCodeAt(i) - 65;
    alphabetLocation[location].push(i);  // i번째에 해당 알파벳이 있습니다. 0번 부터 A 입니다.
  }

  s = s.split('')
  let behind = [...s.sort()];  // 깊은 복사로 만들어야함!!!!!!!!!!!!!

  let word = new Array(s.length).fill(null); // 완성되어갈 단어.
  for (let i = 0; i < s.length; i++) {

    let dic = [];
    let past, idx, location;
    for (let j = 0; j < behind.length; j++) {
      // word에 behind의 알파벳을 하나씩 추가해본다.
      past = word.slice(0);
      idx = behind[j].charCodeAt(0) - 65; // 이 알파벳이 어디에 있는지 알기위한 인덱스.
      location = alphabetLocation[idx][alphabetLocation[idx].length - 1]; // j번 behind는 위치가 어디니?
      past[location] = String.fromCharCode(idx + 65); // 위치를 알았으니 해당 위치를 해당 알파벳으로 바꾼다.

      let newWord = '';
      for(let k=0; k<past.length; k++) {
        if(past[k] !== null) {
          newWord += past[k];
        }
      }

      dic.push({
        no: j,
        word: newWord,
      })
    }
    // 그렇게 만들어진 단어들의 사전순을 조사한다.
    dic.sort((a, b) => {
      a = a.word;
      b = b.word;
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    })
    
    // 가장 앞에 있는 단어로 word를 업데이트 한다.
    let TId = alphabetLocation[behind[dic[0].no].charCodeAt(0) - 65].pop() // 새로 추가한 알파벳의 자리를 찾아야한다.
    word[TId] = behind[dic[0].no];    
    answer += word.join('') + '\n'
    behind.splice(dic[0].no, 1); // 추가한 알파벳을 behind에서 제거시켜준다.    
  }
  console.log(answer.trim())
}
sol();

특이사항

구현 문제가 등장할 때마다 시간이 정말 오래 걸리는 것 같다. 알고리즘이 어렵지는 않지만, 따져야 하는 조건들이 많고 조건들을 따지다 보면 처음에 생각했던 로직이나 변수들의 사용처가 꼬이는 경우가 많은 것 같다. 구상을 최대한 완벽하게 하고 구현을 하려고 더 노력해야겠다.