[구현 - 시뮬레이션과 완전 탐색] 문제 풀이

2-2 [구현 - 시뮬레이션과 완전 탐색] 문제 풀이

<문제1>시각

문제 설명

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시간중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각임.
• 00시 00분 03초
• 00시 13분 30초
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각임
• 00시 02분 55초
• 01시 27분 45초

문제 조건

문제 해결 아이디어

• 이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제임
• 하루는 86,400초이므로, 00시00분00초부터 23시 59분 59초까지의 모든 경우는 86,400가지임.
• 따라서 단순히 시각을 1초씩 증가시키면서 3이 하나라도 포함되어 있는지를 확인하면 됨
• 이러한 유형은 완전 탐색(Brute Forcing)문제 유형이라고 불림.
• 가능한 경우의 수를 모두 검사해보는 탐색방법을 의미함.

 

내가 작성한 코드

const n = prompt("0~23 입력: ");

let count = 0;



for(let hour = 0; hour <= n; hour++){

  for(let min = 0; min < 60; min++ ){

    for(let sec = 0; sec < 60; sec++){

      if( (String(hour)+String(min)+String(sec)).includes("3") )

        {

          count++;

        }

    }

  }

}

 

console.log(count);

자바스크립트의 includes 메소드를 사용하였다.

 

<문제2> 왕실의 나이트

문제 설명

• 행복 왕궁의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면임. 왕실 정원의 특정한 한 칸에 나이트가 서있음. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마함.
• 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없음
• 나이트는 특정 위치에서 다음과 같은 두 가지 경우로 이동할 수 있음
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
• 이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현함.
• c2에 있을 때 이동할 수 있는 경우의 수는 6가지임. 

문제 조건

문제 해결 아이디어

• 요구사항대로 충실히 구현하면 되는 문제
• 나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인
• 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의

 

내가 작성한 코드(자바스크립트)

//a1 -> (1,a) -> (row,col) -> (1,1)
// 총 8,8 까지 있음
function royalKnight(input){
  let col = input.charCodeAt(0) - 96;
  let row = Number(input[1]);
  let nextRow = row;
  let nextCol = col;
  let count = 0;
  console.log(`input : ${input} = (${row},${col})`);
  const move_types = [[-1,-2],[1,-2],[-2,-1],[2,-1],
                      [-2,1],[2,1],[-1,2],[1,2]];
  for(let i = 0; i < move_types.length; i++){
    nextRow = row + move_types[i][0];
    nextCol = col + move_types[i][1];
    if(nextRow >= 1 && nextRow <= 8 && nextCol >=1 && nextCol <= 8){
      count++;
      console.log(`가능한 경우의 수 : ${i+1} : (${nextRow},${nextCol})`);
    }
      
  }
  return count;
}
console.log(royalKnight("c2"));
//기댓값 6

2차원 배열을 이용했음, move_types를 썼다는 점에서 앞 전 게시글의 상하좌우(LRUD)문제와 유사한 점이 많음

 

     

 

<문제> 문자열 재정렬

문제 설명

• 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어짐, 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력함
• 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력함

문제 조건

문제 해결 아이디어

• 요구사항대로 충실히 구현하면 되는 문제
• 문자열이 입력되었을 때 문자를 하나씩 확인함
• 숫자인 경우 따로 합계를 계산함
• 알파벳의 경우 별도의 리스트에 저장함
• 결과적으로 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력하면 정답

 

내가 작성한 코드(자바스크립트)

const inputString = prompt("문자열을 입력해주세요.");



const stringArray = [];

let numberSum=0;



for(let element of inputString){

  if(isNaN(element)){

    stringArray.push(element);

  }

  else{

    numberSum += Number(element);

  }

}



let result = stringArray.sort(); // 문자부터 우선 정렬



if(numberSum != 0){ // 숫자들의 합이 0이 아니라면 배열에 가장 뒤에 삽입

  result.push(numberSum);

}

result = result.join(""); //배열을 문자열로 바꾸기



console.log(result);