[Swift 알고리즘] 백준 20922 (겹치는 건 싫어)

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

20922번: 겹치는 건 싫어

 

 

 

https://www.acmicpc.net/board/view/74687

 

글 읽기 - 제가 만든 반례 Case 모음

-Test Case 모음

 

해결 방법 

간단하게 생각하면 투포인터로 풀면 된다.

아래 예시를 통해서 생각해 보자.

 

10 2

0	1	2	3	4	5	6	7	8	9
1	2	3	4	5	1	1	2	3	4

1 2 3 4 5 1 1 2 3 4

1. 일단 우리는 순차적으로 값을 읽어 나갈 것 이다. 읽으면서 tempArr에 저장한다고 가정하자

      tempArr = [1, 2, 3, 4, 5, 1]

2. 숫자를 읽으면서 따로 정의된 arr에 현재 읽은 값을 저장하자. 

arr[1] = 2, arr[2] =1 arr[3] = 1 ... 

 

3. 현재 읽는 값이 (arr[current]이) 최대 중복수와 같게 된다면, tempArr을 갱신한다.

    - tempArr = [... current ... ] 에서 tempArr = tempArr[(tempArr.firstIndex(of: current)! + 1) ... ] (current이후 값으로 갱신)

    - 또한 숫자가 얼마나 쓰였는지 확인하는 arr도 갱신시켜야 한다.

        - tempArr[0...tempArr.firstIndex(of: targetArr[i])!].map{hash[$0]! -= 1}

4. 이런식으로 끊길 때 마다 resArr.append(tempArr.count)로 배열을 차곡 쌓아가면 된다.

 

 

func sol2() {
    let inputN = readLine()!.split(separator: " ").map{Int($0)!}
    let targetArr = readLine()!.split(separator: " ").map{Int($0)!}
    var hash: [Int: Int] = [:]
    var resArr: [Int] = []
    var tempArr: [Int] = []
    for i in 0..<inputN[0] {
        //print(tempArr, hash[1])
        if hash[targetArr[i]] != nil { //만약 값이 존재 할 때
            if hash[targetArr[i]]! >= inputN[1] { //hash값이 임계값 보다 크다면
                resArr.append(tempArr.count)
                var postArr = Array(tempArr[0...tempArr.firstIndex(of: targetArr[i])!])
                postArr.map{hash[$0]! -= 1}
                tempArr = Array(tempArr[(tempArr.firstIndex(of: targetArr[i])! + 1)...])
                //print("i값은 ? =\(i)    postArr : \(postArr), tempArr : \(tempArr), 그 인덱스 : \(tempArr.firstIndex(of: targetArr[i])!), hash[1] = \(hash[1]!)")
            }
            hash[targetArr[i]]! += 1
        }else { //만약 hash값이 존재하지 않을 때
            hash[targetArr[i]] = 1
        }
        tempArr.append(targetArr[i])
    }
    if !tempArr.isEmpty {
        resArr.append(tempArr.count)
    }
    print(resArr.max()!)
}
sol2()

 

해결방법2

lind와 rind를 나눠 계산 한다.

 

func sol3() {
    let inputN = readLine()!.split(separator: " ").map{Int($0)!}
    let n = inputN[0], k = inputN[1]
    let targetArr = readLine()!.split(separator: " ").map{Int($0)!}
    var lInd = 0
    var rInd = 0
    var hashArr = Array(repeating: 0, count: targetArr.max()! + 1)
    var maxLength = 0
    while rInd < n { //만약 rInd가 target배열의 count보다 크면 종료
        if hashArr[targetArr[rInd]] < k { //tempArr에서 얼마나 쓰였는지 확인
            hashArr[targetArr[rInd]] += 1 //얼마나 중복 되었는지 갱신
            rInd += 1
        }
        else {
            hashArr[targetArr[lInd]] -= 1 //일단 leftInd에서 중복 수 갱신
            lInd += 1
        }
        maxLength = max(maxLength, rInd - lInd)
    }
    print(maxLength)
    
}
sol3()