본문 바로가기
728x90

코딩 테스트69

[LeetCode] 290.Word Pattern (Python) Problem Solutionarray 이전에 포스팅한 isomorphic string 과 동일한 문제.단지 스트링이 단순한 문자열이 아닌 단어로 이루어진 문장으로 변형한 문제.동일하게 sub string을 통해서 각 단어의 index 를 구한 후 pattern 과 비교하였다.  Codeclass Solution: def wordPattern(self, pattern: str, s: str) -> bool: answer = False patternLi , sLi = [], [] for p in pattern: patternLi.append(pattern.index(p)) sub_str = s.split() .. 2025. 1. 28.
[LeetCode] 205. Isomorphic String (Python) ProblemSolutionArray두 개의 문자열 s, t가 동형(isomorphic)인지 확인하는 문제. s에 존재하는 문자를 가지고 t를 만들 수 있으면 두 문자열 s, t는 동형이다. 단, 문자의 순서를 유지하며 모든 문자를 다른 문자로 바꿀 수 있어야한다. 두 문자가 같은 문자로 맵핑되어서는 안된다. 처음에 dictionary로 character 개수만 카운트해서 비교했는데 알고보니 문제 이해를 잘 못했다.엣지 케이스인 s = bbbaaaba, t = aaabbbba 에서 마지막에서 두번째 문자에서 조건을 만족하지 못하므로 falseCodeclass Solution: def isIsomorphic(self, s: str, t: str) -> bool: answer = False.. 2025. 1. 28.
[LeetCode] 202. Happy Number (Python) 1. 문제https://leetcode.com/problems/happy-number/description/?envType=study-plan-v2&envId=top-interview-1502. 풀이Hash 를 사용한 기본 문제. 문제 이해를 완벽하게 못해서 헤맸다.각 자리수를 제곱하여 sum 하는 사이클을 돌다가 만약 1로 끝나면 happy number 이므로 return true 아니면 return falsen=2 인 경우 2 -> 4 -> 16 -> 37 ->  58 -> 89 -> 145 -> 42 -> 20 -> 4 (cycle 발생)즉 방문했던 숫자를 또 방문하면 return false를 반환해야한다. 3. 코드class Solution: def isHappy(self, n: int) -.. 2025. 1. 27.
[HackerRank] Contacts (Python) 1.문제https://www.hackerrank.com/challenges/contacts/problem 2.풀이처음에 정직하게 구현으로 풀다가 time limit exceeded 나서 실패..단순해 보이지만 Time Complexity를 신경써서 풀어야하는 문제이다.def contacts(queries): answer = [] arr = [] for i in range(len(queries)): command = queries[i][0] if command == 'add': data = queries[i][1] arr.append(data) else: target = queries[i][1].. 2025. 1. 18.
[HackerRank] Find the Running Median (Python) 1. 문제https://www.hackerrank.com/challenges/find-the-running-median/problem 2. 풀이처음엔 a의 길이가 홀수, 짝수 케이스로 나누어서 단순히 중위값을 구하려고했다.참고로 python에서 n / 2 를 하면 실수를 반환하지만 n//2를 하면 int 정수를 반환한다.def runningMedian(a): answer = [] for i in range(1, len(a)+1): li = sorted(a[:i]) n = len(li) # odd if (n % 2 != 0): median = li[n // 2] else: med.. 2025. 1. 18.
[HackerRank] Tree: Level Order Traversal 1. 문제https://www.hackerrank.com/challenges/tree-level-order-traversal/problem 2. 풀이처음에 preOrder 문제로 잘 못 생각한 문제. 레벨을 기준으로 순회를 해야한다.아래 코드는 preOrder 코드def levelOrder(root): if root is None: return print(root.info) levelOrder(root.left) levelOrder(root.right) 레벨 기준으로 순회하려면 BFS 와 같이 queue를 사용해야한다.다른 사람 풀이를 보니 stack 과 queue 의 장점을 모두 가지고 있는 deque를 사용해서 deque 를 사용해서 해결한다. queue 의 inse.. 2025. 1. 18.
[HackerRank] Tree: Height of a Binary Tree (Python) 1.  문제https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem 2. 풀이Binary의 가장 높은 height를 구하는 문제.현재 root node 가 None이면 -1 반환재귀함수를 이용해서 왼쪽노드와 오른쪽 노드의 height 구한다. 시간 복잡도 : O(N) - 모든 노드를 한번씩 방문하므로 시간 복잡도는 N, N은 여기서 노드 수공간 복잡도 : O(H) - 재귀호출 스택의 공간 복잡도는 트리의 높이 H 와 동일 3. 코드def height(root): if root is None: return -1 depth_left = height(root.left) depth_right = height.. 2025. 1. 18.
[HackerRank] Balanced Brackets (Python) 1. 문제https://www.hackerrank.com/challenges/balanced-brackets/problem 2.풀이stack을 이용한 기본 문제 3.코드def isBalanced(s): st = [] print(s) for i in range(len(s)): if (s[i] == "(" or s[i] == "{" or s[i] == "["): st.append(s[i]) elif s[i] == ")": if (len(st) 0): return "NO" return "YES" 4.리팩토링dictionary 사용해서 중복된 코드 제거하기def isBalanced(s): stack = [].. 2025. 1. 18.
[LeetCode] Valid Parentheses (Python) 1.Quiz2.Solution전형적인 stack 문제. 코드를 깔끔하게 짜도록 연구해야겠다.다른 사람 코드를 보니 괄호를 미리 정의해두고 닫힘 괄호가 나타나면 stack의 마지막 값을 dict 를 사용하여 짝이 있는지 확인하도록했다.class Solution: def isValid(self, s: str) -> bool: parentheses = {"}":"{", "]":"[", ")":"("} stack = [] for char in s: if char in parentheses.keys(): if len(stack) and stack[-1] == parentheses[char]: stack.pop().. 2025. 1. 15.
[LeetCode] RansomNote (Python) 1.Quizhttps://leetcode.com/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150  2.Solutionmagzine 구성 문자로 reansomNote 문자를 만들 수 있는지 true / false 반환하는 문제다른 사람 풀이를 보니 set 을 사용해서 count 개수로 비교하여 ransomNote 가 magazine 보다 많으면 false 를 반환하도록 했다.class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: for char in set(ransomNote): if ra.. 2025. 1. 15.
[LeetCode] Find the Index of the First Occurrence in a String (Python) 1.문제https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150 2.풀이더 짧은 길이인 needle 문자열이 haystack 에 포함되어있는지 체크이중포문을 돌지않는게 포인트!다른 사람 코드를 보니 index 를 찾는 python method 가 있었다.class Solution: def strStr(self, haystack: str, needle: str) -> int: if needle in haystack: index1 = haystack.index(needle) .. 2025. 1. 15.
[LeetCode] 14.Longest Common Prefix (Python) 1.문제https://leetcode.com/problems/longest-common-prefix/?envType=study-plan-v2&envId=top-interview-1502.풀이1) 주어진 리스트의 원소를 길이순으로 정렬한다.2) 가장 짧은 단어를 기준으로 순환하여 비교한다.3) 반복문을 돌면서 해당 index 의 단어와 첫번째 단어의 index 가 동일한지 체크하고 동일하지 않다면 그 부분까지 substring 해서 반환한다. 3.코드class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if (len(strs) == 0): return "" if (len(str.. 2025. 1. 15.
[LeetCode] Length of Last Word (Python) 1.문제https://leetcode.com/problems/length-of-last-word/description/?envType=study-plan-v2&envId=top-interview-150 2.풀이공백을 기준으로 split 메소드를 사용하면 간단한 문제!  3.코드class Solution: def lengthOfLastWord(self, s: str) -> int: last_word = s.split()[-1] # print(last_word) return len(last_word) 2025. 1. 15.
[LeetCode] Roman to Integer 1.문제https://leetcode.com/problems/roman-to-integer2.풀이dictionary를 이용하여 푸는 문제. 모든 경우의 수를 조합하여 미리 dict 를 만들어도 되고, 주어진 문자열에 대한 값만 dict 로 만들어도된다.[다른사람 풀이]class Solution: def romanToInt(self, s: str) -> int: roman = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } res = 0 for i in range(len(s)): if i + 1  3.코드class Sol.. 2025. 1. 14.
[LeetCode] In Subsequence (Python) 1. 문제https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150 2. 풀이문자열 s 가 문자열 t의 subsequence 인지 확인하는 문제!시간 복잡도를 줄이는게 관건인 문제였다. 다른사람 솔루션을 보니 s의 길이 조건을 먼저 체크하고, s 의 pointer 만 확인해서 s 문자열을 다 체크했는지 확인 후 결과를 반환하도록하였다. 2중 포문을 안쓰는 방법 생각하기!!! [다른사람 풀이]class Solution: def isSubsequence(self, s: str, t: str) -> bool: if len(s) > len(t): return False.. 2025. 1. 13.
[프로그래머스] 6주차 - 복서 정렬하기 (C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/85002#qna 코딩테스트 연습 - 6주차 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 2. 풀이 문제의 기준에따라 정렬을해야하는 sorting문제. 승률을 구할때 자기자신과는 싸울 수 없어서 당연히 전체 경기 수 = 전체 복서 수 - 1 로 계산했다가 잘못 된 것을 인지하고 고쳤다. 경기를 안한 N도 있기때문에 전체 경기 수는 자기자신이 아니고 N인 경우를 제외한 W, L일 경우를 모두 카운트 해.. 2021. 9. 8.
[프로그래머스] 표 편집 (Python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/81303#qna 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 2. 풀이 처음에 배열로 풀었다가 효율성에서 걸려서 검색해서 다른 사람의 풀이를 참조했다. 이중 링크드 리스트로 풀어야하는 문제. 1번 인덱스부터 시작하여 처음에 현재위치(cur)을 +1 해주었다. prev와 next의 값을 저장하여 현재위치(cur)을 옮길 때마다 값을 갱신해준다. 그리고 삭제.. 2021. 9. 8.
[프로그래머스] 가장 먼 노드 (C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189/solution_groups?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 BFS를 활용한 그래프 문제. 1) 양방향 그래프이므로 그래프의 연결 상태를 저장하낟. 2) 1번 노드부터 시작하여 방문 여부를 체크한다. 3) 방문하지 않은 노드의 경우 dist 거리를 갱신하고 방문 여부를 체크, 큐에 저장 4) 2~3번 반복 5) dist에 저장한 거리 중 가장 최대 값을 구한다. 6) 최대값 max_val인 노드가.. 2021. 9. 8.
[프로그래머스] 입국심사 (C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43238/solution_groups?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 처음에 이게 왜 이분탐색 문제일까 고민했다.. 완전탐색으로 풀려하니 시간 복잡도에서 시간초과가 날 것 같았다. 그래서 다른 사람들의 풀이를 찾아보니 최소의 경우 (최소 소요시간 1분) ~ 최악의 경우 (제일 오래 걸리는 시간) 사이에서 이분 탐색으로 모든 사람의 심사를 완료하면서 최소의 시간을 찾는 문제였다. 그리고 각 심사관이 처리할 .. 2021. 9. 8.
[프로그래머스] 베스트앨범 (Python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 2. 풀이 1) 가장 많이 재생된 장르순으로 정렬한다. 2) 가장 많이 재생된 play 순으로 정렬한다. 3) play 수가 동일하면 가장 작은 index 먼저 정렬한다. 3. 코드 def solution(genres, plays): answer = [] genres_cnt = {} for i in range(len(g.. 2021. 9. 6.
728x90