20일차)알고리즘 문제(카펫, 행렬과 연산, 올바른 괄호의 갯수, 무지의 먹방 라이브), 복습(추상 클래스와 인터페이스)

>알고리즘 문제

1. 카펫

1)문제

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

2) 솔루션

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var answer = intArrayOf()
        answer+=(brown/2 +2 +Math.sqrt(((brown/2+2)*(brown/2+2)-4*(yellow+brown)).toDouble()).toInt())/2 
        answer+=(brown/2 +2 -Math.sqrt(((brown/2+2)*(brown/2+2)-4*(yellow+brown)).toDouble()).toInt())/2 
        return answer
    }
}

-가로를 x, 세로를 y로 두었을때 xy=brown+yellow, (x-2)(y-2)=yellow를 이용하여 2x+2y-4=brown식을 도출 후

-xy= brown+yellow와 x+y=brown/2+2를 이용하여 방정식 t^2+(b/2 + 2)t+ b+y=0을 만들음

-근의 공식이용하여 답을 구함

 

 

2. 행렬과 연산

1)문제

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.

• ShiftRow
  • 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.)
  • ShiftRow의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다.
    • 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다.

• Rotate
  • 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다.
  • 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다.
  • 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀려난다는 것을 의미합니다. 즉, 다음 4개의 연산이 동시에 시행됩니다.
    • 첫 행에서 끝 열에 있는 원소를 제외한 첫 행의 모든 원소는 오른쪽으로 한 칸 이동합니다.
    • 끝 열에서 끝 행에 있는 원소를 제외한 끝 열의 모든 원소는 아래쪽으로 한 칸 이동합니다.
    • 끝 행에서 첫 열에 있는 원소를 제외한 끝 행의 모든 원소는 왼쪽으로 한 칸 이동합니다.
    • 첫 열에서 첫 행에 있는 원소를 제외한 첫 열의 모든 원소는 위쪽으로 한 칸 이동합니다.
  • Rotate의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 Rotate를 한 번 시행한 뒤의 행렬입니다.
    • 바깥쪽에 있는 값들이 시계 방향으로 한 칸씩 이동한 것을 확인할 수 있습니다.

당신은 행렬에 연산을 여러 번 시행하려고 합니다.
행렬의 초기 상태를 담고 있는 2차원 정수 배열 rc, 시행할 연산을 순서대로 담고 있는 문자열 배열 operations가 매개변수로 주어졌을 때, 연산을 차례대로 시행한 후의 행렬 상태를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
• rc[i][j] 는 i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
  • 1 ≤ rc[i][j] ≤ 1,000,000
• 1 ≤ operations의 길이 ≤ 100,000
  • operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.

정확성 테스트 케이스 제한 사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 1,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 1,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 10,000
• 1 ≤ operations의 길이 ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

2)솔루션

class Solution {
    fun solution(rc: Array<IntArray>, operations: Array<String>): ArrayDeque<ArrayDeque<Int>> {
        
        var left=ArrayDeque<Int>()
        var right=ArrayDeque<Int>()
        var middle=ArrayDeque<ArrayDeque<Int>>()
        
        
        val wEnd=rc[0].size-1
        for(i in rc.indices){
            left.addLast(rc[i][0])
            right.addLast(rc[i][wEnd])
            var tmpDeque=ArrayDeque<Int>()
            for(j in 1..wEnd-1){
                tmpDeque.addLast(rc[i][j])
            }
            middle.addLast(tmpDeque)
        }
        
        for(i in operations){
            if(i=="Rotate"){
                middle[0].addFirst(left.removeFirst())
                right.addFirst(middle[0].removeLast())
                middle[middle.size-1].addLast(right.removeLast())
                left.addLast(middle[middle.size-1].removeFirst())
            }else{
                middle.addFirst(middle.removeLast())
                left.addFirst(left.removeLast())
                right.addFirst(right.removeLast())
            }
        }
        
        
        for(i in middle.indices){
            middle[i].addFirst(left.removeFirst())
            middle[i].addLast(right.removeFirst())
        }
        return middle
        
    }
}

