programmers.co.kr/learn/courses/30/lessons/42584

 

코딩테스트 연습 - 주식가격

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00

programmers.co.kr

초단위로 주식의 가격을 담은 int[] prices가 주어진다. (인덱스 한 칸 당 1초)

각 초를 시점으로 하여 주식 가격이 몇 초 동안 떨어지지 않는지 기록한 배열을 반환해야한다.

 

주의할 점은 1초 뒤에(바로 다음 인덱스에서) 가격이 떨어지는 경우는 1초 동안 떨어지지 않은 것으로 본다.

마지막 인덱스는 그 뒤의 가격이 존재하지 않기 때문에 0초로 한다.

 

 

풀이 .

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length; i++) {
            int time = 0;
            for(int j = i + 1; j < prices.length; j++) {
                // 다음 초에 가격이 떨어지더라도 그 초까지는 카운트를 해야한다
                time++;
                // 가격이 떨어지면 카운트 중지
                if(prices[i] > prices[j]) {
                    break;
                }
            }
            answer[i] = time;
        }
        return answer;
    }
}

 

주석으로 표시한 사항만 조심하면 되는 문제

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 다리를 지나는 트럭 JAVA  (0) 2020.12.28
[PG] 기능 개발 JAVA  (0) 2020.12.28
[PG] 베스트 앨범 JAVA  (0) 2020.12.28
[PG] 위장 JAVA  (0) 2020.12.27
[PG] 전화번호 목록 JAVA  (0) 2020.12.27

programmers.co.kr/learn/courses/30/lessons/42579

 

코딩테스트 연습 - 베스트앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가

programmers.co.kr

각 노래들의 장르와 플레이 수를 담은 String[] genres, int[] plays가 주어진다.

배열의 인덱스를 각 노래의 고유번호로 한다.

 

이 중 몇 가지 노래를 뽑아 베스트 앨범을 만들고자 한다.

 

베스트 앨범 조건

1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)

2. 장르 별 총 재생 수가 많은 장르부터 뽑는다. 

3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.

4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

 

 

풀이 .

import java.util.*;

//1. 장르 별로 두 개의 곡을 선정한다. (장르에 속한 곡이 하나 뿐이라면 하나만 선정)
//2. 장르 별 총 재생 수가 많은 장르부터 뽑는다.
//3. 같은 장르 내에서 순서는 재생 수의 내림차순이다.
//4. 재생 수가 같을 경우 고유 번호(인덱스)의 오름차순으로 한다.

class Song implements Comparable<Song> {
    int index;
    int play;

    public Song() {}
    public Song(int index, int play) {
        this.index = index;
        this.play = play;
    }

    @Override
    public int compareTo(Song o) {
        if (this.play != o.play) {
            if (this.play > o.play) { return -1; }
            else { return 1; }
        } else {
            if (this.index < o.index) { return -1; }
            else { return 1; }
        }
    }
}

class Solution {
    public ArrayList<Integer> solution(String[] genres, int[] plays) {
        // 장르 별 총 재생 수 세기
        Map<String, Integer> jenreHm = new HashMap<String, Integer>();
        for(int i = 0; i < genres.length; i++) {
            String jenre = genres[i];
            if(jenreHm.get(jenre) == null) {
                jenreHm.put(jenre, plays[i]);
            }else {
                jenreHm.put(jenre, jenreHm.get(jenre) + plays[i]);
            }
        }

        // 총 재생 수의 내림차순으로 정렬
        // List에 옮겨 정렬한 후 LinkedHashMap으로 넘겨 순서 유지
        List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>();
        for(Map.Entry<String, Integer> entry : jenreHm.entrySet()) {
            list.add(entry);
        }
        Collections.sort(list, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        Map<String, Integer> sortedJenreHm = new LinkedHashMap<String, Integer>();
        for(Map.Entry<String, Integer> entry : list) {
            sortedJenreHm.put(entry.getKey(), entry.getValue());
        }

        // Map<String, ArrayList<Song>>으로 멀티 맵 구현
        Map<String, ArrayList<Song>> multiHm = new LinkedHashMap<String, ArrayList<Song>>();
        for(String jenre : sortedJenreHm.keySet()) {
            multiHm.put(jenre, new ArrayList<Song>());
        }

        // 장르 별 노래 저장. 이때 장르 별 총 재생 수 내림차순 정렬은 완료되어있음
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            multiHm.get(genre).add(new Song(i, plays[i]));
        }

        // 장르 별 최다 재생 곡 2개 뽑아서 저장
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(ArrayList<Song> aList : multiHm.values()) {
            Collections.sort(aList);
            // 장르에 곡이 하나 뿐이면 하나만 저장
            ansList.add(aList.get(0).index);
            if(aList.size() >= 2) {
                ansList.add(aList.get(1).index);
            }
        }
        return ansList;
    }
}

 

