두잇뚜의 블로그

문제 링크 : https://leetcode.com/problems/remove-duplicates-from-sorted-array/ 난이도 : Easy 문제 풀이 : 배열안에 존재하는 중복되는 숫자들을 단 한개씩만 남도록 하는 것이 문제의 핵심이다. 정답을 위한 조건으로는 중복을 제거한 숫자들의 갯수가 몇개인지를 반환하고 nums 배열에 순서대로 재정렬 해야한다. 중복을 제거한 숫자들의 갯수는 Set을 이용하여 간단하게 구할 수 있었다. 문제는 nums 배열의 값을 재정렬 해 주는 것이었는데, 이것도 사실 생각해보니 간단했다. 현재 중복되어 변경할 인덱스를 하나 만든다. 그리고 루프를 돌며 numSet에 존재하지 않는 숫자면 numSet에 넣고 nums 배열의 인덱스 위치의 값을 변경해준 후 인덱스를 ..

문제 링크 : https://leetcode.com/problems/merge-two-sorted-lists/ 난이도 : Easy 문제 풀이 : 컴퓨터공학 또는 프로그래밍을 공부한 사람이라면 Merge Sort에 대해 알 것이고 굉장히 익숙한 느낌을 받을 것이다. Merge Sort의 한 부분과 동일하기 때문이다. 1. Int Array 두 개를 합치므로 합친 사이즈인 m+n 만큼의 IntArray를 생성한다. 2. 두 개의 Array를 순회하며 작은 것부터 임시 Array에 추가한다. 3. 위 과정을 거치면 둘 중 하나의 Array는 요소들이 남아있게 된다. 남아있는 요소를 임시 Array에 마저 추가한다. 4. nums1 배열에 결과가 담겨 있어야 하므로 임시 Array의 값을 복사해준다. 소스 코드..

문제 링크 : https://leetcode.com/problems/valid-parentheses/ 난이도 : Easy 문제 풀이 : 자주 접하는 괄호 짝 맞추기 문제다. 스택을 사용하면 어렵지 않게 풀 수 있다. 여는 괄호인 (, [, { 가 나오면 스택에 담고, 닫는 괄호인 ), ], } 가 나오면 스택의 Top에 있는 것을 빼내어 짝이 맞는지 검사한다. Top에 쌓인 것이 없거나, 무사히 for-loop를 빠져나왔더라도 마지막에 스택이 비어있지 않을 수 있다. 이 부분만 잘 고려하면 어렵지 않게 풀 수 있따. 소스 코드 : class ValidParentheses { fun isValid(s: String): Boolean { val stack = Stack() for(bracket in s) {..

문제 링크 : https://leetcode.com/problems/longest-common-prefix/ 난이도 : Easy 문제 풀이 : 주어진 문자열들이 공통으로 갖고 있는 가장 긴 접두어를 찾는 문제다. 가장 긴 접두어는 가장 짧은 문자열의 길이보다 작거나 같다는 것만 생각하면 어렵지 않게 풀 수 있다. 가장 짧은 문자열을 기준으로 모든 문자열들의 맨 앞부터 시작하여 공통으로 가지고 있는 것들을 더해가면 된다. 소스 코드 : class LongestCommonPrefix { fun longestCommonPrefix(strs: Array): String { if(strs.isEmpty()) return "" else if(strs.size == 1) return strs[0] val sorted..

문제 링크 : https://leetcode.com/problems/roman-to-integer/ 난이도 : Easy 문제 풀이 : Symbol에 대하여 정해진 값이 있다. 그리고 이 Symbol들을 조합하여 숫자를 표현한다. 이 때, 어떤 Symbol 두 개의 조합은 특정한 숫자를 나타낸다는 조건이 있다. IV(4), IX(9), XL(40), XC(90), CD(400), CM(900) 에 해당한다. 어떤 Symbol에 해당하는 값을 매핑시켜야 하고 조합이 몇 개 되지 않으므로 HashMap 자료구조를 사용하여 이 조합들의 값을 매핑시킨다. 그리고 주어진 문자열을 순회하면서 조합에 해당하는 값을 더해준다. 소스 코드 : class RomanToInteger { companion object { va..

