[알고리즘] BOJ 7607: 리스트 계산기

태그 BOJKotlin 분류 알고리즘

BOJ 7607번 문제 리스트 계산기를 Kotlin으로 풀이한 글입니다.

chevron_right

목차

문제

링크

solved.ac Diamond 2

문제 리스트를 계산할 수 있는 인터프리터를 만들어보자. 이 인터프리터는 (우선순위가 높은 것에서 낮은 것 순으로) 괄호, 배열 슬라이싱, 단항 연산자, 이항 연산자, 리스트 이어붙이기, 대입 연산자를 포함하는 여러 표현식을 다룰 수 있어야 한다.

배열 슬라이싱 연산자는 [begin:end] 형식을 따르며, 표현식 뒤에 놓여 해당 리스트의 부분 리스트를 반환한다. 인덱스는 0부터 세고, begin은 포함하지만 end는 포함하지 않는다. 따라서 L[1:3]은 리스트 L의 2번째 원소부터 3번째 원소까지를 의미한다. begin이나 end는 생략할 수 있다. begin이 생략되면 0, end가 생략되면 리스트의 길이인 것으로 보면 된다. 만약 end가 begin보다 작거나 같으면 결과는 빈 리스트이다. begin과 end는 15를 넘지 않는다. 인덱스가 범위를 벗어나는 일 또한 없다.

단항 연산자(+, -, *, /)는 리스트 앞에 놓여 리스트의 첫 두 원소를 삭제하고, 두 원소에 해당 연산자를 이항 연산자로 적용한 다음, 결과를 다시 리스트의 제일 앞에 넣는 작업을 반복한다. 예를 들어 +(1:2:4)는 1과 2를 삭제하고, 둘을 더한 3을 리스트 앞에 넣어서 +(3:4)가 된다. 다시 3과 4를 삭제하고, 둘을 더한 7을 리스트 앞에 넣으면 +(7)이 된다. 이제 리스트가 원소 하나만을 포함하므로 결과값은 7이 된다. 계산 과정에서 단항 연산자가 무한하거나 빈 리스트에 적용되는 일은 없다.

이항 연산자(+, -, *, /)는 두 리스트의 대응하는 위치에 있는 원소끼리 연산한다. 만약 한 리스트가 다른 쪽보다 짧으면, 짧은 쪽의 마지막 원소를 뒤에 더 넣어 둘의 길이를 맞춘다. 따라서 (1:2:3)+(4:5)는 (4:5)의 뒤에 마지막 원소인 5를 하나 더 넣어 (4:5:5)로 길이를 맞춰주고, 대응하는 위치끼리 더하여 (5:7:8)이 된다. 한쪽 리스트가 아예 빈 리스트이면 연산 결과는 빈 리스트이다. 예시로 A-A[2:2]는 뒤쪽이 빈 리스트이므로 결과도 빈 리스트이다. 이항 곱셈과 나눗셈은 덧셈과 뺄셈보다 우선순위가 높다.

리스트 이어붙이기는 쌍점(:) 연산자로 주어진다. 상수는 길이 1짜리 리스트로 본다.

대입은 등호(=) 연산자로 주어진다. 모든 변수는 한 글자이고, 대소문자를 구분하며 재정의되지 않는다. 변수의 정의는 이전에 정의되지 않은 변수를 포함하지 않지만, 자기 자신을 재귀적 정의로 포함하는 건 가능하다.

모든 나눗셈은 정수 나눗셈이고 C/C++의 정수 나눗셈 규칙을 따른다. 0으로 나누는 일은 발생하지 않는다. 표현식에 있는 상수는 항상 정수이고, 단항 연산자가 상수 바로 앞에 놓이는 경우는 없다. 계산 과정에서 나타나는 모든 정수는 32비트 정수형으로 표현할 수 있다.

입력

입력은 여러 줄로 구성된다. 각 줄은 대입문 또는 “print” 키워드로 시작하는 출력문이다. 각 줄의 길이는 50보다 작거나 같고, 입력은 30줄을 넘지 않는다.

출력

각 출력문마다 키워드 뒤에 오는 리스트의 원소를 공백 없이 쌍점(:)으로 구분하여 출력한다. 출력할 리스트의 길이는 항상 15보다 크지 않다.

예제 입력 1