1. 최다 재생 수가 많은 장르부터 수록해야 하므로 hm을 통해 장르 별 총 새생 수 먼저 파악

2. LinkedList를 사용해 총 재생 수로 내림차순 정렬 후 LinkedHashMap으로 옮겨 그 순서를 유지 (그냥 HashMap은 입력 순서 유지되지 않아 정렬이 해쳐짐)

3. 장르 안의 노래들 사이에서도 정렬이 필요. Song 클래스를 만들어 정렬 기준 명시 (play 내림차순, index 오름차순)

4. Map<String, ArrayList<Song>>으로 멀티 맵 구현. 장르 별로 자신의 노래를 저장할 리스트를 갖는다.

5. 각 장르에 해당하는 Song을 모두 담고 이를 내림차순 정렬하여 인덱스 0, 1의 원소(상위 2곡)를 정답 리스트에 저장

 

 

 

너무 주먹구구식의 풀이가 아닌가 싶다. 이정도 방법도 생각하는데 꽤 오랜 시간이 걸렸다.

 

 

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 기능 개발 JAVA  (0) 2020.12.28
[PG] 주식 가격 JAVA  (0) 2020.12.28
[PG] 위장 JAVA  (0) 2020.12.27
[PG] 전화번호 목록 JAVA  (0) 2020.12.27
[PG] 완주하지 못한 선수 JAVA  (0) 2020.12.27

컴포넌트 스캔 방식 외에 Bean을 등록하는 로직을 자바 코드로 직접 구현하는 방식도 있다.

@Configuration
public class SpringConfig {

    @Bean
    public MemberService memberService() {
        return new MemberService(memberRepository());
    }

    @Bean
    public MemberRepository memberRepository() {
        return new MemoryMemberRepository();
    }
}

@Configuration 어노테이션을 통해 스프링 컨테이너에 등록할 Bean들을 직접 등록할 수 있다.

단, Controller는 반드시 컴포넌트 스캔 방식을 사용해야한다.

 

 

 

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%EC%9E%85%EB%AC%B8-%EC%8A%A4%ED%94%84%EB%A7%81%EB%B6%80%ED%8A%B8/dashboard

일단 실행이 되면 스프링 컨테이너는 @SpringBootApplication이 달린 경로부터 시작으로 모든 하위경로를 검색한다.

 

이떄 @Component 어노테이션을 달고있는 객체들은 모두 자동으로 생성되어 스프링 컨테이너에 보관된다. 이러한 방식을 컴포턴트 스캔이라고 한다.

(기본적으로 싱글톤 방식을 사용해 각 컴포넌트 객체는 하나씩만 존재한다.)

 

@Controller, @Service, @Repository 모두 내부적으로 @Component를 포함하고 있다.

 

 

A 클래스가 B 클래스의 객체를 멤버로 사용할 경우 A가 B에 의존성을 갖고 있다고 표현한다.

이때 A 내부에서 B 객체를 직접 생성하는 방식으로 사용하지 않는다.