-그냥 array로 하면 index들을 옮기는 과정에서 시간복잡도가 O(n)이 되어 시간초과가 나기때문에 deque으로 문제 풀이

-rotate를 고려하여 좌측열, 중앙, 우측열로 나누어 풀이

 

3)느낀점: 처음엔 적절한 자료구조를 몰라 헤매다 힌트를 보고 deque을 사용하게 되었다. 아이디어가 중요한 문제 같다. 

 

3. 올바른 괄호의 갯수

1)문제

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

제한사항

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

2)솔루션

class Solution {
    fun solution(n: Int): Int {
        return check(n,0,0)
    }
    
    fun check(n:Int, left:Int, right:Int):Int{
        val result=0
        if(left<right) return 0
        if(left>n||right>n) return 0
        if(left==right&&left==n){
            return 1
        }
        return result+check(n,left+1,right)+check(n,left,right+1)
    }
}

-괄호의 경우 여는 괄호가 닫는 괄호 갯수 이상이어야 하는 부분만 조건에 넣으면 됨

-재귀함수를 이용하여 해결

 

3)느낀점: 레벨 4치고는 많이 쉬웠던것같다.

 

 

4. 무지의 먹방 라이브

1)문제

문제 설명

무지의 먹방 라이브

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

제한사항

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
• k 는 방송이 중단된 시간을 나타낸다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

• food_times 의 길이는 1 이상 2,000 이하이다.
• food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
• k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

• food_times 의 길이는 1 이상 200,000 이하이다.
• food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k는 1 이상 2 x 10^13 이하의 자연수이다.

2)솔루션 

class Solution {
    fun solution(food_times: IntArray, k: Long): Int {
        var answer = 0
        var sec=0L
        
        var maps=hashMapOf<Int,ArrayList<Int>>() //키는 음식수, 값은 해당 음식수를 갖는 인덱스들
        var foodIdx=0
        var sizes=food_times.size.toLong()
        
        var weight=0L
        
        
        var max=0
        for(i in food_times){
            if(i>max){
                max=i
            }
            maps.put(i,ArrayList<Int>())
        }
        
        for(i in food_times.indices){
            maps[food_times[i]]!!+=i
        }
        
        var tmpfood=maps.keys.sorted()
        
        var min=-1
        while(true){
            
            if(min==max){
                answer=-1
                break
            }
            
            min=tmpfood[foodIdx++]
            var cnt=maps[min]!!.size
            
            
            
            if(sec+sizes*(min.toLong()-weight)<=k){
                sec+=sizes*(min.toLong()-weight)
            }else{
                var move=(k-sec)%sizes
                for((key, value) in maps){
                    if(value.isEmpty()) continue
                    if(key<min){
                        for(i in value){
                            food_times[i]=0
                        }
                    }  
                }
                for(i in food_times.indices){
                    if(food_times[i]==0){
                        continue
                    }
                    if(move==0L){
                        answer=i+1
                        break
                    }
                    --move
                }
                break
            }
            
            sizes-=cnt
            weight=min.toLong()
            
            
        }
        
        
        return answer
    }
}

-k번을 그냥 돌면 시간초과가 날 것이기에 음식수가 가작 적은것부터 루프마다 음식수만큼을 한번에 도는 방식을 택함.

-접근에서 시간복잡도를 줄이기 위해 Map을 이용해 키는 음식수, 값은 해당 음식이 위치한 인덱스들의 리스트로 만들음

-매 루프마다 시간을 계산해 다음 루프에 시간이 k를 넘어간다면 이번루프는 순회하여 최종 위치를 찾음

-현 sec값까지 움직인 위치는 배열의 첫번째니깐, 나머지 k-sec만큼 추가로 움직인 위치는 k-sec를 남은 음식들의 배열 사이즈인 sizes로 나눈 나머지와 같다. 

@주의할점:

-자료형부분에서 실수와 정수 연산할때 toLong()을 일일히 제대로 붙여주지 않으면 실패가 뜨기도 함

