[코딩테스트]백준 - 맞춰봐

맞춰봐

문제

규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라고 가르쳐 줬다.

이제 규현이는 0~10까지 수를 알고 있다. 어느 날 자신이 알고 있는 숫자를 까먹지 않으려고 종이에 1~10까지 수를 썻다. (0은 잠시 까먹었다) 규현이의 친구 석원이는 밀덕이다. 계급을 엄청나게 좋아해서, 규현이가 써 놓은 숫자에 이등병 마크인 -를 모두 그렸다. 석원이는 규현이에게 이렇게 말했다. "너, 우리 위대하신 미하엘 칼라시니코프께서 뭐라고 했는지 알아? 단순함과 신뢰성, 그리고 저렴한 가격이 최고야!"

규현이는 그 말을 듣고서 아하 세상에는 음수도 있구나 했다.

이제 규현이가 아는 수는 -10부터 10까지 20개가 되었다. 아차, 0을 빼먹었구나, 21개가 되었다.

근처 사파리에 놀러간 규현이는 사파리 가이드 승환이와 함께 관광을 시작했다. "저기, 사자 1마리가 보이죠? 그 옆이 그 사자 부인이에요. 그러니깐, 1 더하기 1은 2죠" 규현이는 덧셈을 익혔다. "저 사자는 아까 그 사자의 자식 2마리 입니다. 그럼 총 사자는 몇 마리이지요?" 이제 규현이는 1+1을 제외한 다른 덧셈도 할 수 있다. 만세!

인도네시아에 놀러간 규현이는 자바 섬에 방문했다. 자바 섬에는 자바 커피를 재배하는 홍태석 농부가 있었다. 홍태석은 "ㅋㅋㅋ 님 음수와 양수와 0의 차이도 모름?" 하면서 음수와 양수와 0을 설명해주었다.

지금까지 배운 것을 종합해서, 한국으로 돌아오는 비행기에서 규현이는 종이에 수를 N개 썼다. (규현이가 아는 가장 큰 수는 10이기 때문에, 수를 10개까지만 쓸 수 있다.) 그 다음에, 가능한 모든 N*(N+1)/2개의 구간의 합을 구했다. 이 것을 해인이는 행렬로 표현했다.

