알고리즘 해결 패턴

1.통용적인 해결 패턴이 없는 경우

1. 문제를 이해

  1-1. 나만의 방식으로 문제를 이해하여 정리하자.
  1-2. 조건을 정확히 이해하고 정리하자.
  1-3. 문제의 입력값과 어떤 출력값이 필요한지 파악하자.

2. 구체적인 예시를 탐색

2-1. 간단한 예시부터 복잡한 예시 순으로 넣어보자.
2-2. 빈 값과 유효하지 않은 값등 예외케이스를 넣어보자.
2-3. 이때 넣어본다는 의미는 완성된 코드에 넣는다는 것이 아닌 머리속으로 넣어본다는 의미이다.

3. 문제를 세분화

3-1. 문제를 이해했다면 단계별 수행할 작업을 명시적으로 표시하자.(수도코드)
3-2. 만약 코딩테스트에서 시간이 부족해 통과하지 못했다면 이러한 단계를 명시한 것이 도움이 될 수있다.

4. 문제를 해결, 단순화

4-1. 만약 해결 가능하다면 바로 문제 해결을 시작하고,
4-2. 해결법이 떠오르지 않는다면 세분화하며 간단한 구현부터 시작하자.

5. 문제를 복습 및 재구성

5-1. 위에서 해결한 문제는 해결을 위한 방법이였다.
5-2. 이를 리팩토링하여 코드를 정리하고 효율적으로 만드는 것이 실력향상의 지름길이다.

통용적인 해결 패턴이 없는 경우의 풀이 예시

문제링크

1. 문제 이해

• 로또 번호와 당첨 번호 리스트가 입력값으로 주어진다.
• 이때 로또 번호는 (숫자, 0)으로 이루어져있다.
• 당첨 번호별 등수가 주어진다. (6개 당첨 => 1등)
• 0은 조커로 무조건 당첨될 수 있고, 무조건 낙첨될 수 있다.
• 이때 최대 당첨 등수와 최저 당첨 등수 순으로 배열을 만들어 출력하라.
• 6 -> 1등, 5 -> 2등 ... 1 -> 6등, 0 -> 6등으로 6등과 매칭되는 당첨 번호 개수는 2개이다.(주의점)

2. 구체적인 예시를 탐색

• 보통 테스트 케이스에 명시된 예시를 사용하여 문제에 대입해 본다.
  • 나의 로또 번호([44, 1, 0, 0, 31, 25]), 당첨 로또 번호([31, 10, 45, 1, 6, 19]) 일때, 0이외에 당첨 개수는 [1, 31]이므로 [0,0]을 모두 당첨으로 따지면 4개 당첨(3등), [0,0]을 모두 낙첨으로 따지면 2개 당첨(5등)이다. => [3,5]
• [0,0,0,0,0,0]을 입력한다면 0이 모두 당첨일경우 1등, 0이 모두 낙첨일 경우 6등이므로 [1,6]이 return되어야 한다.
• 입력값은 항상 길이가 6인 0이상 45이하의 정수 배열이므로 빈배열은 들어갈 수 없다.

3. 문제를 세분화

• 우선 주어진 로또 번호에서 0 이외에 몇개가 당첨번호와 일치하는지 구해야한다.
• 주어진 로또 번호에서 0의 개수를 구하여 위에서 구한 일치한 당첨번호 개수와 더한 뒤 최대 당첨 번호의 개수를 구한다.
• 0의 개수를 더하지 않은 개수는 최저 당첨 개수이다.
• 문제에서 주어진 당첨번호 개수별 당첨 등수를 통해 당첨 등수를 구한다.
  • 이때 당첨번호 1개, 0개는 모두 6등으로 취급하여야 한다.(주의점)

4. 문제 해결

• 해결법을 통해 문제를 해결한다.

function solution(lottos, win_nums) {
    var answer = [];
    let correctNumCount = 0;
    let zeros = 0;
    
  	// 문제 세분화를 코드에 수도코드식으로 적고 해결하자.
  	// 주어진 로또 번호에서 0을 제외한 당첨 번호의 개수를 저장한다.
    lottos.map((num) => win_nums.includes(num) ? correctNumCount += 1 : correctNumCount)
  	// 주어진 로또 번호에서 0의 개수를 저장한다.
    lottos.map((num) => (num === 0) && (zeros += 1))
    
  	// 0을 제외한 당첨 번호에 맞는 등수를 저장한다.
    const low = 7-correctNumCount <= 5 ? 7-correctNumCount : 6;
  	// 0을 포한한 당첨 번호에 맞는 등수를 저장한다.
    const high = low-zeros <= 1 ? 1 : low-zeros;
    
    answer = [high, low];
    
    
    return answer;
}

5. 문제 복습 및 리팩토링

• 위에 코드는 실제 문제를 처음 봤을때 내가 짠 코드이다.
  그런데 가독성이 좋지 않고 복잡하게 구현한 점과 줄일 수 있는 for문이 있었다. (2N을 N으로 줄인것이라 큰 의미는 없다.)

function solution(lottos, win_nums) {
    var answer = []
    let minSameCnt = 0;
    let maxSameCnt = 0;
	
  	// 최소 당첨 개수에 0을 제외한 당첨 번호를 넣고, 최대 당첨 개수에 0을 합한 당첨 번호를 넣는다.
    lottos.forEach(e => {
      if(win_nums.includes(e)){
        minSameCnt++;
      };
      if(win_nums.includes(e) || e===0){
        maxSameCnt++;
      }
    })
    
  	// 최대 당첨 개수와 최소 당첨 개수를 통해 당첨 등수를 구한다. 
    topRank = (7 - maxSameCnt === 7) ? 6 : 7-maxSameCnt; 
    lowRank = (7 - minSameCnt === 7) ? 6 : 7-minSameCnt;
    
    answer = [topRank, lowRank]
    
    return answer;
}

• 앞서 주어진 로또 번호에서 0의 개수를 구하여 위에서 구한 일치한 당첨번호 개수와 더한 뒤 최대 당첨 번호의 개수를 구한다., 0의 개수를 더하지 않은 개수는 최저 당첨 개수이다.의 부분을 하나의 for문으로 처리하였다.

• 최대 등수와 최저 등수의 로직을 동일하게 구현하여 가독성을 높혔다.

2. 통용적인 해결 패턴이 있는 경우

Grid, DFS, BFS, Divide And Conquer, Dijkstra 등등 통용적인 해결 패턴이 있는 경우

=> 관련 문제를 많이 풀고 알고리즘을 이해하는 노력이 필요하다.