문제 링크 : https://leetcode.com/problems/reverse-integer/ 난이도 : Easy 문제 풀이 : 주어진 숫자를 거꾸로 뒤집는 문제이다. 10으로 나눈 나머지를 계속하여 자릿수를 만들면서 더해주면 뒤집을 수 있다. 다만 주의할 점은 32-bit signed integer를 사용한다는 부분이다. 이 Integer의 범위를 넘어간 값은 0을 반환해야 한다. 그래서 결과값이 이 범위를 넘어가는지 안넘어가는지 체크하기 위해 Long 자료형을 사용해야 한다. 소스 코드 : class ReverseInteger { fun reverse(x: Int): Int { var answer: Long = 0 var num = x while(num != 0) { answer = answer ..

문제 링크 : https://leetcode.com/problems/two-sum/ 난이도 : Easy 문제 풀이 : nums 배열에서 target을 만들 수 있는 두 개의 숫자 조합을 찾아 인덱스를 IntArray로 반환하는 문제이다. 두 숫자를 각각 A, B라 하고 두 숫자를 합쳤을 때 나오는 값을 C라고 하자. 그럼 A+B=C 이다. A를 선택했을 때, C를 만들 수 있는 숫자 B는 C-A로 구할 수 있다. 그렇다면, A를 선택했을 때 나머지 숫자들 중 B가 존재하는지 여부를 알고 그 B의 위치를 알면 답을 구할 수 있다. 두 개의 for-loop을 사용하여 풀 수 있지만, 시간복잡도를 낮추기 위해 HashMap 자료구조를 사용한다. HashMap의 Key에 숫자를, Value에 그 숫자의 위치를 ..

# 문제 # 문제 접근 문제만 봤을 때 굉장히 복잡할 것 같다고 느낀 문제였다. 우선 괄호로 이루어진 입력이 보기가 쉽지 않았다. 중요한 것은 "()" 모양으로 된 것은 레이저 라는 것이다. 그래서 ()를 레이저(R)로 표시한 후 생각하였다. 예시의 입력은 R(((RR)(R)R))(R) 로 바뀌게 된다. 막대기가 하나 완성이 되기 위해선 "(" 과 ")" 가 필요하다. 괄호 쌍을 맞추는 알고리즘 문제를 풀어 본 적이 있는가? 이와 유사하다. 스택에 "("를 만나면 쌓고, ")"를 만나면 스택으로 부터 pop 하여 쌍을 맞추게 되는 것이다. 그럼 R을 만났을 땐 어떻게 할 것인가? "("가 스택에 쌓였다는 것은 막대기가 하나 생성되었다는 것을 의미한다. "("가 N개 스택에 쌓였다는 것은 막대기가 N개 생..

# 문제 # 문제 접근 가격이 떨어지지 않았다는 것은 배열의 한 시점을 기준으로 뒤로 갈 수록 현재 시점보다 가격이 낮은 순간이 있는지를 판단하면 된다. 주의할 부분은, 3초 시점의 3은 바로 다음의 4초에 2로 떨어졌으나, 1초 간 가격이 유지 된 것으로 판단하여 떨어지지 않은 것으로 본다는 것이다. 바로 다음 시점에 가격이 떨어져도 1초간 가격은 유지가 된 것이다. # 문제 풀이 1. 배열의 처음부터 끝까지 루프를 돌린다. (i) 2. 현재 배열의 위치부터 다음 위치까지 루프를 돌린다. (j) 3. 인덱스 j가 증가하면 현재 시점의 카운트를 1 늘린다.(위에서 주의했듯이 바로 다음 순간에 떨어져도 1초간 가격이 유지 된 것이기 때문.) 4. 배열의 i 인덱스의 값이 배열의 j 인덱스 값보다 크면 시점..

# 문제 # 문제 접근 신호가 오른쪽에서 왼쪽으로 간다는 조건만 이해하면 어렵지 않은 문제였다. 자신의 위치를 기준으로 왼쪽방향으로 진행하면서 자신보다 높은 가장 먼저 만나는 탑을 기록하면 된다. 스택/큐 로 분류되어 있어서 스택으로 풀까 하였지만, 굳이 사용 할 필요가 없었다. # 문제 풀이 1. 탑 배열의 가장 뒤부터 순회를 시작한다. 2. 현재 탑의 위치를 기준으로 다시 배열을 뒤에서 앞으로 순회한다. 3. 현재 탑보다 높이가 높은 탑을 만나면 기록하고 다음 탑에서 반복한다. # 코드 작성 def solution(heights): # 배열의 길이, 계산을 용이하게 하기 위해. LEN = len(heights) # 정답 배열, 신호를 받지 못한 탑의 값인 0으로 미리 초기화한다. answer = [0..