[프로그래머스/Swift] 17679번 - 프렌즈 4블록

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17679

💡 구현 아이디어

1. 맵을 순회하면서 조건을 확인( (x, y) 가 (x+1, y), (x, y+1), (x+1, y+1)와 같은 블록인가?
2. 만약 같은 블록이라면 checkPos에 (x, y)를 저장
3. 순회가 끝나면 checkPos에 저장된 위치인 (x, y), (x+1, y), (x, y+1), (x+1, y+1)의 값이 “-1”이 아니면 “-1”로 바꿔주면서 개수를 기록. 이때 저장된 위치가 없으면 삭제할 블록이 없기 때문에 종료하고 현재까지의 기록한 개수를 반환
4. 종료되지 않았다면 블록을 정렬한다. 정렬할떄는 왼쪽 아래에서 부터 순회하면서 “-1”이면 자신과 가장 가까운 위쪽 블록과 자리를 바꾼다

• 주의점 : 블록은 항상 위에서 아래로 내려온다는 것이다 단순히 입력된 순서로 배열을 만들었을 경우 (0, 0) 은 좌상단의 블록을 가리키게 된다. 그러면 블록을 정렬할때 헷갈리는 경우가 있어 내 경우엔 최초의 입력을 reversed 시켜 board를 만들었다.

💻 코드

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
  var b: [[String]] = board.reversed().map { $0.map { String($0) } }
  var checkPos: [(Int,Int)] = [] // 지워질 블록의 위치
  var result: Int = 0
  
  while true {
    // 지워하는 블록을 찾음
    for y in 0..<m-1 {
      for x in 0..<n-1 {
        if b[y][x] == "-1" { continue }
        else if b[y][x] == b[y][x+1] && b[y][x] == b[y+1][x] && b[y][x] == b[y+1][x+1] {
          checkPos.append((y,x))
        }
      }
    }
    if checkPos.isEmpty { break }
    // 블록들을 지움
    while !checkPos.isEmpty {
      let pos = checkPos.removeLast()
      for y in 0...1 {
        for x in 0...1 {
          if b[pos.0+y][pos.1+x] != "-1" {
            result += 1
            b[pos.0+y][pos.1+x] = "-1"
          }
        }
      }
    }
    // 전체 블록들을 재정렬
    for y in 0..<m {
      for x in 0..<n {
        if b[y][x] == "-1" {
          for yi in y..<m {
            if b[yi][x] != "-1" {
              b[y][x] = b[yi][x]
              b[yi][x] = "-1"
              break
            }
          }
        }
      }
    }
  }
  return result
}

❌ 틀린 이유 및 틀린 부분

• 마지막 재정렬 부분에서 블록의 위치를 바꾼뒤 break를 걸어야하는데 까먹고 안해줬다…. (코드 아이디어를 짤때는 생각을 해놓은 부분이었는데!)

⏳ 시간 복잡도

• 반복문이 3중으로 되어있지만 대부분이 전체 순회를 하는 구조여서 O(n2)으로 생각된다.

📌 풀이 또는 기억할 정보

• 다른 사람의 경우 보드를 하나더 만들어서 지우고 보드를 정렬한뒤 보드를 바꾸는 식으로 푼사람도 있다.
• 이 문제의 경우엔 반복을 돌리는 행위가 큰 영향을 끼치지 않는것 같다. 다만 구조를 생각해야하는 것과 코드가 난잡해지기 때문에 몇몇 사람은 함수로 내용을 분리시켜 구성했다.