[백준 - Swift] 10799 쇠막대기

문제

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

10799번: 쇠막대기

 

 

풀이

#1 시간 초과

 

 1. 기존 배열에서 레이저 변형해서 새 배열 만들기

 2. 새 배열에서 for문 돌면서 레이저의 위치 담긴 배열, 쇠막대기 위치 정보 담긴 배열 만들기

 3. 쇠막대기 배열 for문 돌면서 레이저 중 자신의 범위에 있는 개수 더하기

 4. 전체 다 돌고 마지막에 총 쇠막대기 개수 더해서 출력하기

 

-> 기존의 방법에는 각각 lazers, rods를 동시에 반복해야 하기 때문에 시간이 초과됐음. stack 또는 Array 문제는 해당 자료구조를 한 번만에 순회해서 답을 도출하는 방식이 주로 정답인 것 같다.

 

 

#2 한 번의 순회로 끝나는 방식

 

1. 기존 배열에서 레이저는 L로 대체해주고

2. 이 문자열을 돌면서

2-1. 만약 (이라면, 막대기 개수 +1

2-2. 만약 )이라면, 막대기 개수 -1

2-3. 만약 L이라면, 계산했던 막대기 개수만큼 더하기

3. 마지막에 막대기 총 개수만큼 또 더해서 출력

 

 

코드

// #1 시간 초과

import Foundation

let input = Array(String(readLine()!).replacingOccurrences(of: "()", with: "L"))
var lasers = [Int](), stack = [Int](), rods = [(front: Int, rear: Int)](), ans = 0

for i in 0..<input.count {
    switch input[i] {
    case "L": lasers.append(i)
    case "(": stack.append(i)
    case ")": rods.append((stack.removeLast(),i))
    default: print("띠용")
    }
}


for (front, rear) in rods {
    ans += lasers.filter{ front <= $0 && $0 <= rear }.count
    
}

print(ans+rods.count)

// #2 한 번의 순회

import Foundation

let input = String(readLine()!).replacingOccurrences(of: "()", with: "L")
var rod = 0, ans = 0, allRods = Array(input).filter{$0 != "L"}.count/2

for char in input {
    switch char {
    case "(": rod += 1
    case ")": rod -= 1
    case "L": ans += rod
    default: print("띠용")
    }
}

print(ans + allRods)

 

+ 더 좋은 코드

• 내 코드에서 "()" -> "L"로 바꾸는 코드 생략
• 배열을 순회할 때 ")" 가 나오는 경우에 대한 처리 세분화 
• 쇠막대기 전체 개수 더해주는 방식 생략. 대신 ")"가 나올 때 막대기 개수 한 번 더 더해줌

import Foundation

let line = readLine()!.map{ String($0) }
var stack = 0
var count = 0

for i in 0..<line.count {
    if line[i] == "(" {
        stack += 1
    } else {
        stack -= 1
        if line[i-1] == "(" {
            count += stack
        } else {
            count += 1
        }
    }
}

print(count)