크래프톤 정글 week01, day09 - 알고리즘 문제

수 정렬하기

• n개의 수가 주어졌을 때, 오름차순으로 정렬하고 중복은 제거해야 한다.

n = int(input())
arr = []
result = []

# 입력값 받아 arr배열에 넣기
for i in range(n):
    arr.append(int(input()))

# 배열의 앞 뒤를 하나씩 비교해 앞이 뒤보다 크면 값을 바꾸기
for i in range(len(arr)-1):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            continue

# 중복 제거, arr안에 i값이 없으면 result배열에 넣기
for i in arr:
    if i not in result:
        result.append(i)

for i in range(len(result)):
    print(result[i])

 

맘 같아선 sort 사용하고 싶었지만 문제 푸는게 목적이 아니라 문제에 사용할 정렬을 학습하는 것이 목적이였기 때문에 버블정렬을 사용해서 작성했다.

• • 정렬의 앞과 뒤를 비교해서 뒤가 작으면 교환하는 식으로 작성했다.
  • 파이썬에서만 되는건진 모르겠는데 (변수, 변수 = 값, 값) 하면 복수의 변수에 값을 넣을 수 있더라

전날에 어려운 문제 풀다가 오늘 시작을 할만한 걸로 푸니까 스타트가 좋다.

​

• 수 정렬하기 2 문제는 1과 문제는 같지만 최대값을 매우 높게 책정해서 기존 코드로는 시간 에러나 출력 에러가 뜬다
• 파이썬은 다른 언어보다 너무 무거워 정렬도 다 빼고 sort()를 이용했고, 입력값도 input()이 아닌 sys.stdin.readline이라는 걸 사용했다.
  • 어디서 들은걸론 input은 입력 시 메세지를 처리하는 게 있어서 느리다고 하고 sys는 메세지없이 입력만 받아내서 빠르다고 들었다.

import sys

n = int(input())
arr = []

# 입력값 받아 arr배열에 넣기
for i in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort()

for i in arr:
    print(i)

 

결국 파이썬 기능 쓸거 다 쓰고 성공, 백준은 가끔 최대값 설정이 거지같아서 뉴비는 문제 풀기가 힘들다​.

 

​단어 정렬

• 알파벳 소문자로 이루어진 n개의 단어를 입력 받고 길이가 짧은 것부터 정렬하고, 길이가 같으면 사전 순으로 하고 중복 제거해야 한다.
• 예를 들어 5개 입력 받고, b, a, a, c, d 입력 받으면 a, b, c, d가 출력되게
• 근데 이것도 최대값이 너무 커서 일반적인 정렬 문제로는 시간에러나 출력에러가 났었다.

# import sys

# n = int(input())
# words = []

# # 단어를 입력받으면 \n까지 입력되서 strip으로 잘라주고 단어의 길이와 함께 객체로 저장
# for _ in range(n):
#     word = sys.stdin.readline().strip()
#     words.append((len(word), word))

# # 첫 단어부터 마지막 단어까지 쭉 정렬하기
# for i in range(len(words)):
#     for j in range(len(words) - 1):
#         if words[j] > words[j + 1]:
#             words[j], words[j + 1] = words[j + 1], words[j]

# # 배열을 쭉 돌려서 중복된 단어가 있으면 단어를 삭제해서 인덱스가 줄어들고 없으면 i를 1 증가시켜서 인덱스를 넘긴다
# i = 0
# while i < len(words) - 1:
#     if words[i] == words[i + 1]:
#         del words[i]
#     else:
#         i += 1

# # 출력
# for word in words:
#     print(word[1])

import sys

N = int(sys.stdin.readline())
text = []

for i in range(N):
    text.append(sys.stdin.readline().strip())
# 중복 제거를 위해 set 사용
set_text = set(text)
text = list(set_text)

text.sort()
text.sort(key=len)
for i in range(len(text)):
    print(text[i])

 

결국 이것도 작성한 걸로 최대값은 에러가 나서 열심히 지피티에서 검색한 코드로 성공했다.

