해시5 [Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2) 요구능력 해시와 이분탐색 문제풀이 일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다. 2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다. 그렇다면 어떻게 풀어야할까? 나는 여기서 중간에서 만나기라는 개념을 처음 접했는데, 대충 이런개념인것같다. 반을 쪼개서 해시로 dictionary에 값들을 저장해주고, 나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다. 그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다. 후기.. 2022. 5. 10. [Swift][프로그래머스][해시] 메뉴 리뉴얼 요구능력 조합 + 해시 문제풀이 DFS를 활용해서 조합을 사용하였고, 문제에서도 조합이라고 했기 때문에 음식의 순서는 상관없다. 그래서 sorTemp변수를 사용해서 얻어오는 조합마다 정렬해서 받았다. 이 부분이 이 문제의 변별력인것 같다. ex) XY, YX는 같은 음식조합이다. 그리고 사실 "만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다." 이 부분을 안읽고 문제를 풀다가 가 예제 2번에 AB는 왜 안되지라는 생각을 계속했는데, 2가지 메뉴구성 중에서도 가장 많이 함께 주문된 메뉴구성을 골라야했다. 가장 많이 함께 주문된 메뉴구성을 안고르고 그냥 course의 개수에 맞고 2개이상인 메뉴구성을 계속 고르다보니 문제가 안풀렸던것이다. 후기 문제의 조건을.. 2022. 4. 27. [Swift][프로그래머스][해시] 오픈채팅방 요구능력 해시(딕셔너리) 문제풀이 문제를 읽어보면 중간에 닉네임을 바꾸게 되면 맨 마지막 결과값에서 해당 uid에 대한 닉네임을 바꿔서 출력해줘야한다. 그래서 우선 생각한것이 uid마다 딕셔너리의 키값으로 nickName을 넣어주었다. 그리고 백준에서 주구장창하던 입력받는게 여기서 도움이 됐다. record를 각각 명령어(Enter, Leave, Change)가 저장되는 command와 아이디가 저장되는 id, 그리고 나가는 경우에는 따로 닉네임이 적혀있지 않으므로 띄어쓰기마다 구분해서 입력받은 str이 3개이상이면 닉네임까지 받는경우라서 str의 count가 3이상이면 dict에 id에 따른 nickName을 저장해주었다. 그리고 swtich문을 활용해서 Enter인 경우와 Leave인 경우를 처리해줬.. 2022. 4. 22. [Swift][프로그래머스][해시] 베스트앨범 요구능력 딕셔너리의 활용 및 정렬 문제풀이 아래는 문제의 조건이다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 1번을 처리하기 위해서 dict를 생성하고 ["classic": 1450]과 같이 저장하였다. 그리고 정렬해서 rankDict에 ["classic": 1]과 같이 저장하였다. 다음으로 2번을 처리하기 위해서 uniqueDict를 생성하고 [0 : ("classic", 500)]과 같이 저장하였다. 그리고 rankDict를 활용해서 장르별로 정렬을 해주었다. 이렇게 장르별로 정렬된 것은 sortedUniqueDict에 저장해주었고, sor.. 2022. 4. 19. 이전 1 2 다음