[Programmers] LV2. 숫자의 표현
2023. 12. 21. 02:02
Algorithm/문제 풀이
문제 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현하는 방법이 여러 개라는 사실을 알게 되었습니다. 예를 들어 15는 다음과 같이 4가지로 표현할 수 있습니다. - 1 + 2 + 3 + 4 + 5 = 15 - 4 + 5 + 6 = 15 - 7 + 8 = 15 - 15 = 15 제한사항 - n은 10,000 이하의 자연수 입니다. 풀이 연속된 수들을 탐색하면서 n과 같으면 되는 간단한 문제이다. 가장 직관적인 방법은 for문을 2개 돌면서 n보다 커지면 break, 같으면 Return 해주는 방법이다! 근데 나는 조금 더 시간을 줄이는 방법이 없을까 생각하다가 Stack을 사용해서 풀어보았다. 정말 좋은 코드인지는 모르겠으나 직접 돌려보면 조금(..
[Programmers] LV3. 가장 긴 팰리드롬
2023. 12. 20. 00:22
Algorithm/문제 풀이
문제 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를 들면, 문자열 s가 "abcdcba"이면 7을 return 하고 "abacde"이면 3을 return 합니다. 제한사항 - 문자열 s의 길이 : 2,500 이하의 자연수 - 문자열 s는 알파벳 소문자로만 구성 풀이 학교 역량 테스트에서 나왔는데 for문으로 해결해서 다른 방법을 찾고자... 다양한 해설들을 참고했는데 투 포인터를 이용하는 방법이 가장 흔한 방법인 것 같다. 예를 들어서, abba라는 문자열이 있다고 가정하자. 그러면 맨 처음 문자열부터 검사를 하므로 0번 인..
[Programmers] LV2. 뒤에 있는 큰 수 찾기
2023. 12. 19. 03:28
Algorithm/문제 풀이
문제 정수로 이루어진 배열 numbers가 있습니다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰 수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰 수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해 주세요. 단, 뒷 큰 수가 존재하지 않는 원소는 -1을 담습니다. 제한사항 4 ≤ numbers의 길이 ≤ 1,000,000 1 ≤ numbers[i] ≤ 1,000,000 풀이 가장 쉽게 생각할 수 있는 방법은 반복문을 돌면서 현재 수 뒤에 있는 숫자들을 모두 돌면서 자기 자신보다 큰 수가 나오면 멈추는 것이다. 근데 이렇게 되면, 예를 들어서 [1,1,1,1,1,1,1,........

[Backjoon 11660] 구간 합 구하기5
2022. 10. 31. 16:15
Algorithm/문제 풀이
문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 풀이 앞에서 풀었던 구간 합 구하기 4와 같이 prefixsum을 미리 구해서 리스트에 넣고, 나중에 필요한 좌표에서의 누적합을 print 하면 된다! import sys N..