[백준] (Python/Swift) 3040번: 백설 공주와 일곱 난쟁이

📌 문제

3040번: 백설 공주와 일곱 난쟁이

 

 

📌 올바른 풀이

7개의 옳은 데이터를 찾는 게 아닌 그것의 여집합인 2개의 틀린 데이터를 찾는 것이 핵심이다.

그 2개의 데이터를 어떻게 다루냐에 따라 여러 방식이 있을 것이다.

 

1. 압도적으로 크거나 압도적으로 작은 수로 재할당 하거나
2. 처음 발견한 두 깂을 저장하여 배열에서 삭제하거나
3. 적당한 수(0이나 -1)로 재할당 하되, 이중 for 문을 한번에 break 하여 빠져 나오는 것이다.

 

---

 

아래의 내용은 초반에 잘못된 방식으로 접근하여 작성한 풀이와 코드이다.

 

📌 잘못된 풀이

1. 7개의 옳은 데이터를 찾는 게 아닌 그것의 여집합인 2개의 틀린 데이터를 찾는 것이 핵심이다.
2. 이중 반복문을 돌 때, Python의 range() 함수와는 다르게 이중 for 문에서 바깥쪽 for 문의 index를 신경써야 한다.
3. 따라서 바깥쪽에 maxIndex가 아닌 maxIndex - 1로 정확한 인덱스 값을 넣었다.

 

📌 문제점

이 풀이는 이중 for 문을 한번에 break 하지 못하면 문제가 발생한다.

 

아래처럼 디버깅을 해 보았다. break를 써도 반복문이 끝나지 않음을 알 수 있다.

왼쪽의 arr_of_dwarf에서 i가 0이고 j가 8일 때, 0을 2개로 만들면 break로 빠져 나와야 한다.

 

break를 써도 안쪽 for 문만 빠져 나온다. i가 1, j는 8로 반복문이 계속 도는 것을 확인할 수 있다.

 

 

📌 잘못된 코드

1. Swift

// 필요한 변수 초기화
var input: Int
var arrayOfDwarf = Array(repeating: 0, count: 9)
var sum: Int = 0

// 아홉 난쟁이에 대한 배열의 최대 index를 상수로 할당
let maxIndex = 8

// 아홉 난쟁이가 가진 수를 각각 배열에 담으면서 총합을 구하기
for i in 0...maxIndex {
    input = Int(readLine()!)!
    arrayOfDwarf[i] = input
    sum += input
}

// 이중 반복문을 돌며 두 수를 총합에서 각각 빼서 100이 나오면 그 요소를 -1으로 재할당
for i in 0...maxIndex - 1 {
    for j in i + 1...maxIndex {
        if sum - arrayOfDwarf[i] - arrayOfDwarf[j] == 100 {
            arrayOfDwarf[i] = -1
            arrayOfDwarf[j] = -1
            break
        }
    }
}

// 배열을 돌면서 요소가 양수인 값만 출력
for i in 0...maxIndex {
    if arrayOfDwarf[i] > 0 {
        print(arrayOfDwarf[i])
    }
}

 

2. Python

import sys

# 테스트 파일 읽기
# sys.stdin = open("input.txt", "r")

# 입력 메서드 지정
input = sys.stdin.readline

# 변수 초기화
arr_of_dwarf = []
sum_of_dwarf = 0
dwarf = 0

# 입력값으로 배열과 총합을 할당
for _ in range(9):
    dwarf = int(input())
    arr_of_dwarf.append(dwarf)
    sum_of_dwarf += dwarf

# 총합이 100이 안되게 하는 두 난쟁이를 -1으로 재할당
for i in range(9):
    for j in range(i+1, 9):
        if arr_of_dwarf[i] + arr_of_dwarf[j] == sum_of_dwarf - 100:
            arr_of_dwarf[i] = -1
            arr_of_dwarf[j] = -1
            break

# 양수인 난쟁이만 출력
for dwarf in arr_of_dwarf:
    if dwarf > 0:

 

📌 후기

생각해 보면 되게 간단한 문제인데, 도저히 풀리지 않아 여기저기 헤맸다.

덕분에(?) 여러 방법을 시도해 보았다.

 

1. Array를 초기화 하는 방법을 알게 되었다. 

// 변경 전
var arrOfInt: [Int] = []

// 변경 후
var arrayOfDwarf = Array(repeating: 0, count: 9)

 

2. 계속 안 풀려서 for 문에서 stride() 함수를 이용해서도 접근해 봤다.

// 변경 전
let range: Int = arrOfInt.count

for i in 0..<range {
    for j in i+1..<range {
        if sum - arrOfInt[i] - arrOfInt[j] == 100 {
            arrOfInt[i] = 0
            arrOfInt[j] = 0
            break
        }
    }
}

// 변경 후
for i in stride(from: 0, to: maxIndex - 1, by: 1) {
    for j in stride(from: i, to: maxIndex, by: 1) {
        if sum - arrayOfDwarf[i] - arrayOfDwarf[j] == 100 {
            arrayOfDwarf[i] = 0
            arrayOfDwarf[j] = 0
            break
        }
    }
}

[Swift] stride() 함수로 숫자를 단계적으로 다루기

 

 

📌 문제 오류(?)가 아닌 접근 방식의 문제

문제 오류를 발견한 것 같은데, 내가 틀린 건지 의문이다.

1. 문제를 풀 때 처음에 -1이 아닌 0으로 재할당하니 계속 틀리다고 나왔다.
2. 값이 0이어도 분명 양수를 출력하는 것은 맞는데 왜 자꾸 틀리다고 하는지 이해가 가질 않는다.

결국 백준에 1~2번의 내용을 질문으로 올렸다.

 

혹시나 다른 분들도 이것에 대해 아는 것이 있다면 댓글로 알려주시길...

 

 

📌 잘못된 코드의 문제점 해결

결국 그에 대한 답변이 올라왔다.

 

내가 생각한 break는 이중 반복문을 모두 빠져 나오는 줄 알았는데

안쪽 루프만 1번 빠져나오고 결국 계속 실행되다가

실행되어 다른 억울한 난쟁이도 0으로 재할당 될 수 있었다.

 

결국, 이중 for 문을 한번에 break 하지 못해 발생한 문제이다.

 

만약 아래와 같이 데이터가 주어지면 -1로 틀린 답이 될 수 있다.

[2, 34, 7, 9, 11, 12, 13, 14, 4] // 총합 106

// 두 값을 찾을 때, 106에서 100을 뺀 6이 나오면 된다.

// 2와 4를 찾아 -1로 재할당
[-1, 34, 7, 9, 11, 12, 13, 14, -1]

// -1과 7를 찾아 -1로 재할당
[-1, 34, -1, 9, 11, 12, 13, 14, -1]

// 결국 6개만 출력
34
9
11
12
13
14