💻코딩문제풀이
+)
풀기만 하고 미뤄 뒀던 문제풀이들을 오랜만에 정리한다. 꾸준히 잘 올려야겠다는 다짐을 해본다!
🔎백준문제
#2012.등수매기기 <난이도:2> https://www.acmicpc.net/problem/2012
문제해설:
모든 학생 N명에게 자신이 N명중 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.
실수로 모든 학생의 프로그램이 날라가 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 상황이발생해, 어쩔 수 없이제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.
자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하여 등수를 매긴다.
ex1.
Input
5
1
5
3
1
2
Output
3
문제풀이(python)
n = int(input())
arr = []
arr = [0]*n
num,cnt = 0,0
for i in range(n):
arr[num] = int(input())
num += 1
arr.sort()
#print(arr)
for i in range(n-1):
if(arr[i] == arr[i+1]):
for j in range(i+1,n-1):
arr[j] += 1
cnt += 1
#print(arr)
print(cnt)
코드해설:
우선 입력받은 예상등수들을 오름차순으로 정렬한다.
이후 for문을 돌려 현재 인덱스와 다음 인덱스의 원소값을 비교해 값이 같으면 동일한 등수일 수 없으니, 값을 1증가시켜주는 작업을 반복한다.
#2923.숫자 게임 <난이도 :3>링크
문제해설: 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 다음과 같은 문제를 풀어야 한다.
지금까지 현우가 말한 모든 A와 모든 B를 짝짓는다. 이때, 각 쌍의 합 중에서 각 라운드 중 가장 큰 값을 작게 만들어라.
ex1.
-Input
3
2 8
3 1
1 4
-Output
10
10
9
추가 해설:
1라운드당 2개의 값을 받아와, 라운드에 관계없이 1번째로 받은 원소 + 2번째로 원소 값을 더 하는 가장 큰값을 작게 하는 방법은 1번째 받은 원소 중 가장 작은 값을 2번째 받은 원소의 가장 큰 값과 더하면 된다.
1라운드에 2와 8을 받으면 합이 10 뿐이다.
2라운드에 3 1까지 받은 상황에서는 (2+8, 3+1)과 (2+1,3+8) 경우가 있는데 첫번째 경우의 2+8 값이 우리가 찾는 값이 된다.
3라운드에는 1 4까지 받은 상황이기에 위 경우 뿐만 아니라 1+8 경우가 추가 되므로 9가 우리가 찾는 값이 된다.
문제풀이(python)
n = int(input())
arr1,arr2 = [],[]
i=0
j=-1
for i in range(n):
n1,n2 = input().split()
n1,n2 = int(n1),int(n2)
arr1.append(n1)
arr2.append(n2)
arr1.sort()
arr2.sort()
result1 = arr1[i] + arr2[j]
result2 = arr1[j] + arr2[i]
if result1 > result2:
print(result1)
else:
print(result2)
i+=1
j-=1
코드 해설 :
for문을 반복해 N라운드 동안 N번 입력 받은 두개의 값을 첫번째 값은 arr1에, 두번째 값은 arr2에 추가해 정렬해준 뒤 a라운드에서 받은 첫번째 원소 값, b라운드에서 받은 두번째 원소값의 합을 비교해준뒤 더 큰 값을 출력해준다.
🔎leetcode
#20. Valid Parentheses <난이도:4> 링크
해설: s는 '(', ')', '{', '}', '[', ']' 을 조합해 만든 문자열이다.
입력 문자열이 유효한 경우, 열린 괄호는 동일한 유형의 닫는 괄호로 닫아야한다.(즉, '('는')'로만 닫을 수 있다.)
열린 괄호는 올바른 순서로 닫아야합니다.(즉, 닫힌 괄호가 먼저 올 수 없다.그리고, 한 유형의 괄호가 닫히지 않은 상태에서 다음 인덱스에 다른 열린 괄호가 있어도 false로 인정한다.)
ex.1
Input: s = "()"
Output: true
ex.2
입력 : s = "([)]"
출력 : false
문제풀이(js)
푼 코드
var isValid = function(s) {
let mapLeft = {
'{' : 1,
'[' : 2,
'(' : 3
},
mapRight = {
'}' : 1,
']' : 2,
')' : 3
};
let stack = [];
for(let i = 0; i < s.length; ++i) {
if(mapLeft[s[i]]) {
stack.push(s[i])
} else if(!stack.length || mapRight[s[i]] != mapLeft[stack.pop()])
return false;
}
return stack.length ? false : true;
};#### 코드해설:
각각의 열린 괄호 유형을 mapLeft 딕셔너리에 담아줬고, 닫힌 괄호 유형을 mapRight에 담아줬다.
그리고 s의 원소를 확인하며 괄호가 각 유형에 맞는 열린괄호 닫힌괄호끼리 매칭이 된다면 true, 하나라도 그렇지 않으면 false를 반환한다.
이 문제는 다른 코드를 많이 참고하여 풀었다. 각 열린괄호가 꼭 닫힌괄호 보다 index가 앞에 있어야한다는 점을 고려할 때 특히 어려워 솔루션을 많이 참고하였다..
솔루션을 참고하지 않고도 잘 할 수 있도록 비슷한 유형을 많이 학습해보자.
< ✅난이도 >
-난이도 1,2 : 구글링 안하고 직접 푼 문제
-난이도 3: 직접 풀었지만 메서드 구글링한 문제
-난이도 4,5: 직접 못 풀고 답을 참고하여 푼 문제 (꼭 다시 풀어봐야 할 문제)_
다시 풀어볼 문제링크
앞으로 풀어볼 백준 문제 링크
