2024 KAKAO WINTER INTERNSHIP

요구사항 분석

구현 목표

• 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구하기

입력값

• 연결된 간선과 간선 정보의 배열. [[시작 정점, 도착 정점]]

함수 요구 기능

• 시작 정점과 도착 정점을 순회하며, 각 정점마다 들어온 간선과 나간 간선의 개수를 구한다.
• 각 정점의 들어온 간선과 나간 간선 개수를 탐색하여, 각 그래프의 개수를 구한다.
• ⭐️ 그래프 공식

   1) out == 0 -> 막대 그래프 ... 막대 끝 정점는 [out: 0]이기 때문
   2) out == 2
      2-1) in == 0 -> 시작 정점 ... 시작 정점만 out이 2개 이상 존재하고 in이 0임.
      2-2) in > 0 -> 8자 그래프 ... 8자 그래프 중심 정점는 [in: 2, out: 2].
   3) out > 2 -> 시작 정점 ... 시작 정점만이 out이 2개 초과할 수 있음.
   4) 그 외는 무시
   
   도넛 그래프 개수 = 시작 정점의 나간 간선(`outEdge`) - 막대그래프 개수 - 8자 그래프 개수

• [생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수] 1차원 정수 배열로 return 한다.

구현 과정

구현

1. Node 구조체 정의

   1. inEdge : 나간 간선의 개수
   2. outEdge : 들어온 간선의 개수
   3. addIn(), addOut() : 간선 개수 연산 함수
   4. getIn(), getOut() : 간선 개수 getter 함수

   struct Node {
       var inEdge: Int
       var outEdge: Int
       
       init(inEdge: Int, outEdge: Int) {
           self.inEdge = inEdge
           self.outEdge = outEdge
       }
       
       mutating func addIn() {
           inEdge += 1
       }
       
       mutating func addOut() {
           outEdge += 1
       }
       
       func getIn() -> Int {
           return self.inEdge
       }
       
       func getOut() -> Int {
           return self.outEdge
       }
   }

1. solution() 프로퍼티

   1. answer : [생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수]
   2. nodes : 정점의 최대 개수가 100000개 이므로, 100001칸의 [Node?] 배열 선언. (없는 정점이 존재할 수 있으므로, 옵셔널 처리)
   3. startNodeNum : 생성한 정점의 번호

   var answer: [Int] = Array(repeating: 0, count: 4)
   var nodes: [Node?] = Array(repeating: nil, count: 1000001)
   var startNodeNum: Int = 0

2. solution() 로직

   1. 입력값 edges를 순회하며, 시작 정점과 도착 정점의 나간 간선과 들어온 간선을 계산한다.

   2. 만약 정점이 존재하지 않다면 Node를 생성하고, 이미 정점이 존재하다면 간선 증가.

   3. ⭐️ 주의할 점! [시작 정점, 도착 정점] 이므로 시작 정점에서 간선이 나가고, 도착 정점에 간선이 들어온다

      for edge in edges {
              guard let outEdgeIndex = edge.first, let inEdgeIndex = edge.last else { continue }
              
              if nodes[inEdgeIndex] == nil {
                  nodes[inEdgeIndex] = .init(inEdge: 1, outEdge: 0)
              } else if nodes[inEdgeIndex] != nil {
                  nodes[inEdgeIndex]?.addIn()
              }
              
              if nodes[outEdgeIndex] == nil {
                  nodes[outEdgeIndex] = .init(inEdge: 0, outEdge: 1)
              } else if nodes[outEdgeIndex] != nil {
                  nodes[outEdgeIndex]?.addOut()
              }
          }

   4. 계산한 정점을 가지고 케이스 분류하기

      for (index, node) in nodes.enumerated() {
              if let n = node {
                  switch n.getOut() {
                  case 0: // 막대
                      answer[2] += 1
                  case 2:
                      if n.getIn() == 0 { 
                          startNodeNum = index
                      }
                      else if n.getIn() > 0 { answer[3] += 1 } // 8자
                  case let out where out > 2:
                      startNodeNum = index
                  default:
                      continue
                  }
              }
          }
          
          answer[0] = startNodeNum
          
          if let n = nodes[startNodeNum] {
              answer[1] = n.getOut() - answer[2] - answer[3]
          }
          return answer

전체 코드

struct Node {
    var inEdge: Int     // 들어온 간선 개수
    var outEdge: Int    // 나간 간선 개수
    
    init(inEdge: Int, outEdge: Int) {
        self.inEdge = inEdge
        self.outEdge = outEdge
    }
    
    mutating func addIn() {
        inEdge += 1
    }
    
    mutating func addOut() {
        outEdge += 1
    }
    
    func getIn() -> Int {
        return self.inEdge
    }
    
    func getOut() -> Int {
        return self.outEdge
    }
}

func solution(_ edges:[[Int]]) -> [Int] {
    
    var answer: [Int] = Array(repeating: 0, count: 4)
    var nodes: [Node?] = Array(repeating: nil, count: 1000001)
    var startNodeNum: Int = 0
    
    
    for edge in edges {
        // 시작 노드, 끝 노드 -> 시작 노드(outEdgeIndex)에서 간선이 나가서(outEdge) 끝 노드(inEdgeIndex)로 간선이 들어옴(inEdge)
        // [outEdgeIndex, inEdgeIndex]
        guard let outEdgeIndex = edge.first, let inEdgeIndex = edge.last else { continue }
        
        // 노드가 없으면 초기화를 하고, 있으면 값 증가
        if nodes[inEdgeIndex] == nil {
            nodes[inEdgeIndex] = .init(inEdge: 1, outEdge: 0)
        } else if nodes[inEdgeIndex] != nil {
            nodes[inEdgeIndex]?.addIn()
        }
        
        if nodes[outEdgeIndex] == nil {
            nodes[outEdgeIndex] = .init(inEdge: 0, outEdge: 1)
        } else if nodes[outEdgeIndex] != nil {
            nodes[outEdgeIndex]?.addOut()
        }
    }
    
    // 노드 순회
    for (index, node) in nodes.enumerated() {
        if let n = node {   // 노드가 존재할 경우
            switch n.getOut() {
            case 0: // 막대
                answer[2] += 1
            case 2:
                if n.inEdge == 0 { 
                    startNodeNum = index
                }
                else if n.inEdge > 0 { answer[3] += 1 } // 8자
            case let out where out > 2:
                startNodeNum = index
            default:
                continue
            }
        }
    }
    
    answer[0] = startNodeNum
    
    if let n = nodes[startNodeNum] {
        answer[1] = n.outEdge - answer[2] - answer[3]
    }
    
    
    return answer
}

func main() {
    print(solution([[2, 3], [4, 3], [1, 1], [2, 1]]))
}

main()

핵심 키워드

• enumerated()
• mutating