TIL 0315, 조금 덜 간단한 문제 풀이

1065 한수

123, 234, 456, 159 등을 구하는 문제다.
생각해야 할 것은 1의 자리, 10의 자리의 수들은 모두 한수로 해당된다는 거,
그러면 1의 자리 | 10의 자리 | 100의 자리를 각기 구분하여 계산 할 생각을 하면 거의 다 온 것이다.

2628 종이자르기

대부분의 정글러가 여기서 조금 체류를 하는 듯 보였다.
나 또한 조금 신경이 쓰였는데, 전형적인 내용으로 통과했다는 말은 못하겠다.
우선 여기서 알려주는 입력은 3가지의 내용으로 나뉜다.

1. 자르게 될 사각형의 전체 정보
2. 자를 액션의 횟수
3. 액션의 상세 내용

나는 배열에 면적으로써 정의 할 수 있는 좌표 정보를 집어 넣어놓고
액션이 일어날때마다 영향 받는 면적들을 꺼내서 재 계산 하는 방식을 썼다.
즉, x가 10이고 y가 8인게 전체 범위라고 하자. 액션을 y 9 로 때려버리면 아무것도 해당이 없지만 y 4 라고 하면 해당이 있다.
내가 미리 세어둔 면적은 x10 y0-4, x10 y4-8로 찢어진다. 이런 식으로 이어 나가면 된다.

10872 팩토리얼

간단한 재귀함수 구현 문제였다.

1914 하노이 탑

목적지를 정하는데 있어 1번 탑, 2번 탑, 3번 탑 세 개를 써야했다. 1, 2를 쓰고 있으면 3번에 대한 개입, 1, 3을 쓰고 있으면 2번 탑의 개입. 여기서 참 많은 고민을 했는데, 결과적으로 전체 탑 번호의 합인 6에서 쓰고 있는 두 탑의 값을 뺌으로써 목표를 이룰 수 있었다. 좀 어이없어서 속상했던 기억이 있다. 

N-Queen

https://hyeonistic.tistory.com/17

[PY] 9663 : N-Queen

 

 

1074 Z

솔직히 이야기하면 과거의 내 기록을 조금 베껴왔다.
사분면으로 인해 split 해야하고 마지막 2 * 2 상황에서 조금 더 생각해보니 해결 할 수 있었다.
생각을 한번 해두었다보니 관성처럼 흘러온 덕분이지 처음 보는 문제였다면 상당히 당황스러웠을 것 같다.

2750 수 정렬하기, 2751 수 정렬하기 2

두 문제는 무식하게 Merge Sort 들어박으니 해결했었는데 파이썬으로 똑같이 하려니 잘 안된다.
그래서 잘하는 조원에게 물어보니 우선순위 큐 구현되어있는걸 쓰면 자동 정렬이 일어나니 그걸로 해결 하라고 해주셨다.
제일 범용적인 정렬이 Quick 이나 Merge가 아닌가 생각하지만 안되면 범용적인 라이브러리 로 해결 해야겠지?

10989 수 정렬하기 3

카운팅 소트를 구현했는데 파이썬 특유의 배열 정의가 익숙치 않아서 그런지 자꾸 생각치 않은 오류가 난다.
우선 작동은 하는데 이 부분에 대해 좀 더 고민해보려고 한다.

1181 단어 정렬

....

2309 일곱 난쟁이

주니어 코치님이 세 시간 뒤엔 답을 보라고 하셨는데 내가 다른 답을 생각해 낼 수 있는지에 대해 심하게 의구심이 들었다.
그래서 그냥 질답 게시판에서 그럴듯 한 답을 봤는데 여기서 좀 충격이었다.
100을 만들어 낼 수 있는 구성원이 아니라 100을 망치는 구성원을 찾아서 빼는 작업을 수행했다는 것이다.

그럼 기존에 100을 만들어 내는 작업 자체에선 뭐가 문제였을까?
9개 중 7개를 골라낸 다음 100이라면 출력하는 시스템을 갖췄었는데 특정한 케이스에서 아무것도 출력하지 못하는 상황이 발생했다.

11
12
26
13
15
18
3
9
7

하지만 질답 게시판에서 보고 구현한 100을 망치는 구성원을 제외한 코드로 해당 테스트 케이스를 시도하면 답을 갖고온다.
그렇다는건 내가 처음에 만든 100 만들기 코드가 잘못됐다는건데 이것만큼은 책상 밖에 있는 동안에도 생각을 좀 해봐야 할 것만 같다.

arr = [0] * 9
processDone = False

for i in range(9):
    arr[i] = int(input())
    # 9개의 배열을 정의하기

def func(choiced, cnt, lv):
    global processDone

    if(processDone):
        return

    if(cnt >= 7):
        total = 0
        for i in range(len(choiced)):
            total += choiced[i]

        if(total == 100):
            target = 0
            filterList = [x for x in choiced if x != target]
            filterList = sorted(filterList, reverse=False)
            for j in range(len(filterList)):
                # 정렬하고 0을 제거
                print(str(filterList[j]))
                processDone = True
            return
        else:
            return
    else:
        for j in range(lv + 1, 9):
            choiced[cnt] = arr[j]
            func(choiced, cnt+1, j)
            choiced[cnt] = 0

            if(processDone):
                return

for i in range(9):
    if(processDone):
        break    
    clearArr = [0] * 9
    clearArr[0] = arr[i]
    func(clearArr, i + 1, 0)

처음 구성했던 답

# 9개 중 7개를 고르는 것보다
# 100을 만드는데 망칠 여지가 있는 2개를 고르는대로 빼고 출력하는 방법
# 와 이렇게 생각 할 수가 있나

arr = [0] * 9
sum = 0

for i in range(9):
    arr[i] = int(input())
    sum += arr[i]

isFounded = False

for i in range(0, 8):
    for j in range(i + 1, 9):
        if (arr[i] + arr[j] == sum - 100):
            arr[i] = 100
            arr[j] = 100
            isFounded = True
            break
    if(isFounded):
        break

sortedArr = sorted(arr, reverse=False)

for i in range(7):
    print(sortedArr[i])

찾은 답. 배열 크기가 정확히 9개이지 않아서 잠시 오차가 있을뻔했다.