본문 바로가기
728x90

코딩 테스트101

[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.
[프로그래머스] 섬 연결하기 (C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 2. 풀이 네트워크와 비슷해보이지만 MST문제로 크루스칼 알고리즘을 사용해야한다. 1) 비용이 작은 순으로 정렬한다. 2) 최소 비용으로 다리를 연결하고 싸이클이 생기는지 확인한다. 1번 섬과 2번 섬이 연결되면 island[1] = 2, island[2] = 1이 된다. 3) 싸이클이 생기지 않으면 두 섬 사이에 다리를 연결한다. 1) ~ 3) 을 costs 길이만큼 반복!! *크루스칼 알고리즘: https://hyeri0903.tistory.co.. 2021. 9. 6.
[프로그래머스] 네트워크 (C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43162/solution_groups?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 DFS를 이용하여 n개 만큼 순회를 한다. 만약 1)방문하지 않고, 2)0이 아닌(길이있는) 경우 그 지점에서 순회를 시작한다. 순회가 끝나고 answer+1 해주면 끝! 3. 풀이 #include #include using namespace std; int visit[201]={0}; void dfs(int start, int n , .. 2021. 9. 6.
[백준] 외판원 순회 (C++) 1. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 알고리즘 테스트보다가 만난 문제. 처음에는 N이 16이하라 완전탐색(DFS) 방식으로 풀면 될 것이라 생각했지만 시간초과가 났다. 왜냐하면 모든 경우의 수를 따지면 16!만큼 연산을 해야하기 때문이다. 그리고 모든 점에서 시작하는 경우를 따지지 않아도 된다. 왜냐하면 만약 점 2에서 시작할 때 2 -> 1 -> 3 -> 2 가 최소 비용 .. 2021. 5. 29.
[Codility] Lesson14. MinMaxDivision (Python) 1.문제 https://app.codility.com/c/run/training77EUN5-7HZ/ Codility Your browser is not supported You should use a supported browser. Read more app.codility.com 2.풀이 어느 회사에 코딩테스트로 비슷한 문제가 나왔었던 문제. 그 당시에는 완전탐색 문제인 줄 알았는데 이 문제를 풀면서 이분탐색을 적용해서 푸는 문제였다는 것을 알았다. 아무리생각해도 어떻게 풀어야할지 몰라서 구글링해서 참고하였다.. ㅎㅎ case1. K == len(A) 일 경우 : 모든 원소의 sum 반환 case2. K >= len(A) 일 경우 : 만약 A=[1, 5], K=3 이면 [],[1],[5] 이므로 max.. 2021. 5. 26.
[Codility] Lesson12. Chocolatesbynumber (python) 1. 문제 2. 풀이 def solution(N, M): x = 0 eat = [0] while(1): res = (x + M) % N if res == 0: break eat.append(res) x = x + M return len(eat) 처음에 while문으로 문제에 나온 그대로 풀다가 Time out... 그래서 풀이를 찾아보았다. 초콜릿을 먹는 개수는 N,M의 최대공약수의 배수 개수만큼 먹는다. 결국 최대공약수를 구하는 문제 3. 코드 def solution(N, M): a, b = N, M while(b): a, b = b, a % b gcd = a #최대공약수 answer = N // gcd return answer 참조 : https://killong.blogspot.com/2019/12.. 2021. 5. 24.
[Codility] Lesson9. MaxSliceSum (Python) 1. 문제 https://app.codility.com/c/run/training2B63MW-T7C/ Codility Your browser is not supported You should use a supported browser. Read more app.codility.com 2. 풀이 테스트케이스 1개가 안풀려서 답을 찾아봤던 문제. 이 문제의 해결 포인트는 합이 음수가 나오기 전까지 계속 합을 더해주고, 음수가 나오면 그 다음 수부터 다시 누적합을 구하면된다. 왜냐하면 현재 음수보다 이전의 합이 더 작으면 앞으로 누적합을 더해도 합이 음수이기 때문에 그 만큼 합계가 작아지기 때문이다. 3. 코드 # you can write to stdout for debugging purposes, e.g. .. 2021. 5. 21.
[Codility] Lesson8. MaxDoubleSliceSum (Python) 1. 문제 https://app.codility.com/c/run/training7WK46H-9HS/ Codility Your browser is not supported You should use a supported browser. Read more app.codility.com 2.풀이 처음에 combination으로 만들수있는 인덱스(3개) 조합을 구하고 그 인덱스에 해당하는 합계를 구하니 시간초과가 났다 ㅜ,ㅜ 시간초과 해결 방법이 생각안나서 구글링으로 결국 해결,,, 전형적인 dp 알고리즘을 사용해서 풀어야하는 문제였다. 왼쪽-> 오른쪽 방향으로 배열의 누적 합을 미리 저장했었는데 왼쪽 2021. 5. 17.
[Codility] Lesson5. PassingCars (Python) 1.문제 app.codility.com/demo/results/training7U86YM-SXN/ Test results - Codility A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count app.codility.com 2.풀이 prefix sum을 응용해서 뒤에서부터 합계를 sum 리스트에 저장했다... 2021. 5. 11.
728x90

티스토리툴바