안녕하세요 구름알고리즘 먼데이 챌린지 2주차에 참여했습니다. 역시나 풀이를 진행해보겠습니다.
해당 게시물의 모든 출처는 구름 레벨의 알고리즘 먼데이 챌린지에 있습니다.
1번 문제
문제설명:
총 시험을 t번을 치른다. 이때 시험의 합격자를 가려내는 방법으로 매 시험 성적의 평균보다 이상인 사람을 합격자로 분류하기로 했다. 그렇게 분류를 하고, 매 시험마다 합격자의 수를 a, 응시자의 수를 b라고한다면 결과를 a/b의 형태로 나타내기로 한다. 이때, 시험 결과들을 출력하라.
해설:
매우 간단한 로직을 가지고 있는 문제이다. 평균을 구하고 모든 응시자를 순회하면서, 평균보다 높은지를 확인하면 된다. t번의 시험에 대해서 for문으로 반복만 시켜주었다. 또한, 결과물 출력같은 경우는 파이썬의 f-string을 이용하여 간편하게 하였다.
t = int(input())
for _ in range(t):
n = int(input())
l1 = list(map(int,input().split()))
mid = sum(l1)/n
count = 0
for k in l1:
if k>=mid:
count = count + 1
print(f'{count}/{n}')별다른 예외케이스가 없어 매우 간단한 문제.
2번문제
문제설명:
문자열 s가 주어졌을때, 아래의 기준에 따라서 문자열을 분리하고 분리된 개수를 출력하시오.
-
같은 문자끼리 하나의 집합이 된다.
-
같은 문자라도 떨어져 있다면 다른 집합이 된다.
예시로 문자열 aabbcca는 {aa}, {bb}, {cc}, {a}로 총 4개의 분리집합을 가진다.
해설:
우선 여담 하나를 하자면... 코딩문제를 풀때는 문제에서 쓰여있는 방법 그대로를 하면 물론 풀리겠지만 복잡하고 오래걸릴 위험이 큽니다. 위와같은 문제가 그렇습니다. 문제를 읽고 "아하~ 집합들을 분리시키면 되는구나" 에 매몰이 되면 문제를 어렵게 풀게 되겠죠. 이러한 알고리즘 문제를 풀때는 좀 다르게 생각할 필요가 있는것 같습니다.
분리된 집합의 개수를 구하는것이기 때문에 저희는 집합을 일일이 구할 필요가 없습니다. 어떤 경우에 개수가 늘어나는지만 확인하면 되겠죠.
이 문제에서는 문자열을 순회하면서 이전문자와 다음문자가 다르기만 하면 분리집합의 개수가 늘어나게 되는것입니다. 이때 첫문자는 자동 count를해야 겠죠.
aba와 같은 경우를 생각해볼까요. a에서 count = 1이 됩니다. 그 다음 b와 a를비교했을때 다르므로 count=2가 됩니다. 마지막 a도 이전의 b와 다르므로 count=3이 됩니다.
n = int(input())
l1 = list(map(str,input()))
count= 1
a = l1[0]
for k in l1:
if k !=a:
count = count + 1
a = k
print(count)flag를 바꿔가면서 순회해나가면 풀리는 간단한 문제입니다. 너무 "분리"라는 단어에 매몰될 필요가 없을거같습니다.
3번문제
문제설명:
N명의 사람들의 이름과 키 정보를 알고 있고, 그것으로 출석부를 만드려고 한다. 출석부의 순서는 이름을 기준으로 사전 순서로 정렬되어 있지만, 이름이 같다면 작은키부터 큰키로 오름차순 정렬을 하려고 한다. 이때 출석부를 완성하고 k번째 있는 사람의 이름과 키를 출력하시오.
해설:
결론부터 말하자면 이 문제는 파이썬의 key를 사용한 sorted를 사용할수있느냐를 묻는 문제이다.
파이썬의 sorted를 사용하면 데이터에서 원하는 값들을 기준으로 정렬을 시킬수 있으므로 이렇게 여러개의 key를 활용해서 정렬을 해야할때 유용하다.
우선 이름정렬이 우선이고, 그 다음이 키 정렬이다. 그렇다면 우리는 sorted를 사용할때는, 이것을 역순으로 해줘야한다. 단순하게 생각해서 이름정렬을 먼저하고, 키정렬을 해준다면 결과물은 키순서가 1순위가 되게 된다. 따라서 이렇게 정렬을해줄때는 우선순위의 역순으로 해주어야한다. 키를 먼저 정렬해주고, 이름정렬을 해주면 된다.
n,k = map(int,input().split())
dic = {}
l1 = []
for _ in range(n):
a,b = map(str,input().split())
dic[float(b)] = b
l1.append((a,float(b)))
def name_sorting(data):
return data[0]
def height_sorting(data):
return data[1]
l1 = sorted(l1,key=height_sorting)
l1 = sorted(l1,key=name_sorting)
print(f'{l1[k-1][0]} {dic[l1[k-1][1]]}')나같은 경우는 sorted를 해줄때 key에다가 함수를 넣어준다. 함수는 각 데이터의 몇번째 수를 참고할건지를 넘겨주었다.
또한 코드를 보면 기상천외한 dictionary코드가 존재하는데, 이것은 제 소숫점 formatting 실력 부족으로 소수점 둘째자리까지 출력에 실패하여... 차라리 input값을 미리 저장해놓고 그것을 그대로 출력하는 방법을 사용하였습니다.
해설을 참고하여 소수점 두자리까지 format의 경우는 print(f"{res:.2lf}") 로 표현할수있다는 것을 알게되었습니다.
4번문제
문제설명:
가로 세로 크기가 n인 정사각형이 있다. 이때 모든 칸에는 폭탄이 존재하는데 폭탄의 초기값은 0이다.
위의 그림과 같이 폭탄이 특정한 칸에 떨어지게 되면 그 칸과 그칸의 인접칸들에 폭탄이 터지게 된다. 그렇게 되면, 그 칸들의 폭탄 값은 1씩 증가하게 된다. 폭탄 값은 영향을 받는 횟수만큼 무한히 증가한다. 폭탄이 터지는 위치들이 모두 주어졌을 때, 모든 폭탄값들의 합을 출력하시오.
해설:
이 문제를 풀때도 너무 문제에서 말하는대로 풀 필요는 없다고 생각합니다(앞서 말한 2번문제처럼). 특히나, 그림을 보게 되면 더더욱 그런 생각이 들텐데요, 그림을 보면 2차원 배열을 만들어서 인접 행열들을 탐색하며 값을 추가해주는 방법이 먼저 떠오르게 될거같습니다(절대 틀린 풀이는 아닙니다). 그렇게 풀게되면 굉장히 하드코딩스럽게 풀리겠지만 저희는 간단히 생각을 해볼 필요가 있습니다.
위와 같은 경우처럼 일반적인 경우에는 폭탄이 터지면 총 5개의 폭탄값이 증가하게됩니다(폭탄값은 전체를 합한 폭탄값으로 관리합니다). 또한,
다음과 같이 빨간칸에 떨어지게 된다면 폭탄값이 4개가 증가하게 되겠죠. 이때는, 폭탄이 테두리에 떨어지게 될 경우입니다. 유념해야할점은 4개의 꼭지점이 아닌 나머지 테두리일 때라는 것입니다.
그렇다면 꼭짓점에 떨어진다면 어떻게 될까요?
이때는 폭탄이 3개가 늘어나게 되겠네요.
이렇게 저희는 총 3가지의 경우로 모든 폭탄의수를 나눌 수 있습니다.
1. 5개 늘어나는경우
2. 4개늘어나는경우
3. 3개늘어나는경우
그러면 저희는 폭탄이 떨어지는 index값만 조사해서 이게 테두리인지, 꼭짓점인지, 둘다 아닌지만 조사하면 끝입니다!
...
...
...
라고 제출을 하면 틀렸습니다가 나옵니다. 왜일까요??
바로 위의 전략은 정사각형의 크기가 3x3 이상일때만 성립하기 때문입니다. 따라서 크기가 1과 2일때는 다른 접근을 해야합니다(예외처리). 그러나, 매우 간단한것이, 크기가 1이면 폭탄값이 무조건 1씩늘어나고 크기가 2이면 폭탄값이 무조건 3씩 늘어나기 때문입니다. 따라서 간단하게 예외처리 해주면 됩니다.
n,k = map(int,input().split())
corner = [[1,1],[1,n],[n,1],[n,n]]
total = 0
for _ in range(k):
a,b = map(int,input().split())
if n ==1:
total = total + 1
elif n == 2:
total = total + 3
else:
if [a,b] in corner:
total = total + 3
elif a == 1 or b == 1 or a==n or b == n:
total = total + 4
else:
total = total +5
print(total)corner 꼭짓점을 미리 저장해두고, 문제를 해결하였습니다.
후기
아직까진 난이도가 평이한 수준입니다. 마지막 문제에서 예외처리 못해서 틀려준것을 제외하면 모두다 쉽게 풀만한 난이도였던것같습니다(그러고 3주차에서 첫번째 틀린문제를 ㅜ).