나중에 퀵정렬을 직접 구현할 수 있게 되면 다시 한번 해보려고 한다.

​

일곱 난쟁이

• 백설공주 밑의 7마리의 난쟁이가 일을 하고 왔는데 9명이 되서 돌아왔다. 하지만 난쟁이 7마리의 키를 모두 합하면 100이 되는데 이걸 이용해 2마리를 쳐내야한다.
• 완전탐색을 이용해 7마리인 모든 경우의 수를 돌려 100이 되는 배열을 찾아야 한다.

from itertools import combinations

arr = []

for i in range(9):
    arr.append(int(input()))

# combinations라는 기능을 이용해 7개의 숫자를 경우의 수가 되는대로 전부 담기
find = list(combinations(arr, 7))

# 경우의 수 안에서 7개 값이 100개일 경우 list타입으로 바꾸어 arr에 담기
for i in find:
    if sum(i) == 100:
        arr = list(i)

# arr을 정렬시키고 출력
arr.sort()

for i in range(len(arr)):
    print(arr[i])

 

어떤 분은 suffle이라는 기능을 사용해 랜덤으로 7마리를 뽑아서 구현했고, 본인은 combinations라는 기능을 사용해 7마리가 되는 경우의 수를 알아서 리스트에 담아줬다

​

값은 리스트로 담겨있기 때문에 하나씩 다 돌려서 합한 후 100이 되면 그 값을 배열에 담아 정렬하고 반복문으로 출력한다.

아마 직접 코드를 짰으면 좀 더 걸리긴 하지만 짤 수는 있을 것 같다.

​

수 찾기

• 목록을 보여주고 그 안에 입력값이 있는지 찾아 있으면 1을 반환 없으면 0을 반환하는 문제이다.
• 이분 탐색으로 푸는 문제이며 내가 구현 해낼 수 있는 알고리즘이 나와서 재밌었다.

# 어차피 입력값 쪼개야해서 n값을 왜 받는진 모르겠지만 횟수 받기
n = int(input())
# n값만큼 받아서 쪼개 리스트에 저장하고 오름차수 정렬
arr = list(map(int, input().split()))
arr.sort()

# 찾을 데이터의 갯수 입력
n2 = int(input())
# n값만큼 받아서 쪼개 리스트에 저장
arr2 = list(map(int, input().split()))

# 이분 탐색으로 찾기
def binary_search(target, data):
    # 시작 과 끝 위치를 잡는다
    start = 0 
    end = len(data) - 1 

    # 시작에서 끝으로 가는동안 중간 값을 지정
    while start <= end:
        mid = (start + end) // 2

        # 찾고자 하는 값이 목록에 있으면 1을 리턴
        if data[mid] == target:
            return 1

        # 검색값이 중간값보다 작으면 중간값부터 끝까지 날리기
        elif data[mid] > target: 
            end = mid - 1
        # 검색값이 중간값보다 크면 처음부터 중간값까지 날리기
        else:              
            start = mid + 1
    # 목록에 없으면 0을 반환
    return 0

# 찾고자하는 수만큼 함수를 돌리고 그 값의 유무를 판단해 1 0 출력
for i in arr2:
    print(binary_search(i, arr))

 

목록과 찾을 값들을 입력 받고 구현한 이분 탐색 함수를 이용해 값을 찾는데 처음에 중간값과 같을 시 반환하는 걸 까먹고 중간 값 날아가는데 어디갔지 하면서 한참 헤맸다.

​

원래는 "N Queen" 문제나 "외판원 순회" 같은 중급 문제를 풀 차례였는데 도저히 못 풀겠어서 코드를 봤지만 그래도 모르겠다. 로직을 봐도 이게 왜 이렇게 되는지도 모르겠고 로직이 뭔지도 이해를 잘 못해서 일단 내일 하급 문제부터 다 풀고 로직을 이해하면서 풀려고 한다.

​

학습시간 : 10 ~ 25시