print +(1:2:4)
print (1:2:3:4:5)[1:3]
print (1:2:3)+(4:5)
N=1:(N+1)
E=2*N
print E[:5]
print +E[:10]
F=1:1:(F+F[1:])
print F[:10]
#

예제 출력 1

7
2:3
5:7:8
2:4:6:8:10
110
1:1:2:3:5:8:13:21:34:55

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2008 M번

알고리즘 분류

  • 구현
  • 문자열
  • 파싱

접근

문제에서 주어졌듯이, 리스트 계산을 수행하는 인터프리터를 구현하는 문제이다. 이때 주의해야 할 것은, N=1:(N+1)과 같이 재귀적으로 정의되는 리스트가 존재한다는 것이다. 하지만 출력할 리스트의 길이는 15 이하임이 보장되므로, lazy하게 값을 평가해야 한다.

풀이

파싱의 경우에는, 구현이 간단하고 이해가 쉬운 Pratt 파싱을 사용하여 구현했다.

import java.util.Scanner
import kotlin.collections.forEach
import kotlin.math.max
import kotlin.math.min

val opBinding = mapOf(
    Token.EndOfLine to -1,
    Token.Plus to 2,
    Token.Minus to 2,
    Token.Asterisk to 3,
    Token.Slash to 4,
    Token.Colon to 1,
    Token.Equal to 0
)
val unaryOperatorsBinding = mapOf(
    Token.Print to 0,
    Token.Plus to 5,
    Token.Minus to 5,
    Token.Asterisk to 5,
    Token.Slash to 5,
)
data class Lexer(val tokens: List<Token>, var cursor: Int)

sealed interface Statement {
    data class AssignStatement(val ref: Value.ListRef, val value: Expr): Statement

    data class PrintStatement(val value: Expr): Statement
}

sealed interface Token {
    data class StringToken(val value: String): Token
    data class IntToken(val value: Int): Token
    data object Print: Token
    data object LParen: Token
    data object LBracket: Token
    data object RParen: Token
    data object RBracket: Token
    data object Plus: Token
    data object Asterisk: Token
    data object Minus: Token
    data object Slash: Token
    data object Colon: Token
    data object EndOfLine: Token
    data object Equal: Token
}

val operators = mapOf(
    '(' to Token.LParen,
    ')' to Token.RParen,
    '[' to Token.LBracket,
    ']' to Token.RBracket,
    '+' to Token.Plus,
    '-' to Token.Minus,
    '*' to Token.Asterisk,
    '/' to Token.Slash,
    ':' to Token.Colon,
    '=' to Token.Equal,
    ' ' to null,
    '\n' to Token.EndOfLine,
)

fun tokenize(text: String): List<Token> {
    val res = mutableListOf<Token>()
    var cursor = 0

    while (cursor < text.count()) {
        if (text[cursor].isDigit()) {
            var tmp = 0

            while (cursor < text.count() && text[cursor].isDigit()) {
                tmp = 10 * tmp + text[cursor].digitToInt()
                cursor++
            }

            res.add(Token.IntToken(tmp))
        } else if (operators.containsKey(text[cursor])) {
            operators[text[cursor]]?.let { res.add(it) }
            cursor++
        } else {
            res.add(buildString {
                while (cursor < text.count() && !text[cursor].isDigit() && !operators.containsKey(text[cursor])) {
                    append(text[cursor])
                    cursor++
                }
            }.let {
                if (it == "print") Token.Print
                else Token.StringToken(it)
            })
        }
    }

    return res.toList()
}

data class Env(
    val refs: MutableMap<Value.ListRef, Value> = mutableMapOf<Value.ListRef, Value>()
)

sealed interface Expr {
    data class SliceExpr(val value: Expr, val begin: Int, val end: Int): Expr {
        override fun execute(env: Env): Value {
            val value = this.value.execute(env).asLazyList(env)

            return if (value?.count != null) { // finite
                Value.ListValue({
                    if (end != -1 && it+begin >= end) return@ListValue value.get(end-1)

                    value.get(it+begin)
                }, max(0, min(if (end != -1) end-begin else Int.MAX_VALUE, value.count-begin)))
            } else {
                Value.ListValue({
                    val v = this.value.execute(env).asLazyList(env)!!

                    if (end != -1 && it+begin >= end) return@ListValue v.get(end-1)

                    v.get(it+begin)
                }, if (end != -1) ( if (begin >= end) 0 else end-begin ) else null)
            }
        }