@Autowired를 사용해 생성자에서 객체를 전달받는데, 이를 의존성 주입(DI : Dependency Injection) 중에서도 생성자 주입이라고 한다.

주의해야할 점은 의존성이 엮여있는 모든 클래스를 전부 다 처리해줘야 제대로 동작한다는 것이다.

@Controller
public class MemberController {

    private final MemberService memberService;

    @Autowired
    public MemberController(MemberService memberService) {
        this.memberService = memberService;
    }
}

 

 

 

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%EC%9E%85%EB%AC%B8-%EC%8A%A4%ED%94%84%EB%A7%81%EB%B6%80%ED%8A%B8/dashboard

Service는 Repository(= DAO)를 통해 기능을 수행한다.

Repository객체를 직접 생성하지 않고 생성자를 통해 받아 사용하는 것이 좋다. (= 생산성 주입)

따로 사용할 경우 ServiceTest에서 사용하는 Repository와 다른 Repository를 사용하게 되어 테스트에 문제가 생길 수 있다.

private final MemberRepository memberRepository;

// Dependency Injection
public MemberService(MemberRepository memberRepository) {
    this.memberRepository = memberRepository;
}

 

함수 추출 (Ctrl + Alt + M)

지정한 로직을 함수로 추출해낸다. 해당 로직은 추출된 함수의 호출로 대체된다.

ex, 사용 전

    // 회원 가입
    public Long join(Member member) {
        // 같은 이름이 있는 중복 회원 X
        memberRepository.findByName(member.getName())
                // ifPresent() : Optional의 기능. 담긴 객체가 null이 아닐 경우 호출된다.
                .ifPresent(m -> {  
                    throw new IllegalStateException("이미 존재하는 회원입니다.");
                });

        memberRepository.save(member);
        return member.getId();
    }

 

ex, 사용 후

	// 회원 가입
    public Long join(Member member) {
        // 같은 이름이 있는 중복 회원 X
        validateDuplicateMember(member);

        memberRepository.save(member);
        return member.getId();
    }

    // 중복 회원 검증
    private void validateDuplicateMember(Member member) {
        memberRepository.findByName(member.getName())
        		// ifPresent() : Optional의 기능. 담긴 객체가 null이 아닐 경우 호출된다.
                .ifPresent(m -> {
                    throw new IllegalStateException("이미 존재하는 회원입니다.");
                });
    }

 

 

 

assertThat().isEqualTo()를 사용하기 위한 Assertions는 

import static org.junit.jupiter.api.Assertions.*; 이 아니라 

import static org.assertj.core.api.Assertions.*; 이다.

 

 

JUnit 테스트를 위한 @BeforeEach, @AfterEach

    @BeforeEach
    public void beforeEach() {
        memberRepository = new MemoryMemberRepository();
        memberService = new MemberService(memberRepository);  // 생성자 주입
    }

    @AfterEach
    public void afterEach() {
        memberRepository.clearStore();
    }

 

 

Test 클래스는 일일히 따로 만들지 않아도 된다.

Test하려는 클래스에 커서를 두고 Ctrl + Shift + T 를 통해 자동으로 생성할 수 있다. (패키지까지 자동 생성된다.)

 

Test 함수의 로직은 given, when, then 순으로 작성하는 것이 좋다. Test 함수명은 한글로 써도 무방하다.

    @Test
    void 회원가입() {
        // given : 주어진 것들로
        Member member = new Member();
        member.setName("hello");

        // when : 이걸 실행했을때
        Long saveId = memberService.join(member);
        
        // then : 이런 결과가 나와야 됨
        Member findMember = memberService.findOne(saveId).get();
        assertThat(member.getName()).isEqualTo(findMember.getName());
    }

 

 

에러 처리를 위해 try catch 대신 다른 방법을 쓸 수 있다.

// when
memberService.join(member1);

// 방법 1
try {
    memberService.join(member2);
    fail();
} catch(IllegalStateException e) {
    assertThat(e.getMessage()).isEqualTo("이미 존재하는 회원입니다.");
}

