https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.
28번 (1074) Z
해당 문제는 다른 문제를 다 풀고, 복습까지 하고 풀어보겠습니다.
29번 (2750) 수 정렬하기
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성해야합니다. 먼저 첫째 줄에는 수의 개수와 둘째 줄은 수가 들어가야하므로 input을 먼저 받습니다.
N = int(input())
list_x = [] # 리스트 생성
for i in range(N): # 인자 i를 N의 갯수만큼 받는다.
i = int(input()) # 인자 i에 입력
list_x.append(i) # x리스트에 입력된 i 추가
list_x.sort() # sort 함수로 리스트 내용 오름차순 정렬
# (사실상 sort는 for문 밖에 써도된다. 입력 받을 때마다 정렬하나 입력 다 받고 정렬하나 같으니까)
# print(list_x)
# 내가 여기까지 썻는데, 정렬은 되는데, 출력 조건처럼 안나오길래 찾아봤더니 for문으로 N번 돌려서 인자를 하나씩
# 출력하게끔 해야됐다.
# print(list_x)를 다음과 같이 바꾼다.
for i in range(N): # 인자 갯수 만큼 만복
print(list_x[i]) # N번까지 인자 i를 출력한다.for문으로 list의 인자값을 하나씩 출력시키는 것 외의 코드는 자력으로 짜봤는데, 쉬운 코드라도 자력으로 풀어보았으니 뿌듯한 감이 있다.
30번 (2751) 수 정렬하기 2
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성해야합니다. 전 문제랑 다른 점은 2750번은 N의 범위가 N(1 ≤ N ≤ 1,000)이었다면, 2751인 해당 문제는 N(1 ≤ N ≤ 1,000,000)로 입력 받는 범위가 크다.
기존의 2750 코드를 사용하면, 범위가 커서 시간 초과가 나온다. 그래서 조사를 해봤더니, input 대신 파이썬의 sys.stdin.readline()를 사용해서 처리해야한다. 왜냐하면, input으로 받으면 prompt message로 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느리다고 한다. 그러나 sys.stdin.readline()은 input과 반대로 개행 문자(\n)를 포함한다는 점 빼고는 빠르다는 장점이 있다.
import sys # sys.stdin.readline()를 쓰기 위해 임포트 해준다.
N = int(input())
list_x = [] # 리스트 생성
for i in range(N): # 인자 i를 N의 갯수만큼 받는다.
i = int(sys.stdin.readline()) ### sys.stdin.readline()를 input 대신 써준다.
# sys.stdin.readline()을 쓸때 주의 점은 기본타입이 str의 개행 문자라 \n과 같이 저장되므로 int로 형변환해서 써야된다.
list_x.append(i) # x리스트에 입력된 i 추가
list_x.sort() # sort 함수로 리스트 내용 오름차순 정렬
for i in range(N): # 인자 갯수 만큼 만복
print(list_x[i]) # N번까지 인자 i를 출력한다.31번 (10989) 수 정렬하기 3
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하세요. 이제는 경우의 수가 더 늘어났다. N(1 ≤ N ≤ 10,000,000)로 입력 받는 크기가 더 커졌다. 또한 같은 숫자가 등장할 수도 있다. 기존의 2751 코드를 사용하면, 범위가 커서 시간 초과가 나온다. 그래서 또 조사를 해봤다. 이 문제의 주핵심은 1부터 9까지 나온 수를 오름차순 해야되는데 중복이 가능하다는 것이다. 그러면 1~9까지 각각 숫자의 중복 횟수를 세어서 그만큼 출력만 해주면된다. 구현을 위해 계수 정렬이라는 것을 여러 블로그를 참고해 구현해보았다. 다행히도 두번째 줄의 입력되는 자연수는 10000보다 작거나 같다는 조건이 있다. 해당 조건들에 부합하게 코드를 작성해보겠다.
import sys # sys.stdin.readline()를 쓰기 위해 임포트 해준다.
N = int(input()) # 수의 갯수인 N개를 받는다.
list_x = [0] * 10001 # 0 ~ 10000까지의 리스트 생성(N이 10000보다 작거나 같으므로)
# 누적합 구하기
for i in range(N): # 인자(수) i를 N의 갯수만큼 받는다.
input_n = int(sys.stdin.readline()) # sys.stdin.readline()를 input 대신 써준다.
# 해당 코드로 인자(수)를 받는다.
list_x[input_n] += 1 # list_x에다가 입력 받은 i 인자(수)의 등장 횟수만큼 카운트를 올린다.
# 세어진 인덱스 데이터만 출력
for i in range(len(list_x)): # list_x의 등장된 인자(수) 갯수 만큼 반복
for _ in range(list_x[i]): # list_x에 있는 각각의 입력된 i 인자(수)의 인덱스 갯수 호출
print(i) # i 인자(수) 등장 횟수만큼 i를 출력한다.수 정렬하기 -1,2 와 비슷해보여서 금방할 줄 알았는데, 계수 정렬이라는 개념을 이해하느라 시간을 꽤 사용했다. 계수 정렬을 어느정도 이해해도 코드로 구현할 줄 몰라 헤멧는데, 블로그 글들을 사용해 작성해보았다.
32번 (1181) 단어 정렬
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하세요.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
문제에서 고려할 사항을 살펴보았다. 길이가 짧은 순이며 길이가 같을 시 사전순이어야한다. 중복 단어는 제거해야한다. 첫째 줄엔 단어의 개수 N을 센다.
import sys
N = int(input())
list_word = [] # 단어 들어갈 리스트를 만든다.
for i in range(N):
i = str(sys.stdin.readline().strip()) # 인풋대신 readline으로 빠르게 받는다.
# 이렇게하면 개행 문자 \n을 같이 보여주므로 strip을 통해 제거해준다.
list_word.append(i) # 알파벳 리스트에 저장
setting_word = set(list_word) # 리스트의 값중 중복값을 set 함수로 없앤다.
list_word = list(setting_word) # set으로 인해 리스트가 풀렸으므로 다시 리스트화 시킨다.
list_word = sorted(list_word) # 리스트의 값을 알파벳순으로 정렬한다. (둘째 조건)
list_word = sorted(list_word, key = len) # 리스트의 값을 길이 순으로 재정렬한다. (첫 조건)
# key를 통해 정렬기준 길이로(len) 조정 가능
# 조건 우선 순위가 높은 걸 밑에 적어야한다. 코드는 순차적으로 처리하므로
for i in list_word: # 리스트에 있는 요소(알파벳)들을 한 줄씩 출력, 범위가 따로 필요없어 간단히 출력된다.
print(i)전과 달라 살짝 당황했지만, set으로 중복값을 없앨수 있고 list로 다시 묶어줘야한다는 것을 알았다. 조건의 우선순위가 높은 것을 나중에 수행해야하고, key = len 을 통해 길이 순으로 리스트를 정렬할 수 있다는 사실을 깨달았다. 전과 달리 정해진 N회차 만큼 리스트 요소를 프린트 안해도 간단하게 바로 출력하는 방법도 알게 되었다.(간편한 방법이 있었구나...)
33번 (2309) 일곱 난쟁이
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하세요. 라는 것이 문제의 시작이다.
이거는 9명의 난쟁이 중에 7명의 난쟁이를 뽑아 100을 출력하면 된다. 그러면 7명의 난쟁이가 100인 조합을 찾으면 된다. 말이 쉽지 재귀함수를 사용해서 계속해서 일일이 돌려서 찾아야된다는 것인데... 코드로 어떻게 구현할 지 감이 도저히 잡히지 않아서 블로그 글을 참고 했다. 푸는 방식이 for, combinations, 재귀 함수가 있는데 재귀함수로 구현해 보겠다.
shortmen = [int(input()) for _ in range(9)] # 난쟁이들의 값을 9개 받는다.
seven_sum = [] # 해당 리스트로 난쟁이 7명을 뽑아 합을 비교한다.
def dfs(depth, start): # dfs 요소는 (배열, 시작 위치, 방문 정보)로 구성되어있는데, 해당 코드에는 방문 정보는 없다.)
if depth == 7: # 7번의 재귀를 돌렸다면 시행
if sum(seven_sum) == 100: # 현재 저장된 일곱난쟁이들의 합이 100이라면
for j in sorted(seven_sum): # 오름차순으로 정렬 후 출력
print(j)
exit() ## 위 조건을 모두 만족하면 코드를 종료합니다.
else: # 7명을 뽑고 나서 합이 100이 아니라면 시행 위에 if과 세트
return # 해당 재귀를 실행하지 않고 종료 왜냐? 적합하지 않은 조합이니까
for i in range(start, len(shortmen)) : # 시작부터 9명의 난쟁이가 있으므로 9번을 반복한다.(7명 추가 과정)
seven_sum.append(shortmen[i]) # 난쟁이들 중에서 한명을 비교 리스트에 추가한다.
dfs(depth + 1, i + 1) # 상단의 dfs로 가서 검사한다.
# 다음 번 깊이(배열)은 +1로 해주고(다른 검사 세트) 인덱스는 중복되지 않기 위해 다음 인덱스를 넣어준다.
seven_sum.pop()
# dfs 검사를 수행하다가 7명이 다 찼으나 합이 100이 되지 않아 리턴되었다면 난쟁이 한명을 다시 뺀다. 이후 다른 난쟁이 넣고 검증한다.
# 해당기능이 백트래킹 역할을 수행한다. 만약 한명 빼도 100이 리턴되지 않으면 한 명 더 빼고 탐색한다.
dfs(0,0)
# depth=0, start=0의 의미로 현재 선택된 난쟁이수가 0명이고 탐색을 시작할 남쟁이의 인덱스는 0번이라는 소리다.
# 이말은 곧 0번 난쟁이부터 하나씩 선택하면서 7명을 찾는 dfs를 시작하는 역할을 한다.이거는 거의 블로그글을 하나하나 뜯어보면서 클론코딩 했기 때문에 자력을 할 수 있을 때까지 노력해야한다. 재귀함수와 백트래킹을 코드로 구현하는 것이 개인적으로 많이 어렵다…
다음 문제인 차이를 최대로 문제가 이해가 되지 않아 낼 다시 풀어보겠다. 오늘은 운동을 해야되므로 1시에 퇴근해야 하는 이유도 있다. 지속적으로 운동안하면 체력이 받쳐주질 못해 학습도 못한다.