        override fun toString(): String = "($value)[$begin:$end]"
    }

    data class UnaryOp(val op: Token, val value: Expr): Expr {
        override fun execute(env: Env): Value {
            val list = value.execute(env).asEagerList(env)

            return when (op) {
                Token.Plus -> list.fold(0) { acc, value -> value.asInt(env) + acc }
                Token.Minus -> {
                    var v = list[0].asInt(env)
                    list.drop(1).forEach { v -= it.asInt(env) }
                    v
                }
                Token.Asterisk -> list.fold(1) { acc, value -> value.asInt(env) * acc }
                Token.Slash -> {
                    var v = list[0].asInt(env)
                    list.drop(1).forEach { v /= it.asInt(env) }
                    v
                }
                else -> throw IllegalStateException()
            }.let { Value.IntValue(it) }
        }

        override fun toString(): String = "${op}(${value})"
    }

    data class BinaryOp(val left: Expr, val op: Token, val right: Expr): Expr {
        override fun execute(env: Env): Value {
            if (op == Token.Colon) {
                val l = left.execute(env).asLazyList(env)!!

                if (l.count == null) return l // l is infinite

                val left = l.asEagerList(env)

                return Value.ListValue({
                    if (it < left.count()) return@ListValue left[it]

                    right.execute(env).asLazyList(env)!!.get(it-left.count())
                }, right.execute(env).asLazyList(env)?.count?.let { it + left.count() })
            }

            val leftList = left.execute(env).asLazyList(env)
            val rightList = right.execute(env).asLazyList(env)

            if (leftList?.count == 0 || rightList?.count == 0) return Value.ListValue({ Value.Unit }, 0)

            val count = if (leftList?.count == null || rightList?.count == null) null else (max(leftList.count, rightList.count))

            return when (op) {
                Token.Plus -> Value.ListValue({
                    Value.IntValue(left.execute(env).asLazyList(env)!!.get(it).asInt(env) + right.execute(env).asLazyList(env)!!.get(it).asInt(env))
                }, count)
                Token.Minus -> Value.ListValue({
                    Value.IntValue(left.execute(env).asLazyList(env)!!.get(it).asInt(env) - right.execute(env).asLazyList(env)!!.get(it).asInt(env))
                }, count)
                Token.Asterisk -> Value.ListValue({
                    Value.IntValue(left.execute(env).asLazyList(env)!!.get(it).asInt(env) * right.execute(env).asLazyList(env)!!.get(it).asInt(env))
                }, count)
                Token.Slash -> Value.ListValue({
                    Value.IntValue(left.execute(env).asLazyList(env)!!.get(it).asInt(env) / right.execute(env).asLazyList(env)!!.get(it).asInt(env))
                }, count)
                else -> throw IllegalStateException("$op")
            }
        }

        override fun toString(): String = "($left) $op ($right)"
    }

    data class StringLiteral(val value: String): Expr {
        override fun execute(env: Env): Value {
            return Value.ListRef(this.value)
        }

        override fun toString(): String = value
    }

    data class IntLiteral(val value: Int): Expr {
        override fun execute(env: Env): Value = Value.IntValue(this.value)

        override fun toString(): String = value.toString()
    }

    fun execute(env: Env): Value
}

sealed interface Value {
    @JvmInline
    value class ListRef(val name: String): Value

    data class ListValue(val get: (Int) -> Value, val count: Int?): Value {
        override fun toString(): String = if (count != null) (0 until count).map { get(it) }.joinToString(":") else "?"
    }

    @JvmInline
    value class IntValue(val value: Int): Value {
        override fun toString(): String = value.toString()
    }

    data object Unit: Value

    fun asInt(env: Env): Int = when(this) {
        is ListRef -> env.refs[this]!!.asInt(env)
        is ListValue -> if (this.count == 1) this.get(0).asInt(env) else throw IllegalStateException()
        is IntValue -> this.value
        else -> throw IllegalStateException()
    }

    fun asLazyList(env: Env): Value.ListValue? = when(this) {
        is ListRef -> env.refs[this]?.asLazyList(env)
        is ListValue -> this
        is IntValue -> ListValue({ this }, 1)
        else -> throw IllegalStateException()
    }

    fun asEagerList(env: Env): List<Value> = when(this) {
        is ListRef -> env.refs[this]!!.asEagerList(env)
        is ListValue -> (0 until this.count!!).map { get(it) }
        is IntValue -> listOf(this)
        else -> throw IllegalStateException()
    }
}