// 방법 2
// 오른쪽 파라미터의 로직을 실행했을때 왼쪽 파라미터의 에러를 반환
IllegalStateException e = assertThrows(IllegalStateException.class, () -> memberService.join(member2));
assertThat(e.getMessage()).isEqualTo("이미 존재하는 회원입니다.");

 

 

 

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%EC%9E%85%EB%AC%B8-%EC%8A%A4%ED%94%84%EB%A7%81%EB%B6%80%ED%8A%B8/dashboard

라인 삭제 : Ctrl + Y

 

라인 복붙 : Ctrl + D

 

import, static import : Alt + Enter

 

getter, setter 자동 생성 : Alt + Insert

 

Rename : Shift + F6

 

출력문 생성 : sout -> tab

 

함수 설명 : Ctrl + Q 

 

자동정렬 : Ctrl + Alt + L

 

변수 추출 : Ctrl + Alt + V (반환값이 있는 함수를 변수로 안 받고 호출만 했을 때 이걸 사용하면 반환값을 받는 변수 자동 생성됨)

 

함수 추출 : Ctrl + Alt + M (지정된 로직을 하나의 함수로 추출해줌. 기존에 존재하던 로직은 이 함수를 호출하는 것으로 대체됨)

 

JUnit Test 자동 생성 : Ctrl + Shift + T (테스트 생성할 클래스에 커서 두고서 눌러야 함. test 부분에 패키지까지 똑같이 만들어진다. 당연히 테스트 로직은 직접 작성해야함)

 

다시실행 : Shift + F10 (바로 전에 실행한 것 다시 실행)

 

인라인 : Ctrl + Alt + N (같은 걸 사용하는 두 로직을 한 로직으로 줄여줌)

@Override
public List<Member> findAll() {
	List<Member> result = em.createQuery("select m from Member m", Member.class)
			.getResultList();
	return result;
}

에서 result에 Ctrl + Alt + N 하면

@Override
public List<Member> findAll() {
	return em.createQuery("select m from Member m", Member.class)
			.getResultList();
}

으로

 

psvm (public static void main) 

 

오류 찾기(오류 발생 라인으로 바로 이동) : F2

 

히스토리 : Ctrl + E (클래스를 디렉토리를 타고 갈 필요 없이 히스토리 검색으로 편하게 갈 수 있다.)

Ctrl + E + Enter 하면 빠르게 이전 클래스로 돌아갈 수 있음

 

다음줄로 자동 엔터 : Ctrl + Shift + Enter

); 같은 짜잘한 놈 자동으로 입력하고 바로 다음줄로 넘어갈 수 있다.

 

구현체 바로가기 : Ctrl + Alt + B 

해당 인터페이스를 구현하는 구현체들로 바로 이동할 수 있다.

 

클래스 검색 : Ctrl + N

존재하는 클래스, 인터페이스, 어노테이션 등을 빠르게 검색할 수 있다.

'기타' 카테고리의 다른 글

GIT CLI  (0) 2021.01.09
POSIX CLI  (0) 2021.01.09
Scanner, BufferedReader 입력  (0) 2021.01.08

programmers.co.kr/learn/courses/30/lessons/42578

 

코딩테스트 연습 - 위장

 

programmers.co.kr

이차원 배열 String[][] clothes가 주어진다.

clothes : { {옷이름, 옷종류}, {옷이름, 옷종류}, ... {옷이름, 옷종류} }

 

주어진 옷들로 만들 수 있는 조합의 수를 반환하는 문제.

단, 각각의 옷은 입을 수도 안 입을 수도 있으나 아무것도 안 입는 경우는 없다.

 

 