규현이가 쓴 수를 A라고 하면, A[i]는 규현이가 i번째 쓴 수이다. 그리고, S[i][j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다. 이렇게 배열을 채우면 배열에는 총 N*(N+1)/2개의 문자가 있다. (+, -, 0 중 하나) 이 S 배열이 주어졌을 때, 규현이가 쓴 N개의 수 A를 구해서 출력하면 된다. 규현이는 -10부터 10까지의 정수밖에 모르기 때문에, A도 -10부터 10까지의 정수로만 이루어져 있어야 한다.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.

출력

첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 답이 여러 가지 일 경우에는 아무거나 출력하면 된다.

예제 입력 1

4
-+0++++--+

예제 출력 1

-2 5 -3 1

출처

• ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2008 G번
• 문제의 오타를 찾은 사람: 1207koo
• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive

문제 해석

N개의 수열과 부호가 주는 힌트와의 관계는 다음과 같다.

• 답으로 제시된 수열 = [-2, 5, -3, 1]에 대해 부호와의 관계를 살펴보면

이렇게 index 0부터 1, 2, ..., 끝까지의 합과 부호가 같다.

부호값이 있는 이차원 배열을 부호[][]라고 한다면,

• 수열[0] = 부호[0][0]
• 수열[0]+수열[1] = 부호[0][1]
• 수열[0]+수열[1]+수열[2] = 부호[0][2]
• 수열[0]+수열[1]+수열[2]+수열[3] = 부호[0][3]
  뭔가 규칙이 보이는 것 같다... ?

그럼 그 다음 줄의 부호들은 무엇? index 1부터 끝까지의 합에 대한 부호이다.

여기 또한,

• 수열[1] = 부호[1][1]
• 수열[1]+수열[2] = 부호[1][2]
• 수열[1]+수열[2]+수열[3] = 부호[1][3]

그 다음 index 2부터 끝까지의 합에 대한 부호를 보자.

• 수열[2] = 부호[2][2]
• 수열[2]+수열[3] = 부호[2][3]

그리고 마지막 index부터 끝까지의 합에 대한 부호로 끝이 난다.

• 수열[3] = 부호[3][3]

즉 부호(x,y) 좌표에 해당하는 부호 값은 수열의 x~y까지의 합에 대한 부호와 상응해야 한다.
그럼 부호값을 이러한 이차원 배열로 만들어서 검사해주면 좋을 것 같다!

해결한 코드

function b1248(){
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var n = parseInt(input[0]) // n값
    var buho = input[1] // 부호 문자열
   
    var map = create2DArray(n, n) // 부호 값을 넣을 2차원 배열 map
    var idx = 0
    for(var i=0; i<n; i++){
      for(var j=i; j<n; j++){
        map[i][j] = buho[idx++] // 문자열로 들어온 부호들을 차례로 map에 넣어주기 
      }
    }
  var arr = new Array(n) // 답을 넣을 배열 
  solve(0, arr, map, n)
}

function create2DArray(row, col){ // 2차원배열 만드는 함수
  var array = new Array(row)
  for(var i=0; i<row; i++){
    array[i] = new Array(col)
  }
  return array
}

function solve(count, arr, map, n){
  if(count === n){
    var str = ''
    for(var s=0; s<n; s++){
     str += arr[i].toString()+' ' 
    }
    console.log(str)
    process.exit(0)
  }
  for(var i=-10; i<=10; i++){
    arr[count] = i
    if(check(count, arr, map)){ 
      solve(count+1, arr, map, n)
    }
  }
}

function check(index, arr, map){ // 유망성 검사 
  for(var i=0; i<=index; i++){
    var sum = 0
    for(var j=i; j<=index; j++){
      sum += arr[j]
      if(map[i][j] !== (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
        return false
      }
    }
  }
  return true 
}

알고리즘

개인적으로 유망성 검사 부분을 코드화 하는데 고민을 많이 했다. 이 부분을 중점으로 정리할 예정 !

1. 백트래킹을 돌릴 함수 solve를 만들어준다.
2. solve 함수를 통해 정답을 넣을 배열 arr를 만들고, 여기에 -10~10까지의 수를 넣어본다.
3. arr에 해당 수를 넣어도 되는지 유망성 검사 시작 !
   3-1. 유망성을 알아보기 위해 필요한 건?
   👉🏻 arr배열, map(부호 정보가 담긴 이차원배열), 현재 인덱스

그럼 -10부터 차근차근(하지만 살짝 띄엄띄엄..) 살펴보자
arr에 -10을 넣는다.

3-1. 현재 상태 :

count = 0
arr = [ -10 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

3-2. -10을 넣어도 되는지 유망성 검사를 위해 check 함수에 들어가면,

check(0, [ -10 ], map){
  for(var i=0; i<=0; i++){
    var sum = 0
    for(var j=0; j<=0; j++){
      sum += -10 
  // sum = -10
  // map[i][j] => map[0][0] = '-'
  // sum < 0 , map값도 '-'
     if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
       // map[0][0] === sum < 0 ? '-' : '+' 아니까 거치지 않음 
       return false
     }
   }
 }
 return true 
}

true로 반환됨 => 그럼 count+1를 해주어 solve함수를 시작
다시 solve함수로 들어가 arr[1]에 -10~10까지의 숫자를 넣어본다.

count = 1
arr = [ -10, -10 ] // arr[1] = -10
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(1, [ -10, -10 ], map){
  for(var i=0; i<=1; i++){
    var sum = 0
    for(var j=0; j<=1; j++){
      sum  = -10 + -10
  // sum = -10 | sum = -20
  // map[i][j] => map[0][0] = '-'| map[i][j] => map[0][1] = '+'
  // sum < 0 , map값도 '-' | sum < 0, map값은 '+'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[0][1]의 부호와 sum의 값이 맞지 않아 return false 
      return false
    }
   }
  }
  return true 
}

false로 반환됨 => 그럼 재귀에서 빠져나와 arr=[ -10 ]인 상태로 되돌아간다.
(하지만 -10+i가 양수가 되는 i는 -10~10 범위 내에 없다...)

3-3. 고로 재귀에서 빠져나와 arr = [ ]인 상태로 되돌아간다.

-10의 다음 수 -9를 넣음
현재상태:

count = 0
arr = [ -9 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(0, [ -9 ], map){
  for(var i=0; i<=0; i++){
    var sum = 0
    for(var j=0; j<=0; j++){
      sum  = -9
  // sum = -9
  // map[i][j] => map[0][0] = '-'
  // sum < 0 , map값도 '-' 
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[0][0]의 부호와 sum의 값이 맞으니 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => 그럼 count+1을 해주어 solve함수 시작
arr[1]에 -10부터 10까지 넣어본다 => 현재 -10이 들어간다.

count = 1
arr = [ -9, -10 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(1, [ -9, -10 ], map){
  for(var i=0; i<=1; i++){
    var sum = 0
    for(var j=i; j<=1; j++){
      sum  = -9
  // sum = -9 | sum = -19
  // map[i][j] => map[0][0] = '-' | map[i][j] => map[0][1] = '+'
  // sum < 0 , map값도 '-' | sum < 0 , map값은 '+'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[0][1]의 부호와 sum의 값이 맞지 않아 return false 
      return false
    }
   }
  }
  return true 
}

false가 반환됨 => 재귀에서 빠져나와 arr=[ -9 ]인 상태로 되돌아간다.
그렇게 arr[1]에 -10~10까지 숫자를 넣어보며 -9+i가 양수가 되는 수를 찾아보다가... i=10의 경우에 왔다면

count = 1
arr = [ -9, 10 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(1, [ -9, 10 ], map){
  for(var i=0; i<=1; i++){
    var sum = 0
    for(var j=i; j<=1; j++){
      sum  = -9 + 10 
  // sum = -9 | sum = 1
  // map[i][j] => map[0][0] = '-' | map[i][j] => map[0][1] = '+' | map[1][1] = '+'
  // sum < 0 , map값도 '-' | sum > 0 , map값도 '+' | sum > 0, map = '+'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[i][j]의 부호와 sum값이 일치하므로 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => count+1를 해주어 solve 시작
(살짝 생략해서) arr[2]에 들어갈 i값으로 (-9 + 10 + i가 0이 되는 수인) i=-1의 경우에 왔다면

count = 2
arr = [ -9, 10, -1]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(2, [ -9, 10, -1 ], map){
  for(var i=0; i<=2; i++){
    var sum = 0
    for(var j=i; j<=2; j++){
      sum  = -9
  // sum = -9 | sum = 1
  // map[i][j] => map[0][0] = '-' | map[0][1] = '+' | map[0][2] = '0' | map[1][1] = '+' | map[1][2] = '+' | map[2][2] = '-'
  // sum(-9) < 0, map = '-' | sum(1) > 0, map = '+' | sum(0) == 0, map = '0' | sum(10) > 0, map = '+' | sum(9) > 0, map = '+' | sum(-1) < 0, map = '-'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[i][j]의 부호와 sum값이 일치하므로 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => count+1을 해주어 solve 시작
arr[3]으로 들어갈 i는? -9 + 10 + -1 + i를 해주어 양수가 되는 수
그렇다면 i가 될 수 있는 수는? 1~10
그런데 map[2][3]은 '-'이므로, -1 + i이 음수여야 한다. 하지만 1~10중 어느 것을 i로 넣어도 음수가 되지 못한다.
결국 모든 수가 false 되고... 재귀를 부른 부모 함수를 따라 돌아간다.
-9는 -9와 i를 더했을 때 양수가 되는 i값이 10밖에 없었는데 이 경우가 false가 되었으므로 결국 처음으로 되돌아가게 된다.

3-4. 또 재귀에서 빠져나와 arr = [ ]의 상태로 되돌아감

-9 다음 수인 -8을 넣음

count = 0
arr = [ -8 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(0, [ -8 ], map){
  for(var i=0; i<=0; i++){
    var sum = 0
    for(var j=0; j<=0; j++){
      sum  = -8
  // sum = -8
  // map[i][j] => map[0][0] = '-'
  // sum < 0 , map값도 '-' 
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[0][0]의 부호와 sum의 값이 맞으니 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => count+1을 해주어 solve 시작
arr[1]의 값이 될 i가 -10부터 시작해 (-8 + i를 해서 양수가 되는) i=9의 경우에 도달하면

count = 1
arr = [ -8, 9 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(1, [ -8, 9 ], map){
  for(var i=0; i<=1; i++){
    var sum = 0
    for(var j=i; j<=1; j++){
      sum  = -8 + 9
  // sum = -8 | sum = 1 | sum = 9 
  // map[i][j] => map[0][0] = '-' | map[0][1] = '+' | map[1][1] = '+'
  // sum < 0 , map값도 '-' | sum(1) > 0, map = '+' | sum(9) > 0, map = '+'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[i][j]의 부호와 sum의 값이 맞으니 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => count+1을 해주어 solve 시작
arr[2]의 값이 될 i가 -10부터 시작해 (-8 + 9 + i를 해서 0이 되는) i=-1의 경우에 도달하면

count = 2
arr = [ -8, 9, -1 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(2, [ -8, 9, -1 ], map){
  for(var i=0; i<=2; i++){
    var sum = 0
    for(var j=i; j<=2; j++){
      sum  = -8 + 9 + -1
  // sum = -8 | sum = 1 | sum = 0 | sum = 9 | sum = 8 | sum = -1
  // map[i][j] => map[0][0] = '-' | map[0][1] = '+' | map[0][2] = '0' | map[1][1] = '+' | map[1][2] = '+' | map[2][2] = '-'
  // sum < 0 , map값도 '-' | sum(1) > 0, map = '+' | sum(0) = 0, map = '0' | sum(9) > 0, map = '+' | sum(8) > 0, map = '+' | sum(-1) < 0, map = '-'
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      // map[i][j]의 부호와 sum의 값이 맞으니 이곳을 거치지 않음 
      return false
    }
   }
  }
  return true 
}

true가 반환됨 => count+1을 해주어 solve 시작
-8 + 9 + -1 + i를 해서 양수가 되는 i는 ? 1~10
하지만 아까와 마찬가지로 map[2][3]은 '-'이므로, -1+i는 음수여야 한다.
1~10까지의 모든 수는 -1과 더했을 때 음수가 되지 못하므로 false로 반환된다.
재귀를 따라 돌아가 arr = [ -8 ]의 상태까지 간다.

3-4. -8 + i를 해서 양수가 되었던 9 다음 숫자인 10을 넣는다.

위와 같은 과정을 거쳐 arr = [ -8, 10, -2 ]까지 채워진다.
arr[3]에 들어갈 i값으로 -8 + 10 + -2 + i를 해서 양수가 나올 수 있는 i는? 1~10
map[2][3]이 '-'이므로, -2+i의 값이 음수일 수 있는 i는? 1
arr[3]의 값으로 -10부터 시작하여 (중간과정 생략하고) i=1인 경우에 도달했다면,

count = 3
arr = [ -8, 10, -2, 1 ]
map = [
  [-, +, 0, +],
  [ , +, +, +],
  [ , , -, -],
  [ , , , +]
]

check(3, [ -8, 10, -2, 1], map){
  for(var i=0; i<=3; i++){
    var sum = 0
    for(var j=i; j<=3; j++){
      sum  = -8 + 10 + -2 + 1
    if(map[i][j] !==  (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))){
      return false
    }
   }
  }
  return true 
}

(주석 달기가 불편해져서 그림으로 대체하였다)
sum을 계산하는 순서에 따라 각 행을 i, 각 열을 j라고 두었으니,

• i가 0일때 j=0, 1, 2, 3의 sum값과 map의 부호를 확인하고
• i가 1일때 sum을 0으로 초기화한 후 j=1, 2, 3의 sum값과 map 부호를 확인하고
• i가 2일때 sum을 0으로 초기화한 후 j=2, 3의 sum값과 map 부호를 확인하고
• i가 3일때 sum을 0으로 초기화한 후 j=3의 sum값과 map부호를 확인하였더니
  =>모두 잘 맞게 떨어졌다.

3-5. true가 return되어 count+1이 된다. 그렇게 시작된 solve의 count는 n값과 같아진다.

arr 배열에 map의 조건에 부합하는 숫자가 모두 담겼으니 이를 공백을 포함한 문자열로 붙여 출력한다.
※ "답이 여러 가지 일 경우에는 아무거나 출력하면 된다"고 하였으니 출력 후 곧바로 프로세스를 종료한다.

시행착오를 많이 겪은 문제다.
(멍청한 건 규현이가 아니라 저인 것 같습니다만...)
부호를 이차원 배열로 만들어 유망성 검사하는 방법을 떠올리지 못해 고생했다.

단순히 부호 = ['-', '+', '0', '+', '+', '+', '+', '-', '-', '+'] 이런 식으로 일차원 배열로서 해결하려고 했는데, ... 확인된 부호들은 중간에 slice로 잘라내야 하나, shift()로 빼서 처리해야 하나 등등의 생각을 많이 했다.

또 점점 백트래킹으로 풀기보다는 다른 방식으로 풀려고 했던 것 같다.
일단 부호 배열의 앞 4자리 조건에 부합하는 n길이의 수열들을 모두 만들어 놓고, 그 중에서 다음 부호 조건들에 해당하는 애들을 솎아내는 방식;; 이러면 백트래킹이 무슨 소용?

몇시간 고민하면서 결국 이 문제는 정말 백트래킹으로 풀 수 있을거 같다는 생각이 들었고, 유망성 검사 부분을 코드화하는데 실패해 구글링의 도움을 받았다.

사기도 저하되고 동기부여도 떨어지는 요즘.. 어떻게 나를 다시 다독일지, 지치지 않게 할 수 있을지가 최대 고민거리다. 조금씩 점점 모든것이 하기 싫어지는 요즘 ㅜㅜ