fun pratt(lexer: Lexer, minBp: Int = 0): Expr {
    var left: Expr = when (lexer.tokens[lexer.cursor]) {
        Token.LParen -> {
            lexer.cursor++
            pratt(lexer, 0).also { lexer.cursor++ }
        }
        is Token.StringToken -> Expr.StringLiteral((lexer.tokens[lexer.cursor] as Token.StringToken).value).also { lexer.cursor++ }
        is Token.IntToken -> Expr.IntLiteral((lexer.tokens[lexer.cursor] as Token.IntToken).value).also { lexer.cursor++ }
        in unaryOperatorsBinding -> {
            val op = lexer.tokens[lexer.cursor]
            lexer.cursor++
            Expr.UnaryOp(op, pratt(lexer, unaryOperatorsBinding[op]!!))
        }
        else -> throw IllegalArgumentException("no ${lexer.tokens[lexer.cursor]}")
    }

    while (lexer.cursor < lexer.tokens.count() - 1) {
        val op = lexer.tokens[lexer.cursor]

        when (op) {
            Token.LParen -> {
                lexer.cursor++
                val right = pratt(lexer, 0)
                lexer.cursor++
                left = Expr.BinaryOp(left, op, right)
            }
            Token.LBracket -> {
                lexer.cursor++

                val begin = if (lexer.tokens[lexer.cursor] == Token.Colon) 0 else {
                    (lexer.tokens[lexer.cursor] as Token.IntToken).value.also { lexer.cursor++ }
                }

                lexer.cursor++

                val end = if (lexer.tokens[lexer.cursor] == Token.RBracket) -1 else {
                    (lexer.tokens[lexer.cursor] as Token.IntToken).value.also { lexer.cursor++ }
                }

                lexer.cursor++

                left = Expr.SliceExpr(left, begin, end)
            }
            Token.RParen -> {
                break
            }
            else -> {
                if (!opBinding.containsKey(op)) println("sibal: $op")
                val bp = opBinding[op]!!

                if (bp <= minBp) break
                lexer.cursor++
                val right = pratt(lexer, bp)
                left = Expr.BinaryOp(left, op, right)
            }
        }
    }

    return left
}

fun parseStatement(value: List<Expr>): Statement = when(value[0]) {
    is Expr.UnaryOp -> {
        if ((value[0] as Expr.UnaryOp).op is Token.Print) {
            Statement.PrintStatement((value[0] as Expr.UnaryOp).value)
        } else throw IllegalArgumentException("$value")
    }
    else -> throw IllegalArgumentException("${value[0]}")
}

fun parse(lexer: Lexer): List<Statement> {
    val statements = mutableListOf<Statement>()
    val expressions = mutableListOf<Expr>()

    while (lexer.cursor < lexer.tokens.count()) {
        expressions.add(pratt(lexer))

        when (lexer.tokens[lexer.cursor]) {
            is Token.Equal -> {
                val left = expressions[0]
                lexer.cursor++
                statements.add(Statement.AssignStatement(Value.ListRef((left as Expr.StringLiteral).value), pratt(lexer)))
                lexer.cursor++
                expressions.clear()
            }
            is Token.EndOfLine -> {
                statements.add(parseStatement(expressions))
                expressions.clear()
                lexer.cursor++
            }
            else -> {}
        }
    }

    return statements
}

fun main() = with(Scanner(System.`in`.bufferedReader()))  {
    val op = buildString {
        while (true) {
            val value = nextLine()
            if (value == "#") break

            appendLine(value)
        }
    }

    val env = Env()

    parse(Lexer(tokenize(op), 0)).forEach {
        when(it) {
            is Statement.PrintStatement -> {
                println(it.value.execute(env).let { v ->
                    if (v is Value.ListRef) v.asLazyList(env)
                    else v
                })
            }

            is Statement.AssignStatement -> {
                env.refs[it.ref] = it.value.execute(env)
            }
        }
    }
}

코드가 긴데, 천천히 살펴 보자. 인터프리터는 일반적으로 입력 → 토큰 → AST → 실행의 과정을 거친다. 여기서는 문자와 정수, 각각의 연산자를 토큰으로 정의했고, tokenize 함수를 통해 입력을 토큰화했다. 이후 파싱을 통해 AST를 구성하는데, 먼저 표현식을 파싱하고 이를 조합하여 구문을 파싱했다. 표현식 파싱이 앞서 말한 Pratt 파싱을 사용하여 구현했다. 각각의 구문을 실행하고, 표현식을 execute를 통해 평가하여 결과를 출력했다.

