No. 2309
1. Problem
2. Others' Solutions
- 첫 번째 방법
- 9명의 난쟁이 중에서 7명의 난쟁이를 고르는 순열 알고리즘 이용
import sys
def solution(n):
if n >= 7:
if sum(dwarf_arr) == 100: # 난쟁이가 7명인데 키의 합이 100이면 출력
for i in sorted(dwarf_arr) :
print(i)
exit()
else: # 아니면 계속해서 진행
return
for i in range(9):
if visited[i] == 1: # 해당 요소가 이미 순열의 요소면 다음 요소로 넘어감
continue
visited[i] = 1
dwarf_arr[n] = dwarfs[i] # n = 0~6 자리에 i 번째 난쟁이의 키를 저장
solution(n+1)
visited[i] = 0
dwarfs = [] # 9명의 난쟁이들의 키를 받을 리스트
dwarf_arr = [0] * 7 # 7명의 난쟁이를 선택했을 때의 리스트
visited = [0] * 9 # 해당 난쟁이를 선택했는지 여부를 설정하는 리스트
for _ in range(9): # 9명의 난쟁이들의 키를 입력 받음
dwarfs.append(int(sys.stdin.readline().rstrip()))
solution(0)
- 두 번째 방법
- 9명의 난쟁이들의 키 누적합에서 2명의 난쟁이 키를 빼서 100이 되면 출력
import sys
dwarfs = [] # 9명의 난쟁이들의 키를 받을 리스트
for _ in range(9): # 9명의 난쟁이들의 키를 입력 받음
dwarfs.append(int(sys.stdin.readline().rstrip()))
total = sum(dwarfs) # 9명의 난쟁이들의 키 누적합
dwarfs.sort()
for i in range(9):
for j in range(i+1,9):
if (total - dwarfs[i] - dwarfs[j]) == 100: # 2명의 난쟁이를 골라 키를 뺏을 때 100이면
for k in range(9):
if i == k or j == k: # 해당 2명의 난쟁이를 제외한 뒤 출력
continue
print(dwarfs[k])
exit()
3. Learned
- 되도록이면 좀 더 명확하고 간단한 알고리즘으로 구현하자
- 순열과 조합에 대한 개념과 차이점에 대해 알게됨
- 순열 참조 유튜브
No. 3085
1. Problem
2. My Solution
- candy[0][0] 부터 시작해서 행 방향으로 판단, 열 방향으로 판단
- 판단 중에 같으면 count++, 아니면 changed 값에 따라 분기
- 상하좌우로 바꿀 수 있기 때문에 상하좌우 바꿔보고 테두리 부분은 예외적으로 분기
- 중첩된 for 문과 너무 많고 복잡한 if 문 -> 실패
3. Others' Solutions
- 인접한 사탕을 바꿔본 뒤 행 방향, 열 방향 판단 -> 모든 인접한 사탕에 대해 교환한 뒤 판단 함수 수행
- O(N^4) - 판단함수에서 행방향, 열방향 판단 O(N^2), 모든 인접한 사탕 교환 O(N^2)
import sys
def check():
temp = 1
for i in range(n): # 행 판단
count = 1
for j in range(1,n):
if candy[i][j] == candy[i][j-1]:
count += 1
else:
count = 1
if count > temp:
temp = count
for j in range(n): # 열 판단
count = 1
for i in range(1,n):
if candy[i][j] == candy[i-1][j]:
count += 1
else:
count = 1
if count > temp:
temp = count
return temp
n = int(sys.stdin.readline().rstrip())
candy = []
result = 0
for _ in range(n):
candy.append(list(sys.stdin.readline().rstrip()))
for i in range(n): # 행 교환
for j in range(n):
if j + 1 < n: # 맨 끝 요소까지 갈 필요 없음
candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]
temp = check()
candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]
if temp > result:
result = temp
for j in range(n): # 열 교환
for i in range(n):
if i + 1 < n:
candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
temp = check()
candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
if temp > result:
result = temp
print(result)또는
import sys
def check():
temp = 1
for i in range(n): # 행 판단
count = 1
for j in range(1,n):
if candy[i][j] == candy[i][j-1]:
count += 1
else:
count = 1
if count > temp:
temp = count
count = 1
for j in range(1,n):
if candy[j][i] == candy[j-1][i]:
count += 1
else:
count = 1
if count > temp:
temp = count
return temp
n = int(sys.stdin.readline().rstrip())
candy = []
result = 0
for _ in range(n):
candy.append(list(sys.stdin.readline().rstrip()))
for i in range(n): # 행 교환
for j in range(n):
if j + 1 < n: # 맨 끝 요소까지 갈 필요 없음
candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]
temp = check()
candy[i][j], candy[i][j+1] = candy[i][j+1], candy[i][j]
if temp > result:
result = temp
if i + 1 < n:
candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
temp = check()
candy[i][j], candy[i+1][j] = candy[i+1][j], candy[i][j]
if temp > result:
result = temp
print(result)
4. Learned
- 생각해낸 해결 방법이 제대로 적용되지 않는다면 다른 방법으로 넘어가자
- 문자열 리스트 접근 방법 (리스트[] 내에서는 ',' 를 기점으로 인덱스 증가)
test =[["abc"],["abc"]]
print(test[0][0][1])
# 결과 -> b
print(test[0][1][1])
# 결과 -> out of index
test = ["abc", "abc"]
print(test[0][1])
# 결과 -> b
No. 1476
1. Problem
2. My Solution
- [1,1,1] 에서 모두 1씩 증가시키면서 e,s,m 최대값 도달하면 % 연산으로 1로 초기화
- 1씩 증가시킬 때마다 year 변수 또한 + 1
- esm == temp 참이면 year 출력
import sys
esm = list(map(int,sys.stdin.readline().rstrip().split()))
temp = [1,1,1]
year = 1
while(True):
if esm == temp:
print(year)
break
else:
temp[0] = (temp[0]+1) % 16
temp[1] = (temp[1]+1) % 29
temp[2] = (temp[2]+1) % 20
for i in range(3):
if temp[i] == 0:
temp[i] = 1
year += 1
3. Others' Solutions
- e,s,m 을 리스트가 아닌 각각 변수에 저장함
- year 를 e,s,m 의 최대값으로 각각 % 연산했을 때 나오는 값이 입력 받은 e,s,m 과 같은지 비교
- 최대값과 동일한 값인 경우 % 연산 후 0이 되기 때문에 비교전 똑같이 % 연산된 값을 e,s,m 에 각각 저장
e, s, m = map(int,sys.stdin.readline().rstrip().split())
e, s, m = e % 15, s % 28, m % 19
year = 1
while True:
if year % 15 == e and year % 28 == s and year % 19 == m:
print(year)
break
year += 1No. 1107
1. Problem
2. My Solution
- 고장나지 않은 버튼으로 조합할 수 있는 채널을 모두 구함 (목표하는 채널의 자리수, +1, -1)
- 조합된 채널중에서 채널과 가장 가까운 값과 목표하는 채널의 차이(abs) + 선택된 채널의 자릿수
- 조합을 구하는 과정에서 시간초과가 발생한 것 같음 (if 문으로 7자리 채널은 생성 x)
import sys
def permutation(level, length, arr): # 고장나지 않은 버튼으로 만들 수 있는 조합생성
if level >= length:
result.append(int(''.join(map(str,arr))))
else:
for i in range(10):
if button[i] == False: # 고장난 버튼은 제외
continue
arr[level] = i
permutation(level+1, length, arr)
channel = int(sys.stdin.readline().rstrip()) # 목표하는 채널
n = int(sys.stdin.readline().rstrip()) # 고장난 버튼의 수
button = [True] * 10
if n != 0:
not_working = list(map(int,sys.stdin.readline().rstrip().split())) # 고장난 버튼 입력 받음
for i in not_working: # 고장난 버튼은 False로 처리
button[i] = False
ch_len = len(str(channel)) # 목표하는 채널의 자리수
result = [] # 고장나지 않은 버튼으로 만들 수 있는 조합
if ch_len != 1:
arr_1 = [0] * (ch_len - 1)
permutation(0, ch_len - 1, arr_1)
arr_2 = [0] * (ch_len)
permutation(0, ch_len, arr_2)
if ch_len != 6:
arr_3 = [0] * (ch_len + 1)
permutation(0, ch_len + 1, arr_3)
count = abs(channel - 100) # + - 버튼으로만 움직였을 때의 count
for i in result: # 조합 중에서 목표하는 채널과 가장 가까운 채널까지의 버튼 수와 + - 버튼 수
if abs(channel - i) + len(str(i)) < count:
count = abs(channel - i) + len(str(i))
if channel == 100:
print(0)
else:
print(count)
3. Others' Solutions
- 0번 채널에서부터 1000000 채널까지 각각 현재 버튼으로 만들 수 있는지 판단
- 만들 수 있다면 해당 버튼에서 + - 버튼을 얼만큼 눌러야 되는지와 채널의 자릿수를 더함
- 0 ~ 1000000 인 이유는 500000 보다 높은 채널에서 - 하는 경우도 있기 때문임
- set 을 list로 바꾼 뒤 int(i) 연산을 수행하면 모든 경우에 연산이 이루어지므로 시간 소요가 2배나 걸림
import sys
channel = int(sys.stdin.readline().rstrip())
result = abs(100 - channel)
n = int(sys.stdin.readline().rstrip())
if n:
button = set(input().split())
# list(map(int,sys.stdin.readline().rstrip().split()))
else:
button = []
for num in range(1000001):
for i in str(num):
if i in button: # list -> int(i)
break
else:
result = min(result, len(str(num)) + abs(num - channel))
print(result)
4. Learned
-
for - else 구문
- for 반복문이 break 등으로 중단되지 않았을 경우 수행되는 else 문 -
문제에 주어진 테스트 케이스는 핵심 및 대표적인 경우임, 여기서 예외적인 테스트 케이스 등을 파악해서 버그를 잡도록 하는 것이 중요
-
1 2 3 4 숫자로 만들 수 있는 모든 조합을 생각해볼 때, 조합 알고리즘도 가능하지만 0 ~ 4321 까지 모든 수를 각각 1,2,3,4 숫자로 만들 수 있는 지 판단해도 됨
