[Swift] 백준, 한 줄로 서기

문제 링크

백준 알고리즘 - 한 줄로 서기

잡담

뭔가 맨날 문제 어렵다고만 하는 거 같은데 ㅋㅋㅋ 이번엔 스스로 풀어봤어요 그런데 이번에도 역시 테스트 케이스는 맞았으나 제출했더니 틀렸다고 나오더라구요 ㅡㅡ 🤪

그래서 결국 다른 블로그를 참고했는데, 뭔가 생각했던 방식은 그대로 인 것 같은데… 반례가 뭔지 아직도 모르겠네요..

풀이

제가 생각했던 풀이 방식은 각 인덱스마다 왼쪽에 있는 자신보다 큰 수의 개수를 알 수 있는데, 1부터 차례대로 입력받은 값을 인덱스로 다른 배열에 넣어줍니다.

만약에 그 인덱스에 이미 다른 요소가 있다면, 다음 칸으로 계속 이동해서 다른 요소가 없는 칸에 값을 넣어줍니다.

흠.. 뭔가 풀이 자체는 다른 블로그랑 똑같은거 같은데.. 혹시 이 글을 보시고, 반례를 아시는 분이 있다면 댓글 남겨주시면 감사하겠습니다.

코드

• 짠 코드 (틀렸습니다..)

//
//  main.swift
//  한줄로서기
//
//  Created by 남기범 on 2021/01/03.
//  Copyright © 2021 남기범. All rights reserved.
//

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.components(separatedBy: " ").map { Int($0)! }
var result = Array(repeating: 0, count: count)
var check = Array(repeating: false, count: count)

for i in 0..<arr.count {
    var num = arr[i]
    
    while check[num] && num < count-1 {
        num += 1
    }
    
    result[num] = i+1
    check[num].toggle()
}

for element in result {
    print(element, terminator: " ")
}

• 정답 코드

//
//  main.swift
//  한줄로서기
//
//  Created by 남기범 on 2021/01/03.
//  Copyright © 2021 남기범. All rights reserved.
//

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.components(separatedBy: " ").map { Int($0)! }
var result = Array(repeating: 0, count: count)
var check = Array(repeating: false, count: count)

for i in 0..<arr.count {
    var num = arr[i]
    
    for j in 0..<arr.count {
        if num == 0 && !check[j] {
            result[j] = i+1
            check[j].toggle()
            break
        } else if !check[j] {
            num -= 1
        }
    }
}

for element in result {
    print(element, terminator: " ")
}