백준1940 - 주몽 (정렬, 투포인터) JS

https://www.acmicpc.net/problem/1940

위에서 주어진 예제를 예를 들면, 해당 문제는 수들 [2,7,4,1,5,3]을 조합하여 9를 만드는 방법은 몇 가지가 있는지 출력하는 문제다.

 

이 경우, 정렬을 한 뒤 맨 앞의 값과 맨 뒤의 값을 합한 뒤, 우리가 원하는 값과 같은지 비교해가며 풀이하면 된다.

 

예를 들어, 주어진 수 [2,7,4,1,5,3]을 정렬한다. 

이후 [1,2,3,4,5,7]로 정렬된 값에서 맨 앞수 '1'과 맨 뒷수'7'을 합하여 '9'와 비교한다.

이때 합쳐진 수 '8'는 '9'보다 작기 때문에, 앞에 있는 수 '1'은 제거한다.

('1'은 가장 큰 수 '7'과 합쳐도 원하는 수를 만들 수 없기 때문에 필요 없음)

만약 합친 수가 더 크면 큰 수를 제거, 동일하다면 작은 수, 큰 수 모두 제거하는 방식으로 반복하여 진행한다.

 

소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

function solution(data) {
  const [_,M,...temp] = data
  const sorted = temp[0].split(' ').map(Number).sort((a,b)=> a-b)

  let result = 0
  // 수의 길이가 홀수로 주어진 경우, 마지막에 하나가 남기 때문에
  // while문의 종료 조건은 1이하일 경우로 설정
  while(sorted.length > 1) {
    const sum = sorted[0] + sorted.at(-1)
    if(sum === +M) {
      sorted.shift()
      sorted.pop()
      result ++
    } else sum < +M ? sorted.shift() : sorted.pop()
  }

  console.log(result)
}

solution(input)

 

그리고 위 코드는 shift() 메서드 자체의 시간 복잡도가 O(n)이기 때문에 배열의 길이가 클수록 비효율적이다.

따라서 shift 메서드를 사용하지 않고, 앞수와 뒷수를 배열의 인덱스로 접근하는 방식으로 개선이 가능한데, 

이를 적용한 풀이가 아래의 소스 코드다.

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

function solution(data) {
  const [_,M,...temp] = data
  const sorted = temp[0].split(' ').map(Number).sort((a,b)=> a-b)

  let result = 0
  let [frontIdx, backIdx] = [0, sorted.length - 1]
  while(backIdx - frontIdx > 0) {
    const sum = sorted[frontIdx] + sorted[backIdx]
    if(sum === +M) {
      frontIdx ++
      backIdx --
      result ++
    } else sum < +M ? frontIdx ++ : backIdx --
  }

  console.log(result)
}

solution(input)

 

 

그리고 두 소스코드의 시간 소요 시간을 비교해본 결과, 크진 않지만 차이를 확인할 수 있었다.

(아무래도 문제에서는 15000 이하의 수들이 주어진다고 했지만, 그리 많은 수들이 테스트로 주어지지는 않은 듯하다.)