앞서 말했듯 리스트는 lazy하게 평가되어야 한다. 따라서 Value.ListValue는 리스트의 원소를 반환하는 get 함수와 리스트의 길이를 나타내는 count를 포함한다. 이를 통해 연산자를 정의하면 lazy한 평가를 쉽게 구현할 수 있다. 이때 count를 올바르게 추적해야 한다.

  • SliceExpr: 원래 리스트의 get으로 인덱스를 적절히 옮겨주면 된다. count는 end와 begin의 차이로 계산할 수 있고, end가 없는 경우에는 원래 리스트가 유한하다면 적절히 계산하고, 그 외의 경우에는 무한하다.
  • UnaryOp: 단항 연산자의 경우 입력으로 무한한 리스트가 주어지지 않음이 주어져 있으므로 eager하게 계산해도 된다.
  • BinaryOp: 대응하는 위치끼리 연산하므로, get에서는 각각의 리스트의 get을 호출하여 계산하면 된다. count는 두 리스트의 count 중 하나라도 0이면 0, 하나라도 null이면 null, 그렇지 않으면 두 count의 최대값이 된다. 리스트가 그 개수를 넘어가더라도 마지막 원소를 반환하도록 asLazyList와 SliceExpr을 정의했으므로, 새로운 리스트에서는 이를 고려할 필요는 없다.
    • 연결의 경우에도 왼쪽 리스트 안에 있다면 왼쪽 리스트의 원소를 반환하고, 그렇지 않다면 오른쪽 리스트의 원소로 적절히 옮겨서 반환하면 된다. 이때 왼쪽이 무한하다면 애초에 오른쪽 리스트를 고려할 필요가 없으므로, 왼쪽 리스트를 eager하게 계산해서 길이를 알아낼 수 있으니 오른쪽 리스트의 offset을 알아낼 수 있다.

시행착오

  • 처음에는 문제를 제대로 보지 않고 eager하게 구현하려 했는데, 예제조차 실행하지 못하는 것을 보고 lazy하게 구현해야 한다는 것을 깨달았다.
  • ListRef가 그대로 출력될 수 있음을 고려하지 않고 구현해서, print E같은 입력이 ListRef("E")로 출력되는 버그가 있었다.
  • ’-‘와 ’/‘은 fold로 구현하면 문제가 생길 수 있으므로 다른 방식으로 구현해야 했다. 예를 들어 -(1:2:3)의 경우, fold로 구현하면 ((0-1)-2)-3이 되어버리지만, 실제로는 1-(2-(3))이 되어야 한다.
  • 연산자 우선순위는 당연히 신경써야 한다.

후기

내 첫 다이아몬드 문제이자, 마지막 다이아몬드 문제일 것이다. 아직 알고리즘 관련 글을 많이 쓰지도 못 했는데, BOJ가 먼저 서비스를 종료할 예정이 되어 버렸다… lazy하게 평가하는 인터프리터를 구현하는 것이 까다롭고 시간도 오래 걸렸지만 뿌듯한 문제였다.

chevron_left
이전 글
[알고리즘] BOJ 21736: 헌내기는 친구가 필요해
article
현재 글
[알고리즘] BOJ 7607: 리스트 계산기
chevron_right
다음 글
[알고리즘] Farewell, BOJ
인용하기
BibTeX 
@misc{devngho202620260418boj7607,
  author       = {Yu, Dongho},
  title        = {BOJ 7607: 리스트 계산기},
  howpublished = {\url{https://ngho.dev/posts/20260418-boj7607}},
  year         = {2026},
  month        = {apr},
  note         = {Accessed: 2026-04-19}
}

APA 유동호. (2026년 4월 19일). BOJ 7607: 리스트 계산기. devngho 블로그. https://ngho.dev/posts/20260418-boj7607

Chicago 유동호. “BOJ 7607: 리스트 계산기.” devngho 블로그 (blog). 2026년 4월 19일. https://ngho.dev/posts/20260418-boj7607.

MLA 유동호. “BOJ 7607: 리스트 계산기.” devngho 블로그, 2026년 4월 19일, https://ngho.dev/posts/20260418-boj7607.