풀이 .

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(String[][] clothes) {
        // clothes : [{옷이름, 옷종료}, {옷이름, 옷종류}, ... , {옷이름, 옷종류} ]
        int answer = 1;

        Map<String, Integer> hm = new HashMap<String, Integer>();
        for(String[] cloth : clothes) {
            String key = cloth[1];  // 옷 종류를 key로 사용

            if(hm.get(key) == null) {
                hm.put(key, 2);  // 안 입는 경우도 고려하여 2부터 시작
            }else {
                hm.put(key, hm.get(key) + 1);
            }
        }

        for(Integer num : hm.values()) {
            answer *= num;
        }
        answer--;  // 아무것도 안 입는 경우는 없음
        return answer;
    }
}

 

옷의 이름은 중요하지 않다.

옷의 종류를 key로 잡고 HashMap을 사용해 종류별로 몇 개의 옷이 있는지 센 다음 그걸 모두 곱하면 된다.

옷을 입지 않는 경우, 아무것도 입지 않는 경우에 대한 고려를 해줘야한다.

O(n)으로 처리 가능

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 기능 개발 JAVA  (0) 2020.12.28
[PG] 주식 가격 JAVA  (0) 2020.12.28
[PG] 베스트 앨범 JAVA  (0) 2020.12.28
[PG] 전화번호 목록 JAVA  (0) 2020.12.27
[PG] 완주하지 못한 선수 JAVA  (0) 2020.12.27

programmers.co.kr/learn/courses/30/lessons/42577

 

코딩테스트 연습 - 전화번호 목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조

programmers.co.kr

전화번호 목록이 담긴 String[] phone_book이 주어진다.

등록된 번호들 중 다른 번호의 접두어로서 존재하는 번호가 있는지 찾는 문제.
(접두어가 존재하면 false, 존재하지 않으면 true를 반환. 반대여야 하는 거 아닌가..?)

 

 

풀이 1.

import java.util.Arrays;
import java.util.Comparator;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean solution(String[] phone_book) {
        // String의 길이순으로 정렬
        Arrays.sort(phone_book, Comparator.comparing(String::length));

        // O(n^2) 시간 소요..
        for(int i = 0; i < phone_book.length - 1; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                // charAt()으로 하나씩 검사하지 않고 substring으로 한 번에 처리
                int len = phone_book[i].length();
                String sub = phone_book[j].substring(0, len);
                if (phone_book[i].equals(sub)) {  // 접두어 존재
                    return false;  // 존재'할' 경우에 false 반환임. 헷갈림 주의
                }
            }
        }
        return true;
    }
}

String[] phone_boo의 최대길이는 1,000,000 (10^6)이기 때문에 O(n^2)의 방식으로는 시간초과가 나야한다.

근데 안 나길래 그냥 O(n^2)로 풀었다. (테스트케이스가 좀 허술한 듯) 더 효율적인 방법을 모르겠다.

 

그냥 Arrays.sort()를 사용할 경우 String의 길이 순으로 정렬할 수 없었다.

구글링을 통해 Arrays.sort()의 두번째 파라미터를 찾아 길이순으로 정렬할 수 있었다.

 

처음엔 charAt()를 통해 phone_book[i].length()만큼 반복하며 [i]와 [j]의 char를 하나씩 비교하려고 했었다.

 

그 후 substring()을 통해 시간복잡도를 줄일 수 있었다. (그래봤자 O(n^2)이지만..)

 

 

 

풀이 2.

class Solution {
    public boolean solution(String[] phoneBook) {
       for(int i=0; i<phoneBook.length-1; i++) {
            for(int j=i+1; j<phoneBook.length; j++) {
                if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
                if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
            }
        }
        return true;
    }
}

프로그래머스의 '다른 사람의 풀이'를 통해 startWith()에 대해 알게 되었다.

시간복잡도는 동일하지만 길이순으로 정렬할 필요도 없고 코드도 더 직관적이다.

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 기능 개발 JAVA  (0) 2020.12.28
[PG] 주식 가격 JAVA  (0) 2020.12.28
[PG] 베스트 앨범 JAVA  (0) 2020.12.28
[PG] 위장 JAVA  (0) 2020.12.27
[PG] 완주하지 못한 선수 JAVA  (0) 2020.12.27

+ Recent posts