Today's Algorithm(2019-01-08) programmers. 가장 큰 수 이전에 풀어봤던 문제인데요. 그 때 아마 제 힘으로 못 풀고 다른 사람의 코드를 참고했던 것 같습니다. 이전에 정리한 적이 없어서 다시 한번 풀어보았는데요. 아이디어가 기억이나서 다행이지 만약 기억이 나지 않았다면 어렵게 풀었을 것 같아요. 이 문제에서 일반 문자열 정렬로 되지 않는 부분이 다음과 같은 예 입니다. int[] numers = {3, 30, 34, 5, 9}; 문자열 정렬로 하면 9, 5, 34, 30, 3으로 정렬이 되겠지만 사실 가장 큰 수가 나오기 위해선 9, 5, 34, 3, 30 으로 되어야하거든요. 그래서 앞자리가 같은 경우엔 추가적으로 정렬을 해줘야합니다. 그리고 그 부분이 포인트인데요. ..
programmers. 베스트 앨범 문제 자체가 그렇게 복잡하진 않았습니다. 다만 자료구조를 어떻게 만들 것이고, 그리고 그 자료구조를 이용하여 어떻게 여러 정렬기준을 적용할 것인지가 문제의 관건이었던 것 같습니다. 저의 경우 객체를 2개를 만들었는데요. Gerne 와 Song 입니다. 그리고 Genre 안에 Song List가 있습니다. 여러 정렬 기준이 존재함에 따라 해당 상태값을 갖고 그것에 맞게 정렬할 수 있도록 해야했습니다. 정렬 기준은 다음과 같습니다. 가장 많이 재생된 장르순 > 장르내 가장 많이 재생된 노래순 > 재생 고유번호가 낮은 순 package p42579; import java.util.*; class Solution { public int[] solution(String[] ge..
programemrs. 위장 많은 사람들이 풀었던 문제인 만큼 난이도는 높지 않았습니다. 종류별로 의상을 나눠야 한다는 필요성은 문제를 풀면서 느꼈을 것입니다. 그리고 해시를 이용하면 깔끔하게 분류할 수 있겠다는 생각도 했을 것입니다. 그리고 나서 드는 생각은 이것이죠. 의상 종류 중 하나도 고를수도 있고, 두개를 고를수도 있고, 또 여러개를 고를 수 있는데 이 조합을 어떻게 구할 수 있을까? 그렇습니다. 조합을 찾아야 합니다. 조합이라는 단어만 들어도 뭔가 경우의 수를 많이 만들어야할 것만 같습니다. 하지만 다행이게도 여기서의 조합은 쉽게 구할 수 있습니다. 각 의상 종류별로 다음 의상을 하나 더 추가시키면 되거든요. 상의 - 티셔츠, 후드, 선택 안하는 경우 하의 - 청바지, 면바지, 쫄바지, 선택 ..
programmers. 등굣길 지도 문제 그리고 최단거리를 보니 저도 모르게 bfs를 생각하게 되었습니다. 이러한 고정관념이 문제를 다양한 방식으로 생각하는 것을 막았던 것 같습니다. 그렇기 때문에 전형적인 bfs를 푸는 방식으로 큐를 이용하여 풀었습니다. 하지만 bfs는 최단거리를 찾는 것에 최적화된 것이지 '최단거리를 갈 수 있는 개수'에 대해서는 최적화되진 않았기 때문에 bfs코드에서 추가적인 조건이 붙었습니다. 그래서 목적지의 위와 옆에 왔을 때는 visit표시를 하지않고(만약 해버리면 다른 경우의 수가 무시되기 때문입니다) 그 개수를 세아렸습니다. 하지만 역시 어설픈 저의 조건인지 몇 개의 경우 오류가 났고 결정적으로 런타임 오류가 발생하였습니다. class Solution { p..
programmers. 정수 삼각형 동적 계획법의 대표적인 문제였던 것 같습니다. 처음에 재귀적으로만 접근했다가 '시간 초과'를 경험하고 다른 코드들을 참고하다가 Memorization을 사용할 수 있다는 것을 다시 깨닫게 되었습니다. Memorization은 이전의 값을 기록해둠으로써 이후에 불필요한 계산을 줄일 수 있게 해줍니다. 그렇기 때문에 앞의 결과에 따라서 뒤에서 처리해주는 것이 동적으로 달라지죠. 그럼 앞서 재귀로 풀면서 시간초과했던 코드부터 보겠습니다. class Solution { private int maxSum; public int solution(int[][] triangle) { search(triangle, 0, 0, 0); return maxSum; } publi..
programmers. 타일 장식물 문제 자체는 어렵지 않았습니다. 원소가 4개 이상이면 answer은 제일 마지막에서 앞으로 순서대로 3배, 2배, 2배, 1배 한 값들을 더해주면 구할 수 있거든요. 다만 효율성 테스트에서 실패가 발생했었는데요. 그래서 코드를 조금씩 수정해봤는데 결국은 해결방법은 형변환이었습니다 위 과정을 다 정수(Integer)타입으로 계산을 했었는데 실제 반환값이 long이었거든요. 형변환 과정에서 좀 더 시간이 걸렸던 것 같아요. 실제로 답을 제출할 때 2ms에서 실패가 떴었는데 계산과정 내에서 long타입으로 하면 1ms로 시간이 줄어들 수 있었거든요. 반환값 타입이 제가 계산한 것과 다를 때는 형변환이 필요한지 유무도 고려해야할 것 같네요. class Solution { pu..