-maps에서 key목록을 그냥 음식수의 max값을 이용해 1부터 max까지 생성해 버리면 시간초과가 남

=>그냥 maps을 food_times를 순회하며 생성한 후에 key를 추출해 정렬하는게 빠름

 

3)느낀점: map이란 적절한 자료구조를 찾는것은 금방 알 수 있었지만 자료형 문제로 실패가 뜬것때문에 조금 헤매서 까다로운 느낌이었다.

 

 

>복습

1. 추상 클래스 

1)abstract:

-클래스앞에 붙으며 프로퍼티나 메소드도 추상화 시킬 수 있다

-프로퍼티나 메소드에 붙는 경우: 프로퍼티에 붙으면 초기화를 안하고 자료형까지만 쓰며 메소드에 붙으면 본문에 해당하는 {}부분을 작성하지않는다

=>단, 추상 클래스에서도 abstract가 안붙은 프로퍼티나 메소드를 작성할 수 있다.

 

2)open이 필요없음: abstract키워드가 붙은 부분(클래스, 메소드, 프로퍼티)에서는 open키워드를 붙이지 않아도 오버라이드 가능하다.

=>단, 상속받을때 abstract부분은 반드시 오버라이드 해줘야함.

-예시

abstract class Shape {
    // 추상 프로퍼티: 하위 클래스에서 반드시 구현되어야 함
    abstract val area: Double
}

class Circle(val radius: Double) : Shape() {
    override val area: Double
        get() = Math.PI * radius * radius
}

 

3)상속받는 하위클래스 없이 추상클래스 사용법:object

-예시

abstract class A {
	abstract fun a()
}

val t = object : A() {
	override fun a() {
		println("a 재정의")
	}
}

fun main() {
	 A.a()
}

 

 

2. 인터페이스

1)종류

<1>메소드

-추상 메소드: 구현부가 없는 메소드 ({}부분)

-일반 메소드: 구현부가 있는 메소드

 

<2>프로퍼티

-추상 프로퍼티: 초기화를 시키지 않고 자료형까지만 쓴 프로퍼티

-get(): val로 선언한 프로퍼티는 get()으로 값을 저장할 수 있다.

=>예시

interface A{
	val a:String
    	get()="게터로 값 대입"
}

 

2)다중 상속

-여러개의 인터페이스를 상속할 수 있다.

-합집합과 같은 개념으로 사용

-예시

interface A {
    fun a()
}

interface B {
    fun b()
}

class MyClass : A, B {
    override fun a() {
        println("Method a() implementation")
    }

    override fun b() {
        println("Method b() implementation")
    }
}

 

3)인터페이스에서 구현한 메소드 이름이 겹치는 경우: super<인터페이스명>.메소드명을 이용

-예시

interface A {
    fun a()
}

interface B {
    fun a()
}

class MyClass : A, B {
    override fun a() {
        super<B>.a(){
        	println("Method a() implementation")
        }
    }
}

-super의 여부에 따라 동시에 실행 시킬 수도 있음 

=>예시

interface InterfaceA {
    fun commonMethod() {
        println("InterfaceA method")
    }
}

interface InterfaceB {
    fun commonMethod() {
        println("InterfaceB method")
    }
}

class MyClass : InterfaceA, InterfaceB {
    override fun commonMethod() {
        super<InterfaceA>.commonMethod()  // InterfaceA의 메소드 호출
        super<InterfaceB>.commonMethod()  // InterfaceB의 메소드 호출
    }
}

fun main() {
    val obj = MyClass()
    obj.commonMethod()
}

/*결과는
InterfaceA method
InterfaceB method
로 나온다*/

 

4)오버라이드 여부

-추상 메소드나 프로퍼티는 반드시 오버라이드 해줘야함

-일반 메소드는 안 해도 된다.

 

3. 둘의 차이점

1)인터페이스는 프로퍼티 기본값 저장 불가능:내부 초기화 불가

2)추상클래스는 하나만 상속되나 인터페이스는 다중상속 가능