(Java) 프로그래머스 - 롤케이크 자르기

2023. 5. 5. 23:59·코딩 테스트

문제가 간단하지만 시간 제한을 맞추는게 꽤 까다로웠다.

인풋값이 크기 떄문에 O(n^2) 로직은 무조건 시간 초과가 나고, O(n log n) 이내로 작성해야 된다고 생각해서

최종적으로 O(n) 로직으로 풀이에 성공했다.


 

실패 코드

import java.util.*;
import java.util.stream.Collectors;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        for(int i = 1; i < topping.length; i++) {
            Set<Integer> set1 = Arrays.stream(Arrays.copyOfRange(topping, 0, i))
            .boxed()
            .collect(Collectors.toSet());
            
            Set<Integer> set2 = Arrays.stream(Arrays.copyOfRange(topping, i, topping.length))
            .boxed()
            .collect(Collectors.toSet());
            
            if(set1.size() == set2.size()) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < topping.length; i++) {
            map.put(topping[i], map.getOrDefault(topping[i], 0) + 1);
        }
        
        for(int i = 0; i < topping.length; i++) {
            set.add(topping[i]);
            map.put(topping[i], map.getOrDefault(topping[i], 0) - 1);
            if(map.get(topping[i]) == 0) {
                map.remove(topping[i]);
            }
            
            if(set.size() == map.size()) {
                answer++;
            }
        }
        return answer;
    }
}

 

 

저작자표시 (새창열림)

'코딩 테스트' 카테고리의 다른 글

(Java) 프로그래머스 - 이모티콘 할인행사  (0) 2023.05.06
(Java) 프로그래머스 - 택배상자  (0) 2023.05.06
(Java) 프로그래머스 - 숫자 변환하기  (0) 2023.05.05
(Java) 프로그래머스 - 뒤에 있는 큰 수 찾기  (0) 2023.05.04
(Java) 프로그래머스 - 연속 부분 수열 합의 개수  (0) 2023.04.28
'코딩 테스트' 카테고리의 다른 글
  • (Java) 프로그래머스 - 이모티콘 할인행사
  • (Java) 프로그래머스 - 택배상자
  • (Java) 프로그래머스 - 숫자 변환하기
  • (Java) 프로그래머스 - 뒤에 있는 큰 수 찾기
로승리
로승리
  • 로승리
    Roy's Blog
    로승리
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Issuefy
      • Language
      • Spring
      • Database
      • Network
      • Kubernetes
      • AWS
      • 코드스쿼드
      • 코딩 테스트
      • 생각정리
      • 국비지원
      • 회고
      • 컨퍼런스, 세미나
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
로승리
(Java) 프로그래머스 - 롤케이크 자르기
상단으로

티스토리툴바